Uniqueness of the Finite Ruin Recurrence

Why Uniqueness Matters

First-step conditioning gives a recurrence for the probability of ruin before reaching a target fortune. But an equation alone does not show that a proposed formula is the answer: there could, in principle, be several sequences satisfying the same equations and boundary values. A uniqueness proof closes that gap. Once uniqueness is established, verifying a candidate at the boundaries and at every interior state is enough to identify it with the ruin probability.

Fix an integer \(N\ge2\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \((X_n)_{n\ge0}\) be the finite-capital gambler’s-ruin chain with state space \(S=\{0,1,\ldots,N\}\) and discrete time \(n\ge0\). States \(0\) and \(N\) are absorbing. At each interior state \(i\), the fortune increases to \(i+1\) with probability \(p\), and decreases to \(i-1\) with probability \(q=1-p\), where \(0<p<1\). Use the filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). The transition matrix is row-stochastic: its endpoint rows each put probability \(1\) on the endpoint, and its row at \(i\in\{1,\ldots,N-1\}\) has probability \(q\) at \(i-1\) and \(p\) at \(i+1\).

Define \(T_0=\inf\{n\ge0:X_n=0\}\) and \(T_N=\inf\{n\ge0:X_n=N\}\), with the infimum of the empty set equal to infinity. The ruin probability from \(i\) is \(r_i=\mathbb{P}_i(T_0<T_N)\). Starting at \(0\) gives \(r_0=1\), and starting at \(N\) gives \(r_N=0\). For an interior starting state, conditioning on the first transition gives the finite boundary-value problem

r_0=1,\qquad r_N=0,\qquad r_i=q\,r_{i-1}+p\,r_{i+1}\quad (1\le i\le N-1).

The strict inequality \(T_0<T_N\) matters: reaching \(N\) first is not ruin. The recurrence records that after the first move the probability of eventual ruin is the value at the new state. The result below concerns uniqueness of this finite system, not a formula for solving all choices of \(p\) and \(N\).

The Maximum Principle for the Recurrence

Theorem (Uniqueness of the finite ruin recurrence): Let \(N\ge2\), \(0<p<1\), and \(q=1-p\). There is at most one real sequence \((u_0,\ldots,u_N)\) satisfying \(u_0=1\), \(u_N=0\), and \(u_i=q\,u_{i-1}+p\,u_{i+1}\) for every \(1\le i\le N-1\).

Proof. Suppose \(u\) and \(v\) both satisfy these boundary values and recurrences. Define \(w_i=u_i-v_i\). Then \(w_0=w_N=0\), and subtraction of the two recurrences gives \(w_i=q\,w_{i-1}+p\,w_{i+1}\) at every interior state. Because the finite list \(w_0,\ldots,w_N\) has a maximum and a minimum, both are attained. If its maximum \(M\) were positive, it would be attained at an interior state \(i\), since the endpoint values are zero. Both neighboring values are at most \(M\), while \(w_i=q\,w_{i-1}+p\,w_{i+1}=M\). The weights \(q,p\) are strictly positive and sum to \(1\), so this weighted average can equal \(M\) only if \(w_{i-1}=w_{i+1}=M\). Repeating this implication along neighboring states forces \(w_0=M\), contradicting \(w_0=0\). Thus the maximum is not positive. If the minimum were negative, the same argument applied to a state attaining it forces that minimum to propagate to an endpoint, also contradicting the zero endpoint values. Therefore every \(w_i\) is both nonpositive and nonnegative, so \(w_i=0\) for all \(i\). Hence \(u=v\). \(\square\)

This argument is a discrete maximum principle: an interior value equal to a strict weighted average of its neighbors cannot be a strict maximum or minimum unless that extremal value propagates all the way to a boundary. The finite state space ensures that extrema are attained; the condition \(0<p<1\) ensures both neighbors receive positive weight.

