Exact Expected-Duration Calculations

From the Game to an Exact Calculation

In a finite gambler’s ruin game, the capital changes by one unit at each play until it reaches either boundary. The expected duration depends on both the starting capital and the win probability. When the probabilities are rational, the first-step equations can be solved exactly: no approximation or simulation is needed. This tutorial focuses on carrying out those calculations and checking each answer against the original equations.

Fix an integer \(N\ge1\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \((X_n)_{n\ge0}\) be the capital after \(n\) plays, with state space \(S=\{0,1,\ldots,N\}\) and discrete time \(n\). At each play before absorption, the capital increases by \(1\) with probability \(p\) and decreases by \(1\) with probability \(q=1-p\), where \(0<p<1\). States \(0\) and \(N\) are absorbing. The transition rows are \(p_{00}=1\), \(p_{NN}=1\), and, for \(1\le i\le N-1\), \(p_{i,i+1}=p\), \(p_{i,i-1}=q\), with all other entries zero. Thus the boundary rows sum to \(1\), and every interior row sums to \(p+q=1\).

Let \(T=\inf\{n\ge0:X_n\in\{0,N\}\}\), and define \(t_i=\mathbb{E}_i[T]\), where the subscript means \(X_0=i\). In particular, \(t_0=t_N=0\). The natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). For \(1\le i\le N-1\), conditioning on the first play gives the expected-duration recurrence

The \(1\) counts the play just made. The coefficient \(p\) belongs to the transition to \(i+1\), and \(q\) belongs to the transition to \(i-1\). The boundary conditions are \(t_0=t_N=0\). To use this recurrence reliably, first check that the expected duration is finite, then solve the equations and substitute the proposed values back into every equation.

Proof. Write \(q=1-p\), so \(0<q<1\). For any interior state \(i\), the event that the next \(i\) potential tosses are all losses has probability \(q^i\), and on that event the chain reaches \(0\) within \(i\le N\) plays. Here the independent tosses are defined even if the game has already stopped; tosses after absorption do not change the chain. Let \(r=\min(p,q)>0\). Since \(i\le N\), \(q^i\ge q^N\), and since \(q\ge r\), \(q^N\ge r^N\). Consequently, from every interior state the probability of absorption within the next \(N\) steps is at least \(\delta=r^N>0\). Applying the same bound conditionally at successive multiples of \(N\) gives \(\mathbb{P}_i(T>kN)\le(1-\delta)^k\) for every integer \(k\ge0\). For a nonnegative integer-valued random variable, \(\mathbb{E}_i[T]=\sum_{n\ge0}\mathbb{P}_i(T>n)\). Grouping terms into blocks of \(N\), this sum is at most \(N\sum_{k\ge0}(1-\delta)^k=N/\delta<\infty\). Conditioning on the first step is therefore valid and gives the stated recurrence. To prove uniqueness, subtract any two solutions. Their difference \(x_i\) has \(x_0=x_N=0\) and satisfies \(x_i=p x_{i+1}+q x_{i-1}\). If some \(x_i>0\), a positive maximum is attained at an interior state. Because \(p,q>0\), an average of the two neighboring values can equal that maximum only if both neighbors equal it. Repeating this implication reaches a boundary, contradicting its value \(0\). If some \(x_i<0\), apply the same argument to a negative minimum. Thus \(x_i=0\) for all \(i\), proving uniqueness. \(\square\)

Solving by Successive Differences

Instead of solving directly for all the \(t_i\), define the successive differences \(d_i=t_i-t_{i-1}\) for \(1\le i\le N\). This turns the second-order recurrence into a first-order recurrence. It also makes the boundary condition easy to enforce: because \(t_0=t_N=0\), the differences must sum to zero.

Proof. Substitute \(t_{i+1}=t_i+d_{i+1}\) and \(t_{i-1}=t_i-d_i\) into \(t_i=1+p\,t_{i+1}+q\,t_{i-1}\). Using \(p+q=1\), the right side becomes \(1+(p+q)t_i+p\,d_{i+1}-q\,d_i=1+t_i+p\,d_{i+1}-q\,d_i\). Subtracting \(t_i\) from both sides gives \(p\,d_{i+1}-q\,d_i=-1\). Also, \(\sum_{i=1}^N d_i=\sum_{i=1}^N(t_i-t_{i-1})=t_N-t_0=0\). Conversely, if the differences satisfy these equations and sum to zero, defining \(t_0=0\) and \(t_i=\sum_{j=1}^i d_j\) gives \(t_N=0\), and reversing the substitution gives every interior duration equation. The theorem’s uniqueness then identifies these values with the expected durations. \(\square\)

The method is particularly useful for exact arithmetic. Each step is linear, and the final sum determines the one initially unknown difference \(d_1\). The examples below show the full calculation, followed by checks in the original first-step equations.

Reading and Checking the Answer

The values \(t_i\) are expected numbers of plays, not probabilities. A value such as \(\tfrac{28}{13}\) is therefore meaningful even though a realized game lasts an integer number of plays: an expectation can be noninteger. In these examples, the starting state matters because the boundaries are at different distances, and the direction of the bias matters because it changes which boundary is reached more readily.

A practical check has three parts. First, verify the transition probabilities: every boundary row must sum to \(1\), and each interior row must sum to \(p+q=1\). Second, check the two boundary values \(t_0=t_N=0\). Third, substitute the calculated values into every interior recurrence, not just the recurrence at the starting state. Exact fractions make discrepancies visible instead of hiding them through rounding.

Common mistake: reversing the win and loss probabilities. In the last example, a mistaken first-step equation at state \(1\) might be written as \(t_1=1+\tfrac14t_2+\tfrac34t_0\). Substituting the calculated values into that incorrect equation gives \(1+\tfrac14\cdot\tfrac{20}{13}+\tfrac34\cdot0=\tfrac{18}{13}\), not \(t_1=\tfrac{28}{13}\). The transition description says a win, of probability \(\tfrac34\), takes state \(1\) to state \(2\); a loss, of probability \(\tfrac14\), takes it to state \(0\). The correct equation is \(t_1=1+\tfrac34t_2+\tfrac14t_0\), and its right side is \(1+\tfrac{15}{13}=\tfrac{28}{13}\). Always attach each probability to its destination before solving.

The recurrence calculation is not a substitute for checking the model. If either boundary were not absorbing, or if a play could change capital by more than one unit, the transition equations would differ. Here the finite state space, the absorbing boundary rows, and the two specified one-unit moves are exactly the conditions used in the calculations.