Uniqueness of the Expected-Duration Recurrence

Why Uniqueness Matters

For a finite gambler’s ruin game, the expected time to reach either absorbing boundary satisfies a recurrence at every interior fortune. But writing down a recurrence is not, by itself, enough to identify the expected duration: we must also impose the correct boundary values and know that no second function satisfies the same system. Uniqueness supplies the missing link. Once a candidate has the right endpoint values and satisfies every interior equation, it must be the expected duration.

Consider a gambler whose fortune is \(i\in\{0,1,\ldots,N\}\). At each round, the fortune increases by one with probability \(p\) and decreases by one with probability \(q=1-p\), until it reaches \(0\) or \(N\). Assume \(N\ge1\) and \(0<p<1\), so both step probabilities are strictly positive. On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \((X_n)_{n\ge0}\) be this chain, with state space \(S=\{0,1,\ldots,N\}\) and discrete time \(n\ge0\). Its filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). The endpoints are absorbing, and the duration is \(T=\inf\{n\ge0:X_n\in\{0,N\}\}\).

The endpoint values express that the game ends immediately when the initial fortune is already \(0\) or \(N\). For an interior state, the equation counts the round just played, then weights the remaining expected duration according to the next state. This is the first-step equation established in the earlier material on expected game duration. The result below explains why satisfying these equations and endpoints is decisive.

Finiteness and Uniqueness

Proof. If \(N=1\), the chain starts at an absorbing endpoint, so \(T=0\) from either state and the boundary values uniquely specify the solution. Now suppose \(N\ge2\). Set \(r=\min(p,q)>0\). From any interior state \(i\), a run of \(i\) consecutive downward steps reaches \(0\) within at most \(N\) steps, and its probability is \(q^i\). Since \(i\le N\) and \(q\ge r\), this probability is at least \(r^N\). Thus, from every interior state, the probability of absorption within the next \(N\) steps is at least \(\varepsilon=r^N>0\). By the Markov property, on the event \(T>mN\), conditional on \(\mathcal{F}_{mN}\), the probability of surviving another \(N\) steps is at most \(1-\varepsilon\). Therefore \(\mathbb{P}_i(T>(m+1)N)\le(1-\varepsilon)\mathbb{P}_i(T>mN)\), and induction gives \(\mathbb{P}_i(T>mN)\le(1-\varepsilon)^m\). For \(mN\le n<(m+1)N\), \(\mathbb{P}_i(T>n)\le(1-\varepsilon)^m\). Hence \(\mathbb{E}_i[T]=\sum_{n\ge0}\mathbb{P}_i(T>n)\le N\sum_{m\ge0}(1-\varepsilon)^m=N/\varepsilon<\infty\). Conditioning on the first step now gives the stated recurrence for \(k_i\), with \(k_0=k_N=0\).

It remains to prove uniqueness. Suppose \(u_0=u_N=0\) and \(u_i=p u_{i+1}+q u_{i-1}\) for every interior state \(i\). Let \(M=\max_{0\le i\le N}u_i\). If \(M>0\), it is attained at an interior state \(i\), since both endpoints equal zero. The recurrence writes \(M\) as a weighted average of \(u_{i-1}\) and \(u_{i+1}\), each at most \(M\), with strictly positive weights \(q\) and \(p\). For that average to equal \(M\), both neighbors must equal \(M\). Repeating this argument at each interior state reached to the right forces \(u_N=M\), contradicting \(u_N=0\). Thus \(M\le0\). If any value of \(u\) were negative, the minimum \(m<0\) would be attained in the interior. Its weighted-average equation, with both neighbors at least \(m\) and both weights strictly positive, forces both neighbors to equal \(m\). Repeating to the right forces \(u_N=m\), again a contradiction. Thus every value is zero. The difference of any two solutions satisfies this homogeneous system, so the solution is unique. For \(N=1\), uniqueness follows from the endpoints alone. \(\square\)

Proof. The theorem shows that the expected-duration vector \(k\) exists, is finite, and satisfies the boundary-value problem. By assumption, \(c\) satisfies the same equations and endpoints. The difference \(u_i=c_i-k_i\) therefore has zero endpoints and satisfies \(u_i=p u_{i+1}+q u_{i-1}\) at every interior state. The uniqueness proof shows \(u_i=0\) for all \(i\), so \(c_i=k_i\) at every state. \(\square\)

Using the Verification Principle

The principle has two separate requirements: a proposed vector must satisfy the interior recurrence, and it must satisfy both endpoint conditions. Checking only one of these does not establish that the vector is the expected duration. In the examples, the transition matrices make the step probabilities and absorbing boundaries explicit; each row is checked before the recurrence is used.

Common Pitfalls and Why the Endpoints Matter

A frequent error is to check an interior equation but overlook an endpoint. The recurrence only constrains interior states; without the boundary values, it is not the expected-duration problem. For example, adding the same constant to every entry of a solution preserves each interior equation because \(p+q=1\), but the resulting vector generally fails the endpoint conditions. The endpoints are not an optional check: they specify where the game stops and anchor the recurrence.

Arithmetic accuracy matters just as much. In the three-fortune example, the first recurrence uses \(k_2=\tfrac{15}7\). A mistaken multiplication might claim \(1+\tfrac13\cdot\tfrac{15}7=\tfrac{22}7\). But \(\tfrac13\cdot\tfrac{15}7=\tfrac{15}{21}=\tfrac57\), so the correct value is \(1+\tfrac57=\tfrac{12}7\). The wrong value would fail the recurrence and cannot be accepted as a duration.

The assumptions also have a role. Strict positivity of \(p\) and \(q\) allows the uniqueness proof to propagate an interior maximum or minimum toward an endpoint; it also gives a positive chance of absorption within a bounded number of steps. If \(p=1\), for example, every interior state moves upward with certainty. For \(N=2\), the expected duration from state \(1\) is \(1\), so the recurrence is \(k_1=1+k_2\), with \(k_2=0\). The homogeneous equation is \(u_1=u_2\), and \(u_0=u_2=0\) still forces \(u_1=0\) in this particular case. However, that boundary case is outside the theorem’s assumptions and is not covered by its strict-weight argument; assumptions should not be silently weakened.

In practice, a reliable verification has a fixed order: record the two zero endpoint values, write the recurrence for every interior state, substitute the candidate into each equation, and only then invoke uniqueness. The calculation may be short, but omitting any of these checks leaves a gap between a plausible formula and the expected duration.