Corollary (Candidate verification): Under the theorem’s assumptions, if a sequence \(c_0,\ldots,c_N\) has \(c_0=1\), \(c_N=0\), and \(c_i=q\,c_{i-1}+p\,c_{i+1}\) at every interior state, then \(c_i=r_i\) for all \(i\).

Proof. By conditioning on the first transition, the ruin probabilities \(r_i=\mathbb{P}_i(T_0<T_N)\) have the stated boundary values and satisfy the recurrence. The candidate sequence \(c\) satisfies the same system by assumption. The uniqueness theorem therefore gives \(c_i=r_i\) at every state. \(\square\)

The corollary is the practical use of uniqueness. It does not require deriving a candidate from scratch. It does require checking every equation, including both boundary values. A candidate that looks plausible or has values between \(0\) and \(1\) is not validated until those substitutions are made.

Worked Verifications

Worked Example: One Interior State

Take \(N=2\), \(p=\tfrac34\), and \(q=\tfrac14\). The states are \(0,1,2\), and the transition matrix in that order is

P= \begin{bmatrix} 1&0&0\\ \tfrac14&0&\tfrac34\\ 0&0&1 \end{bmatrix}.

The row sums are \(1\), \(\tfrac14+\tfrac34=1\), and \(1\), so this is a valid transition matrix. There is only one interior equation, at state \(1\). The candidate values \(c_0=1\), \(c_1=\tfrac14\), \(c_2=0\) have the required boundary values, and substitution gives

q c_0+p c_2 =\tfrac14\cdot1+\tfrac34\cdot0 =\tfrac14 =c_1.

Thus the candidate satisfies the entire boundary problem. By the corollary, \(r_1=\tfrac14\). As a direct check, ruin from state \(1\) occurs exactly when the first move is to \(0\), which has probability \(\tfrac14\).

Worked Example: Checking Both Interior Equations

Take \(N=3\), \(p=\tfrac23\), and \(q=\tfrac13\). In state order \(0,1,2,3\), the transition matrix is

P= \begin{bmatrix} 1&0&0&0\\ \tfrac13&0&\tfrac23&0\\ 0&\tfrac13&0&\tfrac23\\ 0&0&0&1 \end{bmatrix}.

The endpoint rows sum to \(1\), and each interior row sums to \(\tfrac13+\tfrac23=1\). Consider the candidate \((c_0,c_1,c_2,c_3)=(1,\tfrac37,\tfrac17,0)\). It has \(c_0=1\) and \(c_3=0\). At state \(1\), the recurrence gives

q c_0+p c_2 =\tfrac13\cdot1+\tfrac23\cdot\tfrac17 =\tfrac13+\tfrac{2}{21} =\tfrac{7}{21}+\tfrac{2}{21} =\tfrac37 =c_1.

At state \(2\), it gives

q c_1+p c_3 =\tfrac13\cdot\tfrac37+\tfrac23\cdot0 =\tfrac17 =c_2.

Both interior equations and both boundary values hold. Uniqueness therefore identifies this candidate with the ruin probabilities: \(r_1=\tfrac37\) and \(r_2=\tfrac17\). The values are nonnegative and no greater than \(1\), as probabilities must be; the recurrence and uniqueness, rather than that range check alone, establish the identification.

Worked Example: A Four-Unit Boundary Problem

Take \(N=4\), \(p=\tfrac23\), and \(q=\tfrac13\). The transition matrix in state order \(0,1,2,3,4\) is

P= \begin{bmatrix} 1&0&0&0&0\\ \tfrac13&0&\tfrac23&0&0\\ 0&\tfrac13&0&\tfrac23&0\\ 0&0&\tfrac13&0&\tfrac23\\ 0&0&0&0&1 \end{bmatrix}.

Each endpoint row sums to \(1\), and the three interior rows each sum to \(\tfrac13+\tfrac23=1\). Test the candidate \((c_0,c_1,c_2,c_3,c_4)=(1,\tfrac7{15},\tfrac15,\tfrac1{15},0)\). At state \(1\), the weighted neighbor value is

