First-Step Equations for Expected Game Duration

From the First Play to an Expected-Duration Equation

In a finite gambler’s ruin game, the player’s capital changes by one unit on each play until it reaches either zero or a fixed upper boundary. To find the expected number of plays before the game ends, one can condition on the result of the first play. That conditioning must account for the play just made, while treating a game that starts at either boundary as already finished.

Consider a probability space $(\Omega,\mathcal{F},\mathbb{P})$ supporting a discrete-time Markov chain $(X_n)_{n\ge0}$ with state space $S=\{0,1,\ldots,N\}$, where $N\ge2$. The state $X_n=i$ means the player has capital $i$ after $n$ plays. At each play in an interior state $i\in\{1,\ldots,N-1\}$, the capital increases by one with probability $p$ and decreases by one with probability $q=1-p$, where $0<p<1$. The states 0 and $N$ are absorbing: from either boundary the chain stays there. The filtration is $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. Write $\mathbb{P}_i$ and $\mathbb{E}_i$ for probability and expectation when $X_0=i$.

Definition: The absorption time, or game duration, is $T=\inf\{n\ge0:X_n\in\{0,N\}\}$, with $\inf\varnothing=\infty$. For each state $i$, let $t_i=\mathbb{E}_i[T]$, initially allowing the value $+\infty$. Since the game has ended if it starts at a boundary, $t_0=t_N=0$.

Before conditioning on the first play, it is useful to know that these expectations are finite. This follows from a uniform chance of absorption within a bounded number of plays.

Proposition: If $N\ge2$ and $0<p,q<1$ with $p+q=1$, then $\mathbb{E}_i[T]<\infty$ for every $i\in S$.

Proof. Starting from an interior state $i$, the path that takes $i$ consecutive losses reaches 0 in exactly $i$ plays. Its probability is $q^i$: each of those $i$ transitions is from an interior state to the state one unit lower, including the final transition from state 1 to state 0. Because $i\le N-1$ and $0<q<1$, $q^i\ge q^N>0$. Thus, from every interior state, the probability of absorption within the next $N$ plays is at least $q^N$. This argument uses a path that ends at absorption; it does not require loss transitions after the chain has reached 0.

Let $a=1-q^N$, so $0\le a<1$. By the Markov property, conditional on survival through $kN$ plays, the chain is in an interior state and the probability it survives for another $N$ plays is at most $a$. Therefore, for every integer $k\ge0$, $\mathbb{P}_i(T>kN)\le a^k$. For $n$ between $kN$ and $(k+1)N-1$, $\mathbb{P}_i(T>n)\le\mathbb{P}_i(T>kN)\le a^k$. The tail-sum identity for a nonnegative integer-valued random variable gives \[ \mathbb{E}_i[T]=\sum_{n\ge0}\mathbb{P}_i(T>n) \le N\sum_{k\ge0}a^k =\frac{N}{q^N}<\infty. \] At a boundary, $T=0$, so finiteness holds there as well. $\square$

The First-Step Recurrence

Theorem (First-step equations for expected game duration): Under the assumptions above, the expected durations satisfy $$ t_0=0,\qquad t_N=0,\qquad t_i=1+p\,t_{i+1}+q\,t_{i-1}\quad(1\le i\le N-1). $$

Proof. Fix an interior state $i$. The game cannot end before the first play, so that play contributes one unit of duration. After the play, the chain is at $i+1$ with probability $p$, or at $i-1$ with probability $q$. If the new state is a boundary, its remaining duration is zero by definition. If it is interior, the Markov property says that the conditional expected remaining duration, given the first-step state $j$, is $t_j$. Equivalently, conditioning on $X_1$ and adding the first play gives $$ \mathbb{E}_i[T]=1+\mathbb{E}_i[t_{X_1}] =1+p\,t_{i+1}+q\,t_{i-1}. $$ The expectations are finite by the proposition, so this conditioning and addition involve finite quantities. If the chain starts at 0 or $N$, then $T=0$, giving the boundary equations. $\square$

The boundary conditions are part of the system, not optional details. The recurrence applies only to interior states, where a play is made. At a boundary there is no further game to play, so the expected remaining duration is zero. In particular, one should not apply the interior equation at a boundary: doing so would count another play after the game has already ended.

The recurrence is a description of the expected durations; deriving it does not itself solve the system or establish uniqueness of its solution. Its immediate value is that it translates a question about the full future of the game into equations relating neighboring capital states. The examples below focus on setting up and checking those equations.

Worked Example: A Biased Game with Four Units of Capital as the Upper Boundary

Let $N=4$, with win probability $p=\tfrac23$ and loss probability $q=\tfrac13$. The state space is $S=\{0,1,2,3,4\}$. In the state order $0,1,2,3,4$, the transition matrix 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}. $$ The row sums are $1$ at state 0, $\tfrac13+\tfrac23=1$ at state 1, $\tfrac13+\tfrac23=1$ at state 2, $\tfrac13+\tfrac23=1$ at state 3, and $1$ at state 4.

