Gambler’s Ruin on a Finite Interval

The finite-interval ruin problem

A nearest-neighbor walk on a finite interval has two absorbing endpoints. Starting between them, the walk eventually reaches one endpoint or the other. The central questions are: what is the probability that it reaches the upper endpoint first, and how long does it take on average to reach either endpoint?

The answers depend on the balance between upward and downward steps. In the symmetric case, the hitting probability is linear in the starting position and the expected duration is a quadratic function. A bias changes both formulas, but the problems still reduce to solving finite difference equations with boundary values.

Setup and definitions

Fix an integer \(N\ge 2\). Let \((X_n)_{n\ge 0}\) be a random walk on \(\{0,1,\ldots,N\}\). From any interior state \(i\in\{1,\ldots,N-1\}\), it moves to \(i+1\) with probability \(p\) and to \(i-1\) with probability \(q=1-p\), where \(0<p<1\). Both endpoints are absorbing: once the walk reaches 0 or \(N\), it stays there.

Definition: For a starting state \(i\), let \( \tau=\inf\{n\in\mathbb{N}_0:X_n\in\{0,N\}\} \) be the absorption time. Define \( h_i=\mathbb{P}_i(X_\tau=N) \), the probability of absorption at the upper endpoint, and \( m_i=\mathbb{E}_i[\tau] \), the expected time until absorption. Here \(\mathbb{P}_i\) and \(\mathbb{E}_i\) mean probability and expectation when \(X_0=i\).

At a boundary, absorption has already occurred. Thus \(h_0=0\), \(h_N=1\), and \(m_0=m_N=0\). We first check that \(\tau\) is finite with finite expectation, so that the expected durations and first-step equations used below are well-defined.

Proposition: If \(0<p<1\), then for every starting state \(i\), \(\mathbb{P}_i(\tau<\infty)=1\) and \(m_i<\infty\).

Proof. Put \(a=\min(p,q)>0\). From any interior state \(i\), the probability of taking \(i\) consecutive downward steps and reaching 0 within \(N\) steps is \(q^i\ge q^N\ge a^N\). Consequently, conditional on not yet being absorbed at the start of any block of \(N\) steps, the probability of remaining unabsorbed throughout the block is at most \(1-a^N\). Iterating this bound gives \[ \mathbb{P}_i(\tau>kN)\le (1-a^N)^k,\qquad k\in\mathbb{N}_0. \] The right-hand side tends to zero, so \(\mathbb{P}_i(\tau=\infty)=0\). Also, grouping the tail probabilities of \(\tau\) into blocks of \(N\) terms yields \[ \mathbb{E}_i[\tau] =\sum_{n=0}^{\infty}\mathbb{P}_i(\tau>n) \le N\sum_{k=0}^{\infty}(1-a^N)^k =\frac{N}{a^N}<\infty. \] Thus absorption occurs almost surely and has finite expected duration. \(\square\)

First-step equations

Starting at an interior state, the first step is either upward or downward. Conditioning on that step gives the hitting-probability recurrence \(h_i=p h_{i+1}+q h_{i-1}\). For the duration, one step is spent before the walk continues from its new state, giving \(m_i=1+p m_{i+1}+q m_{i-1}\). These equations apply for \(1\le i\le N-1\), together with the boundary values above.

\begin{aligned} h_i&=p h_{i+1}+q h_{i-1}, & h_0&=0,\quad h_N=1,\\ m_i&=1+p m_{i+1}+q m_{i-1}, & m_0&=0,\quad m_N=0. \end{aligned}

The additional \(1\) in the duration equation is essential: it counts the step just taken. Omitting it would instead give the harmonic equation, which describes a different quantity.

Hitting the upper endpoint first

The recurrence for \(h_i\) can be solved by examining the increments \(d_i=h_i-h_{i-1}\), \(1\le i\le N\). Rearranging the recurrence gives \(p(h_{i+1}-h_i)=q(h_i-h_{i-1})\), or \(d_{i+1}=(q/p)d_i\). The boundary values determine the overall constant.

Theorem: For \(1\le i\le N-1\), the probability of reaching \(N\) before 0 is \[ h_i= \begin{cases} \dfrac{i}{N}, & p=q=\dfrac12,\\[6pt] \dfrac{1-(q/p)^i}{1-(q/p)^N}, & p\ne q. \end{cases} \]

Proof. If \(p=q=1/2\), the increment relation gives \(d_{i+1}=d_i\), so all increments equal a constant \(c\). Since \(h_0=0\), summing the first \(i\) increments gives \(h_i=ic\). The condition \(h_N=1\) implies \(c=1/N\), hence \(h_i=i/N\). Now suppose \(p\ne q\), and set \(r=q/p\), so \(r>0\) and \(r\ne1\). The increment relation gives \(d_k=r^{k-1}d_1\). Therefore \[ h_i=\sum_{k=1}^{i}d_k =d_1\frac{1-r^i}{1-r}. \] Using \(h_N=1\) gives \(d_1(1-r^N)/(1-r)=1\). Since \(r\ne1\), the denominator \(1-r^N\) is nonzero, and substitution yields \(h_i=(1-r^i)/(1-r^N)\). The formulas satisfy both boundary values and the recurrence, which determine the solution uniquely: the difference of two solutions would have zero boundary values and, by the same increment calculation, would vanish everywhere. \(\square\)

Worked Example: A symmetric walk

Let \(N=8\), \(p=q=1/2\), and start at \(i=3\). By the symmetric formula, \[ h_3=\frac{3}{8}. \] Thus the walk is three times as likely to be absorbed at 0 as at 8: the respective probabilities are \(5/8\) and \(3/8\). These add to 1, as they must because absorption occurs almost surely.