\tfrac13c_0+\tfrac23c_2 =\tfrac13+\tfrac{2}{15} =\tfrac5{15}+\tfrac2{15} =\tfrac7{15} =c_1.

At state \(2\), it is

\tfrac13c_1+\tfrac23c_3 =\tfrac7{45}+\tfrac2{45} =\tfrac9{45} =\tfrac15 =c_2.

At state \(3\), it is

\tfrac13c_2+\tfrac23c_4 =\tfrac1{15}+0 =\tfrac1{15} =c_3.

The endpoint values also match the required boundary values. Since every equation has been checked, the corollary gives \(r_1=\tfrac7{15}\), \(r_2=\tfrac15\), and \(r_3=\tfrac1{15}\). In particular, the middle value is verified by the explicit substitution \(\tfrac7{45}+\tfrac2{45}=\tfrac9{45}=\tfrac15\).

What the Assumptions Do—and Do Not—Say

Uniqueness is not the same as existence. The theorem says that two solutions cannot differ; it does not claim that an arbitrary list of proposed values solves the recurrence. The examples establish existence for their particular candidates by direct substitution. For the probability problem, the sequence \(r_i\) itself is defined by probabilities, and first-step conditioning shows that it satisfies the boundary equations. The corollary then allows any other verified solution to be identified with it.

The strict assumption \(0<p<1\) is essential to the propagation step in this proof. If \(p=1\), then \(q=0\) and the interior equations are \(u_i=u_{i+1}\); the boundary value \(u_N=0\) forces all interior values to be \(0\), uniquely. If \(p=0\), the equations are \(u_i=u_{i-1}\); the value \(u_0=1\) forces all interior values to be \(1\), uniquely. These deterministic endpoint cases can be checked directly, but they are not covered by the strict-weight maximum-principle proof. In the usual nondegenerate game, both directions are possible and the theorem applies as stated.

Common mistake: reversing the direction of the transition weights. In the \(N=3\), \(p=\tfrac23\) example, the probability of moving up is \(p\), and that of moving down is \(q=\tfrac13\). Reversing these weights at state \(1\) and testing the reversed candidate \(c_1=\tfrac17\), \(c_2=\tfrac37\) gives the incorrect equation \(c_1=\tfrac13c_0+\tfrac23c_2\). Its right side is \(\tfrac13+\tfrac23\cdot\tfrac37=\tfrac13+\tfrac27=\tfrac{13}{21}\), which is not \(\tfrac17=\tfrac3{21}\). The correct equation uses the downward probability on \(c_0\) and the upward probability on \(c_2\): \(\tfrac13c_0+\tfrac23c_2\). With the correct candidate \(c_1=\tfrac37\), \(c_2=\tfrac17\), that expression is \(\tfrac13+\tfrac2{21}=\tfrac37\). Always attach each probability to the state reached by its move.

For practical use, keep the logical steps separate: write the boundary values, write the recurrence with probabilities matched to their destinations, substitute the candidate at every interior state, and only then invoke uniqueness. A missed boundary value or a single failed interior equation means the candidate has not been verified.

Check Your Understanding

For each question, use the recurrence and boundary values explicitly; when asked to verify a candidate, substitute it into every relevant equation.

For \(N=2\), \(p=\tfrac25\), and \(q=\tfrac35\), what value must a candidate have at state \(1\) if its boundary values are \(c_0=1\), \(c_2=0\)?
In the uniqueness proof, where is finiteness of the state space used?
Why does a positive maximum of the difference of two solutions have to propagate to an endpoint when \(0<p<1\)?
For \(N=3\), \(p=\tfrac23\), test the candidate \((1,\tfrac37,\tfrac17,0)\) at state \(2\).
Explain why checking that a candidate’s entries lie between \(0\) and \(1\) is not enough to prove that they are ruin probabilities.