Expected Duration in a Fair Finite Game

From Fair Plays to Expected Duration

In a finite gambler’s ruin game, the fortune changes by one unit at each play until it reaches either zero or a fixed upper boundary. Ruin probabilities describe which boundary is reached; expected duration asks a different question: how many plays does the game last? In the fair game, the answer depends on the starting fortune through a simple quadratic expression. The recurrence explains why that expression appears, and the boundary conditions determine it uniquely.

Fix an integer \(N\ge1\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \((X_n)_{n\ge0}\) be the discrete-time Markov chain with state space \(S=\{0,1,\ldots,N\}\). The fortunes \(0\) and \(N\) are absorbing: from either one the chain stays there with probability \(1\). From each interior fortune \(i\in\{1,\ldots,N-1\}\), the next fortune is \(i-1\) or \(i+1\), each with probability \(\tfrac12\). Thus every interior transition row has sum \(\tfrac12+\tfrac12=1\), and each boundary row has sum \(1\). Use the filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\), and write \(\mathbb{P}_i\) and \(\mathbb{E}_i\) for probability and expectation when \(X_0=i\).

The game ends at the first time the chain reaches a boundary. Its duration, measured in plays, is \(T=\inf\{n\ge0:X_n\in\{0,N\}\}\). This is a stopping time for \((\mathcal{F}_n)\), since whether \(T\le n\) is determined by \(X_0,\ldots,X_n\). In particular, if the initial fortune is already a boundary, then \(T=0\). For each \(i\), denote the expected duration by \(t_i=\mathbb{E}_i[T]\), allowing an expectation to be infinite until finiteness is established.

The recurrence follows by conditioning on the first play, but to use it as an equation for finite numbers we first check that the duration has finite expectation. From any interior state, \(N\) consecutive losses force absorption at \(0\) within at most \(N\) plays. The probability of those losses is \(2^{-N}>0\). This gives a uniform chance of absorption in successive blocks of \(N\) plays, even though the current interior fortune can vary.

Why the Recurrence Has One Solution

Proof. Suppose \(u\) and \(v\) are two such sequences, and set \(w_i=u_i-v_i\). Subtracting their equations gives \(w_0=w_N=0\) and \(w_i=\tfrac12w_{i-1}+\tfrac12w_{i+1}\) for \(1\le i\le N-1\). Rearranging yields \(w_{i+1}-w_i=w_i-w_{i-1}\). If \(d_i=w_i-w_{i-1}\) for \(1\le i\le N\), this says \(d_{i+1}=d_i\) for \(1\le i<N\). Hence all \(d_i\) equal a constant \(d\), so \(w_N-w_0=\sum_{i=1}^N d_i=Nd\). Since both boundary values are zero, \(Nd=0\); as \(N\ge2\), \(d=0\). All increments vanish and \(w_i=0\) for every \(i\), proving \(u=v\). \(\square\)

This uniqueness result means that it is enough to find a finite sequence satisfying the recurrence and both boundary values. To confirm that the expected durations themselves are finite, put \(r=2^{-N}\). Conditional on the history at time \(kN\), if the game is still unabsorbed then the current fortune is interior. The probability of \(N\) consecutive losses in the next \(N\) plays is \(r\), and that event ensures absorption within the block. Therefore \(\mathbb{P}_i(T>(k+1)N)\le(1-r)\mathbb{P}_i(T>kN)\). Starting from \(\mathbb{P}_i(T>0)\le1\), induction gives \(\mathbb{P}_i(T>kN)\le(1-r)^k\). For \(kN\le n<(k+1)N\), \(\mathbb{P}_i(T>n)\le(1-r)^k\). The tail-sum identity for a nonnegative integer-valued random variable now gives \(\mathbb{E}_i[T]=\sum_{n\ge0}\mathbb{P}_i(T>n)\le N\sum_{k\ge0}(1-r)^k=N/r<\infty\). Boundary starts have duration zero, so finiteness holds there too.

Solving the Fair-Game Recurrence

Proof. The expectation is finite by the block bound. At a boundary \(t_0=t_N=0\). From any interior state, the first play takes one unit of time and leads to \(i-1\) or \(i+1\) with probability \(\tfrac12\) each. The Markov property, applied after that first play, gives \(t_i=1+\tfrac12t_{i-1}+\tfrac12t_{i+1}\). Define the candidate \(v_i=i(N-i)\). It has the required boundary values, since \(v_0=0\cdot N=0\) and \(v_N=N\cdot0=0\). For an interior \(i\), expand both neighboring terms: \((i-1)(N-i+1)=iN-i^2+2i-N-1\), and \((i+1)(N-i-1)=iN-i^2+N-2i-1\). Their average is \(iN-i^2-1=i(N-i)-1\). Consequently \(1+\tfrac12v_{i-1}+\tfrac12v_{i+1}=1+i(N-i)-1=v_i\). Thus \(v\) satisfies the duration recurrence and both boundary conditions. By the proposition, the recurrence has at most one solution; \(t\) is a solution, so \(t_i=v_i=i(N-i)\). When \(N=1\), there are no interior states: both possible starts are boundaries and have duration zero, also given by the formula. \(\square\)

The equation can also be written as a constant second-difference equation: \(t_{i+1}-2t_i+t_{i-1}=-2\) for interior \(i\). The quadratic formula is consistent with that form: the first differences of \(i(N-i)\) decrease by \(2\) at each step. The boundary values then fix the particular quadratic. The first-step equation emphasizes the probabilistic origin of the recurrence; the second-difference form makes its algebraic structure visible.

Interpreting the Formula and Avoiding an Algebra Error

The product \(i(N-i)\) is zero at either boundary and is largest near the middle of the interval. This matches the duration question: starting close to a boundary leaves fewer states to traverse before absorption, while a middle starting fortune has more opportunity to wander before reaching either endpoint. The formula gives an exact expected number of plays; it does not assert that every game lasts that many plays. Individual durations vary, and the expectation is an average over repeated games with the same starting fortune.

A frequent error is to expand the neighboring quadratic terms incorrectly. For example, with \(N=4\) and \(i=2\), the correct value is \((i+1)(N-i-1)=3\cdot1=3\). The incorrect expansion \(iN-i^2-N-1\) would give \(8-4-4-1=-1\), contradicting the direct product. The correct expansion is \(iN-i^2+N-2i-1\), which gives \(8-4+4-4-1=3\). The other neighbor is \((i-1)(N-i+1)=1\cdot3=3\), or \(iN-i^2+2i-N-1=8-4+4-4-1=3\). Their average is \(3\), which equals \(i(N-i)-1=4-1\). Adding the one play in the recurrence gives \(4\), as required.

This check illustrates a useful habit: when an algebraic expansion is central to a recurrence proof, test it at a small admissible state and also verify it symbolically. Here the direct products expose the sign error, and the corrected expansions show that the average neighboring value is exactly one less than the current quadratic candidate. The \(+1\) in the duration recurrence then restores the candidate value. Omitting that term would produce a different equation and would not count the play already made.