Worked Example: A downward-biased walk

Take \(N=5\), \(p=2/5\), \(q=3/5\), and \(i=2\). Here \(r=q/p=3/2\), so \[ h_2=\frac{1-(3/2)^2}{1-(3/2)^5} =\frac{-5/4}{-211/32} =\frac{40}{211}. \] In particular, the probability of absorption at 0 is \(1-h_2=171/211\). The upward-hitting probability is below \(1/2\), consistent with the downward bias.

Expected time until absorption

The duration recurrence has a constant term, so its solution is not itself harmonic. In the symmetric case, a quadratic function provides the required one-step increase. In the biased case, a linear function provides that increase, and a multiple of the already-solved hitting probability supplies the boundary adjustment.

Theorem: For \(1\le i\le N-1\), the expected absorption time is \[ m_i= \begin{cases} i(N-i), & p=q=\dfrac12,\\[6pt] \dfrac{i-Nh_i}{q-p}, & p\ne q, \end{cases} \] where \(h_i\) is the upper-hitting probability given above.

Proof. First suppose \(p=q=1/2\), and define \(g_i=i(N-i)\), including \(g_0=g_N=0\). For an interior state, \[ \begin{aligned} 1+\frac12g_{i+1}+\frac12g_{i-1} &=1+\frac12\big((i+1)(N-i-1)+(i-1)(N-i+1)\big)\\ &=1+\frac12\big(2i(N-i)-2\big)\\ &=i(N-i)=g_i. \end{aligned} \] Thus \(g_i\) satisfies the duration recurrence and both boundary conditions. Now suppose \(p\ne q\). Let \(g_i=(i-Nh_i)/(q-p)\). Its boundary values are zero because \(h_0=0\) and \(h_N=1\). The function \(h\) is harmonic, so \(h_i-ph_{i+1}-qh_{i-1}=0\). For the linear function \(i\), direct calculation gives \[ i-p(i+1)-q(i-1)=q-p. \] It follows that \[ g_i-pg_{i+1}-qg_{i-1} =\frac{q-p}{q-p}=1, \] which is exactly the duration recurrence rearranged. Finally, the solution to this recurrence with zero boundary values is unique: the difference of two solutions is harmonic with zero boundary values, and the increment argument used for \(h_i\) shows that such a function is identically zero. Hence \(g_i=m_i\). \(\square\)

Worked Example: Mean duration in the symmetric case

For the symmetric walk on \(\{0,\ldots,8\}\) starting from 3, the expected absorption time is \[ m_3=3(8-3)=15. \] This is an expectation measured in individual steps, not a guarantee that absorption occurs exactly after 15 steps. The walk may stop sooner or later, but its mean stopping time over repeated runs is 15.

Worked Example: Mean duration in the biased case

Continue with \(N=5\), \(p=2/5\), \(q=3/5\), and \(i=2\). We have \(h_2=40/211\), so \[ m_2=\frac{2-5(40/211)}{1/5} =\frac{422-200}{211}\cdot 5 =\frac{1110}{211}. \] As a check, compute neighboring means from the same formula. Since \(h_1=16/211\) and \(h_3=76/211\), \[ m_1=\frac{1-5(16/211)}{1/5}=\frac{655}{211}, \qquad m_3=\frac{3-5(76/211)}{1/5}=\frac{1265}{211}. \] The first-step equation at state 2 is then verified directly: \[ 1+\frac25m_3+\frac35m_1 =1+\frac{2530+1965}{1055} =1+\frac{4495}{1055} =1+\frac{899}{211} =\frac{1110}{211} =m_2. \] The exact check illustrates how the probabilities weight the two possible next states; the factor \(1/5\) in the duration formula is \(q-p\), not \(p-q\).

Reading the formulas and avoiding pitfalls

The upper-hitting probability responds directly to the direction of the bias. If \(p>q\), then \(r=q/p<1\), and the formula gives a larger chance of reaching \(N\) than the symmetric walk gives from the same interior state. If \(p<q\), then \(r>1\), and that chance is smaller. The expected duration is not simply the distance to the nearer boundary: the walk can move away from the boundary, and the bias affects how often it does so.

A frequent source of errors is switching the meaning of \(p\) and \(q\). Here \(p\) always denotes the probability of a step upward, and \(q\) the probability of a step downward. With this convention, the ratio in the hitting formula is \(q/p\), and the denominator in the duration formula is \(q-p\). Checking the recurrence is a reliable way to catch a sign error.

The symmetric formulas also arise as limits of the biased formulas when \(p\) approaches \(1/2\), although direct substitution into the biased expressions gives a zero denominator. The separate symmetric cases are therefore important, not merely cosmetic. Finally, these results rely on the finite interval and on \(p,q>0\): the finite-state walk has a uniformly positive chance of absorption within a bounded number of steps. That argument is what justifies the expected-time calculation.

Check Your Understanding

Use the boundary equations and formulas to answer the following questions.

For a symmetric walk on \(\{0,\ldots,10\}\) starting at 4, what are the upper-hitting probability and expected absorption time?
For a biased walk, why must the ratio in the hitting-probability formula be \(q/p\) under the convention that \(p\) is the upward-step probability?
For \(N=5\), \(p=2/5\), and \(i=2\), what is the probability of absorption at 0?
Where does the constant \(1\) in the first-step equation for \(m_i\) come from?
Which part of the finite-interval assumption is used to establish finite expected absorption time?