A Reliable Setup for Expected Game Duration
In a finite gambler’s ruin game, an expected duration is found from a recurrence, but the recurrence is easy to misread. Omitting the cost of the first play, assigning a nonzero duration at an absorbing endpoint, or changing a sign while rearranging the equation can produce plausible-looking but incorrect answers. The safest approach is to define the stopping time first, write the transition probabilities explicitly, and check the final values in the original equations.
Let \(N\ge2\) be an integer and let \(0<p<1\), with \(q=1-p\). On a probability space \((\Omega,\mathcal F,\mathbb P)\), let \((X_n)_{n\ge0}\) be the fortune after \(n\) plays, with state space \(S=\{0,1,\ldots,N\}\) and filtration \(\mathcal F_n=\sigma(X_0,\ldots,X_n)\). From each interior state \(i\), the chain moves to \(i+1\) with probability \(p\) and to \(i-1\) with probability \(q\). States \(0\) and \(N\) are absorbing. Define the duration to absorption by \(T=\inf\{n\ge0:X_n\in\{0,N\}\}\), and write \(e_i=\mathbb E_i[T]\). In particular, a game started at an endpoint has already ended, so \(e_0=e_N=0\).
Proof. First check finiteness so that the expectation equations are meaningful. From any interior state \(i\), the event that the next \(N-i\) plays are all upward moves reaches \(N\) within \(N-i\le N\) plays. Its probability is \(p^{N-i}\ge p^N>0\). This event only requires the upward moves up to the time the chain reaches \(N\); it does not require further moves after absorption. Thus, from every interior state, the conditional probability of absorption during the next \(N\) plays is at least \(p^N\). By the Markov property, \(\mathbb P_i(T>kN)\le(1-p^N)^k\) for every integer \(k\ge0\): the bound holds at \(k=0\), and conditional on survival through \(kN\), the probability of surviving the next block is at most \(1-p^N\). For \(kN\le n<(k+1)N\), \(\mathbb P_i(T>n)\le\mathbb P_i(T>kN)\), so \(\sum_{n\ge0}\mathbb P_i(T>n)\le N\sum_{k\ge0}(1-p^N)^k=N/p^N<\infty\). The tail-sum formula gives \(\mathbb E_i[T]<\infty\). If \(i\) is interior, one play elapses before the chain moves to \(i+1\) or \(i-1\); conditioning on that first transition gives \(e_i=1+p e_{i+1}+q e_{i-1}\). Starting at either endpoint gives \(T=0\), proving the boundary values. \(\square\)
The \(1\) in this recurrence counts the play just taken. It is not a probability and it does not disappear when the next state is an endpoint. The endpoint’s remaining duration is zero; the play that brought the chain there has already been counted by the \(1\).
Two Checks Before Solving
A recurrence calculation needs more than algebra. First, the transition probabilities must match the game: upward with probability \(p\), downward with probability \(q\), and \(p+q=1\). Second, after solving, substitute the proposed values into the original recurrence, not merely into a rearranged version that may contain the original sign error.
For finite games, the solution to the duration recurrence is unique. This fact lets a direct verification establish the answer: if candidate values have the right boundary values and satisfy every interior equation, they must be the expected durations.
Proof. Suppose two vectors satisfy the system, and let \(d_i\) be their difference at state \(i\). Then \(d_0=d_N=0\), and \(d_i=p d_{i+1}+q d_{i-1}\) for each interior \(i\). Let \(M=\max_{0\le j\le N}|d_j|\). If \(M>0\), it is attained at an interior state \(i\). The recurrence and \(p+q=1\) give \(|d_i|\le p|d_{i+1}|+q|d_{i-1}|\le M\). Since \(|d_i|=M\) and both weights are strictly positive, equality requires \(|d_{i+1}|=|d_{i-1}|=M\); equality in the first inequality also requires both neighbors to have the same sign as \(d_i\). Repeating this argument along adjacent states forces an endpoint to have absolute value \(M\), contradicting \(d_0=d_N=0\). Therefore \(M=0\), so the two vectors agree at every state. \(\square\)
Worked Examples: Spotting the Errors in the Equations
Worked Example: The Missing One-Step Term
Consider a fair game with \(N=4\), so \(p=q=\tfrac12\). In state order \(0,1,2,3,4\), the transition matrix is
The row sums are \(1\), \( \tfrac12+\tfrac12=1\), \( \tfrac12+\tfrac12=1\), \( \tfrac12+\tfrac12=1\), and \(1\), respectively. The duration equations are \(e_0=e_4=0\), \(e_1=1+\tfrac12 e_2\), \(e_2=1+\tfrac12 e_3+\tfrac12 e_1\), and \(e_3=1+\tfrac12 e_2\). By symmetry, or by subtracting the first and third equations, \(e_1=e_3\). Then \(e_1=1+\tfrac12e_2\), and \(e_2=1+e_1\). Substitution gives \(e_1=1+\tfrac12(1+e_1)\), so \(\tfrac12e_1=\tfrac32\) and \(e_1=3\). Hence \(e_2=4\) and \(e_3=3\).
Check: At state \(1\), \(1+\tfrac12(4)+\tfrac12(0)=3\); at state \(2\), \(1+\tfrac12(3)+\tfrac12(3)=4\); and at state \(3\), \(1+\tfrac12(0)+\tfrac12(4)=3\). If the \(1\) is omitted, the zero vector satisfies the resulting homogeneous equations and the boundary values. That answer fails the original equation at state \(1\), since \(0\ne1+\tfrac12(0)+\tfrac12(0)\). The missing term is exactly the play already taken.
Worked Example: An Incorrect Endpoint Duration
Now take a fair game with \(N=3\). In state order \(0,1,2,3\), the matrix rows are \((1,0,0,0)\), \((\tfrac12,0,\tfrac12,0)\), \((0,\tfrac12,0,\tfrac12)\), and \((0,0,0,1)\). Their sums are \(1\), \(\tfrac12+\tfrac12=1\), \(\tfrac12+\tfrac12=1\), and \(1\). Since duration means time to hit either endpoint, \(e_0=e_3=0\). The interior equations are \(e_1=1+\tfrac12e_2\) and \(e_2=1+\tfrac12e_1\). Substituting the second into the first gives \(e_1=1+\tfrac12+\tfrac14e_1\), hence \(\tfrac34e_1=\tfrac32\), \(e_1=2\), and \(e_2=2\).
A common off-by-one error sets \(e_3=1\), as if the game takes one more play after reaching \(3\). Keeping that incorrect boundary value would give \(e_1=1+\tfrac12e_2\) and \(e_2=1+\tfrac12e_1+\tfrac12(1)=\tfrac32+\tfrac12e_1\). Substituting yields \(e_1=\tfrac74+\tfrac14e_1\), so \(e_1=\tfrac73\) and \(e_2=\tfrac83\). These are not durations for the stated stopping time: the second equation of the correct system requires \(e_2=1+\tfrac12e_1=\tfrac73\), not \(\tfrac83\).
The distinction is between absorption duration and a first-return time. Here \(T\) includes \(n=0\), so starting at \(3\) gives \(T=0\). A first-return time instead requires \(n\ge1\), which is a different random variable and is not the boundary condition for this duration problem.
Worked Example: A Sign Error and an Invalid Fair-Game Formula
Consider \(N=3\), with upward probability \(p=\tfrac23\) and downward probability \(q=\tfrac13\). In state order \(0,1,2,3\), the transition matrix rows are \((1,0,0,0)\), \((\tfrac13,0,\tfrac23,0)\), \((0,\tfrac13,0,\tfrac23)\), and \((0,0,0,1)\). Their sums are \(1\), \(\tfrac13+\tfrac23=1\), \(\tfrac13+\tfrac23=1\), and \(1\). The boundary values are \(e_0=e_3=0\), and the equations reduce to \(e_1=1+\tfrac23 e_2\) and \(e_2=1+\tfrac13e_1\). Substituting the second equation into the first gives \(e_1=1+\tfrac23+\tfrac29e_1\); therefore \(\tfrac79e_1=\tfrac53\), \(e_1=\tfrac{15}{7}\), and \(e_2=1+\tfrac13\cdot\tfrac{15}{7}=\tfrac{12}{7}\).
Check: \(1+\tfrac23\cdot\tfrac{12}{7}=\tfrac{7}{7}+\tfrac{8}{7}=\tfrac{15}{7}\), and \(1+\tfrac13\cdot\tfrac{15}{7}=\tfrac{7}{7}+\tfrac{5}{7}=\tfrac{12}{7}\). Another way to check the signs is to rearrange the original recurrence as \(p(e_{i+1}-e_i)-q(e_i-e_{i-1})=-1\). At \(i=1\), the left side is \(\tfrac23(-\tfrac37)-\tfrac13(\tfrac{15}{7})=-\tfrac27-\tfrac57=-1\). Replacing \(-1\) with \(+1\) is a sign error, detectable by substituting back into the original recurrence.
A second mistake is to substitute the fair-game expression \(i(N-i)\) into a biased game without checking it. Here that expression gives candidate values \(e_1=e_2=2\). At state \(1\), the right side of the biased recurrence would be \(1+\tfrac23(2)+\tfrac13(0)=\tfrac73\), which is not \(2\). The formula therefore does not solve this biased recurrence. A formula from another case is not a substitute for checking the present equations.
A Practical Error-Checking Routine
For a finite expected-duration problem, a short sequence of checks prevents most of the errors discussed above. These checks do not replace solving the equations; they test whether the equations and the proposed solution correspond to the stated game.
State whether duration is the first hit of the absorbing set, with time index starting at \(n=0\). This determines whether an endpoint has remaining duration zero.
For each interior state, record the probability of moving up and down; check that they sum to \(1\). Keep the absorbing rows distinct from interior rows.
For an interior state, write \(1\) plus the probability-weighted expected duration after that play. The endpoint terms remain in the equation, but their expected remaining durations are zero.
Check both boundary values and every interior equation. This catches algebraic sign errors and formulas imported from a different probability regime.
These checks matter because the recurrence is a model of the stopping rule, not merely an algebraic pattern. Changing \(e_N=0\) to \(e_N=1\) changes the random variable being measured; deleting the \(1\) changes the number of plays counted; and changing a sign changes the transition balance. A result that solves a modified system can be internally consistent and still answer the wrong question.
Check Your Understanding
For each question, state the boundary conditions before solving, and substitute any proposed values into the original interior equations.
- For a fair game with endpoints \(0\) and \(4\), why does a game started at \(4\) have absorption duration zero rather than one?
- In the fair \(N=4\) example, verify the duration equation at state \(2\) using the computed values.
- For \(N=3\), \(p=\tfrac23\), and \(q=\tfrac13\), identify the sign on the right side of \(p(e_{i+1}-e_i)-q(e_i-e_{i-1})\) after rearranging the duration recurrence.
- Explain why the event used to bound absorption within \(N\) plays requires only the upward moves up to the time the chain reaches \(N\).
- Give one substitution check that shows \(i(N-i)\) does not solve the \(N=3\), \(p=\tfrac23\) duration recurrence.