Writing $t_i=\mathbb{E}_i[T]$, the boundary conditions are $t_0=t_4=0$. At state 1, a loss ends the game and a win takes the chain to state 2, so $$ t_1=1+\tfrac23t_2+\tfrac13t_0=1+\tfrac23t_2. $$ At state 2, either result leaves the chain in the interior, giving $$ t_2=1+\tfrac23t_3+\tfrac13t_1. $$ At state 3, a win ends the game and a loss takes the chain to state 2, so $$ t_3=1+\tfrac23t_4+\tfrac13t_2=1+\tfrac13t_2. $$ The $+1$ in each equation counts the play just made. Substituting the boundary values into the unsimplified equations recovers the displayed equations, which checks the endpoint terms.

Worked Example: A Fair Game with Three Units of Capital as the Upper Boundary

Let $N=3$ and $p=q=\tfrac12$, so $S=\{0,1,2,3\}$. In state order $0,1,2,3$, the transition matrix is $$ P= \begin{bmatrix} 1&0&0&0\\ \tfrac12&0&\tfrac12&0\\ 0&\tfrac12&0&\tfrac12\\ 0&0&0&1 \end{bmatrix}. $$ The row sums are $1$ at state 0, $\tfrac12+\tfrac12=1$ at state 1, $\tfrac12+\tfrac12=1$ at state 2, and $1$ at state 3.

The boundary durations are $t_0=t_3=0$. From state 1, the game ends on the first play if there is a loss, and otherwise continues from state 2. From state 2, it ends on the first play if there is a win, and otherwise continues from state 1. Thus $$ t_1=1+\tfrac12t_0+\tfrac12t_2=1+\tfrac12t_2,\qquad t_2=1+\tfrac12t_1+\tfrac12t_3=1+\tfrac12t_1. $$ For a direct check of the first equation, its two first-step cases contribute $1+\tfrac12(0)$ for a loss and $1+\tfrac12t_2$ for a win; weighting those cases gives $\tfrac12(1+0)+\tfrac12(1+t_2)=1+\tfrac12t_2$. The second equation follows by the same case calculation with the two neighboring states shown explicitly above.

Worked Example: A Game That Must End on Its First Play

Let $N=2$, $p=\tfrac13$, and $q=\tfrac23$. The only interior state is 1, and either a win or a loss moves directly to a boundary. In state order $0,1,2$, the transition matrix is $$ P= \begin{bmatrix} 1&0&0\\ \tfrac23&0&\tfrac13\\ 0&0&1 \end{bmatrix}. $$ Its row sums are $1$ at state 0, $\tfrac23+\tfrac13=1$ at state 1, and $1$ at state 2.

Here $t_0=t_2=0$. Applying the recurrence at state 1 gives $$ t_1=1+\tfrac13t_2+\tfrac23t_0 =1+\tfrac13(0)+\tfrac23(0)=1. $$ This is also checked directly: from state 1, the probability of ending after one play is $\tfrac13+\tfrac23=1$, so $T=1$ with probability 1 and $\mathbb{E}_1[T]=1$. The direct calculation agrees with the recurrence.

Why the One-Play Term and Boundaries Matter

A frequent error is to write $t_i=p\,t_{i+1}+q\,t_{i-1}$ and omit the initial 1. For the two-unit example, this incorrect equation would give $$ t_1=\tfrac13t_2+\tfrac23t_0=0, $$ because $t_0=t_2=0$. But the game makes one play from state 1, and in fact it ends after exactly one play. The corrected equation is $t_1=1+\tfrac13t_2+\tfrac23t_0=1$. The omitted term is not an adjustment to the transition probabilities; it counts the play taken before the chain reaches its next state.

Another way to check an equation is to inspect the cases. The first play occurs in every case, so each case’s duration is one plus the remaining duration from the new state. At a boundary, that remaining duration is zero. This case-by-case interpretation catches both a missing $+1$ and an incorrect boundary term.

The finiteness argument also depends on the game’s assumptions. In particular, both $p$ and $q$ are strictly positive. The lower bound $q^N>0$ would fail if $q=0$, and the uniform absorption argument as written would no longer apply. Within the stated finite, two-sided game, the recurrence is justified by finite expectations, and it records exactly the first play and the expected continuation.

Check Your Understanding

For each question, identify the relevant boundary conditions and verify any recurrence by substituting the stated transition probabilities.

For $N=4$, $p=\tfrac14$, and $q=\tfrac34$, write the first-step equation for $t_2$.
Why is $t_0=0$, rather than $t_0=1$, when $T$ is defined using $n\ge0$?
For a game with $N=3$, $p=q=\tfrac12$, compute the probability of absorption on the first play when the initial state is 1.
In the finite-expectation argument, starting from state $i$, what path gives probability $q^i$ of reaching 0, and within how many plays does it do so?
For $N=2$, $p=\tfrac25$, and $q=\tfrac35$, use the recurrence and boundary values to find $t_1$. Check the answer from the possible first-play outcomes.

First-Step Equations for Expected Game Duration

What You'll Learn