Fair Gambler's Ruin with Two Absorbing Barriers

The Fair Gambler’s Ruin Problem

A gambler starts with a finite amount of capital and plays a fair game, winning or losing one unit on each turn. Play ends when the capital reaches either a lower or an upper boundary. The key calculation is short once the stopping argument is justified: the capital process is a martingale, and at the stopping time its value must be one of the two boundaries. The important detail is that the exit time is usually finite almost surely but is not bounded by a fixed number of turns.

Fix an integer \(N\ge1\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \((\xi_n)_{n\ge1}\) be independent random variables with \(\mathbb{P}(\xi_n=1)=\mathbb{P}(\xi_n=-1)=\tfrac12\). The finite state space is \(S=\{0,1,\ldots,N\}\), and the time index is discrete, \(n\ge0\). For a fixed starting capital \(i\in S\), define the absorbed random walk \((X_n)\) by \(X_0=i\); if \(X_n\in\{0,N\}\), set \(X_{n+1}=X_n\), and otherwise set \(X_{n+1}=X_n+\xi_{n+1}\). Its filtration is \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). At an interior state \(j\), the transition probabilities to \(j-1\) and \(j+1\) are each \(\tfrac12\), so that row sums to \(\tfrac12+\tfrac12=1\); at either boundary the transition probability of staying there is \(1\), so that row also sums to \(1\).

The process \(X_n\) is a martingale with respect to \((\mathcal{F}_n)\): at an interior state its next increment has conditional mean \(\tfrac12(1)+\tfrac12(-1)=0\), and at a boundary its increment is zero. The stopping time \(T\) is a stopping time because \(\{T\le n\}=\bigcup_{m=0}^{n}\{X_m\in\{0,N\}\}\), an event determined by the observations through time \(n\).

Why Exit Occurs, but Not in a Fixed Number of Steps

For an interior starting state, a run of \(N\) consecutive losses forces the walk to reach \(0\) within those \(N\) turns. Such a run has probability \(2^{-N}\), regardless of the current interior capital. Independence of future turns therefore gives a uniform chance of exit in each block of \(N\) turns.

Proof. If \(i\) is a boundary state, then \(T=0\), and the inequality holds. Otherwise, for each block \(r=0,1,\ldots\), condition on the history through time \(rN\). On the event \(\{T>rN\}\), the walk is still in the interior. If the next \(N\) increments are all \(-1\), the walk reaches \(0\) during that block, since its current state is at most \(N-1\). This event has conditional probability \(2^{-N}\), by independence of the increments from \(\mathcal{F}_{rN}\). Thus \(\mathbb{P}_i(T>(r+1)N\mid\mathcal{F}_{rN})\le1-2^{-N}\) on \(\{T>rN\}\), and the conditional probability is zero on \(\{T\le rN\}\). Taking expectations gives \(\mathbb{P}_i(T>(r+1)N)\le(1-2^{-N})\mathbb{P}_i(T>rN)\). Iterating from \(\mathbb{P}_i(T>0)\le1\) proves the stated bound. Since \(0<1-2^{-N}<1\), the bound tends to zero as \(k\) tends to infinity. The events \(\{T>kN\}\) decrease to \(\{T=\infty\}\), so continuity of probability for decreasing events gives \(\mathbb{P}_i(T=\infty)=0\). \(\square\)

This result does not say that \(T\) has a deterministic upper bound. For example, with \(N=8\) and \(i=3\), the ten-turn sequence up, down, up, down, up, down, up, down, up, down keeps the walk alternating between \(3\) and \(4\), so \(T>10\) on that event. Its probability is \(2^{-10}>0\). The geometric tail proves almost-sure finiteness, not boundedness of the random variable \(T\).

The Ruin Probability from the Stopped Martingale

Proof. If \(i=0\), then \(T=0\), so the success probability is \(0=0/N\). If \(i=N\), then \(T=0\), so the success probability is \(1=N/N\). It remains to consider an interior initial state. For each integer \(n\ge0\), the stopped value \(X_{n\wedge T}\) lies in \([0,N]\). For \(k\ge0\), \(X_{(k+1)\wedge T}-X_{k\wedge T}=\mathbf{1}_{\{T>k\}}(X_{k+1}-X_k)\). The event \(\{T>k\}\) belongs to \(\mathcal{F}_k\); on this event the walk is in the interior and its next increment has conditional expectation zero. Hence \(\mathbb{E}_i[X_{(k+1)\wedge T}-X_{k\wedge T}]=0\). Summing these equalities for \(k=0,\ldots,n-1\) yields \(\mathbb{E}_i[X_{n\wedge T}]=i\).

By the lemma, \(T<\infty\) almost surely, so \(X_{n\wedge T}\to X_T\) almost surely as \(n\to\infty\). Also \(0\le X_{n\wedge T}\le N\), so the dominated convergence theorem applies and gives \(\mathbb{E}_i[X_T]=i\). At exit, \(X_T\) equals either \(0\) or \(N\). If \(q=\mathbb{P}_i(X_T=N)\), then \(\mathbb{E}_i[X_T]=0(1-q)+Nq=Nq\). Equating this with \(i\) gives \(q=i/N\); since exit occurs almost surely, the remaining probability is \(\mathbb{P}_i(X_T=0)=1-i/N\). \(\square\)

The proof does not apply the bounded-stopping-time theorem directly to \(T\): as the alternating path shows, \(T\) need not have a fixed finite upper bound. Instead, it first stops at \(T\wedge n\), establishes the expectation identity by summing conditional mean-zero increments, and then passes to the limit using the uniform bound \(0\le X_{n\wedge T}\le N\). This is the condition that makes the limiting argument valid.

Common Pitfall: Treating Almost-Sure Finiteness as Boundedness

A tempting but incorrect argument is: “The gambler must eventually hit a boundary, so \(T\le N\); therefore the bounded stopping-time result applies.” The first clause is true in the almost-sure sense established by the lemma, but it does not imply the claimed deterministic bound. For \(N=8\), \(i=3\), the ten-turn alternating sequence displayed above has probability \(2^{-10}=1/1024\) and gives \(T>10\). Thus even the particular claim \(T\le10\) fails with positive probability.

The correction is to keep the two facts distinct. The exit time is finite almost surely, while the stopped positions \(X_{n\wedge T}\) are bounded by \(N\) for every \(n\). The first fact identifies the almost-sure limit as \(X_T\); the second permits dominated convergence in the expectation calculation. Neither fact alone should be silently substituted for the other.

The formula is specific to a fair walk with unit steps and two finite barriers. It expresses a balance of expected capital at absorption, not a claim that the two outcomes are equally likely. For example, the starting point \(i\) determines the success probability \(i/N\), while the complementary probability is ruin. The next problem in this sequence changes the fairness assumption and uses a different martingale argument.