Ruin Probabilities in a Biased Finite Game

The Finite Biased Game

A gambler starts with $i$ units and plays a game in which each round changes the fortune by exactly one unit. A win occurs with probability $p$, and a loss with probability $q=1-p$. The game ends when the fortune reaches $0$ or a fixed target $N$. The question here is the probability of reaching $N$ before $0$, not the expected length of the game. When the chance of winning differs from the chance of losing, this probability varies geometrically with the starting fortune.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space carrying the game, and let $(X_n)_{n\ge0}$ be the gambler’s fortune after $n$ rounds. Its state space is $S=\{0,1,\ldots,N\}$, where $N$ is a positive integer, and time is discrete. We use the natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. Assume first that $0<p<1$, so $q=1-p$ also lies strictly between zero and one. At an interior state $i$, the next state is $i+1$ with probability $p$ and $i-1$ with probability $q$; both boundary states are absorbing.

Definition: For $0\le i\le N$, let $h_i=\mathbb{P}_i(T_N<T_0)$, where $T_N=\inf\{n\ge0:X_n=N\}$ and $T_0=\inf\{n\ge0:X_n=0\}$. Thus $h_i$ is the probability of reaching the target before ruin when the initial fortune is $i$. At the boundary, $h_0=0$ and $h_N=1$.

For $1\le i\le N-1$, conditioning on the first round gives $h_i=p h_{i+1}+q h_{i-1}$. The two probabilities $p$ and $q$ are positive, and the two possible next states are $i+1$ and $i-1$. The boundary conditions are part of the problem: starting at $0$ means ruin has already occurred, while starting at $N$ means the target has already been reached.

Solving the Recurrence

Suppose $N\ge2$. Define the successive increments $d_i=h_i-h_{i-1}$ for $1\le i\le N$. Rearranging the recurrence shows that $p(h_{i+1}-h_i)=q(h_i-h_{i-1})$. Hence each increment is $q/p$ times the preceding one. This turns the second-order recurrence into a geometric sum.

Theorem: If $N\ge1$, $0<p,q<1$, and $p+q=1$, then for $0\le i\le N$, $$ h_i= \begin{cases} \dfrac{1-(q/p)^i}{1-(q/p)^N},&p\ne q,\\[6pt] \dfrac{i}{N},&p=q=\tfrac12. \end{cases} $$ For $i=0$ and $i=N$, these expressions give the boundary values $0$ and $1$, respectively.

Proof. When $N=1$, there are no interior states. The only possible initial fortunes are the boundaries, with $h_0=0$ and $h_1=1$; both formulas give those values. Now let $N\ge2$. For an interior state $i$, the recurrence is equivalent to $$ p(h_{i+1}-h_i)=q(h_i-h_{i-1}), $$ so $d_{i+1}=r d_i$, where $r=q/p>0$. Repeated application gives $d_k=r^{k-1}d_1$ for $1\le k\le N$. Since $h_0=0$, summing the increments yields $h_i=d_1\sum_{k=0}^{i-1}r^k$. The condition $h_N=1$ gives $d_1\sum_{k=0}^{N-1}r^k=1$. If $p\ne q$, then $r\ne1$, and the finite geometric sum is $(1-r^i)/(1-r)$; dividing the two sums gives $h_i=(1-r^i)/(1-r^N)$. If $p=q=\tfrac12$, then $r=1$, so the sums are $i$ and $N$, giving $h_i=i/N$.

It remains to verify that solving the recurrence determines the desired probabilities uniquely. This also explains why checking the recurrence and the two boundaries suffices. Suppose $u_i$ and $v_i$ are two solutions, and let $w_i=u_i-v_i$. Then $w_0=w_N=0$ and $w_i=pw_{i+1}+qw_{i-1}$ at each interior state. If $M=\max_{0\le i\le N}|w_i|>0$, this maximum occurs at an interior state $i$. The recurrence and the triangle inequality give $M=|w_i|\le p|w_{i+1}|+q|w_{i-1}|\le pM+qM=M$. Equality, with $p,q>0$, requires both neighboring absolute values to equal $M$; equality in the triangle inequality also requires their signs to agree with $w_i$. Repeating this argument along the states reaches a boundary, where $w_0=w_N=0$, contradicting $M>0$. Therefore $M=0$, so the solution is unique. The formula satisfies the recurrence by its increment relation and has the stated boundary values, so it is the probability $h_i$. $\square$

Worked Calculations

Worked Example: A Favorable Game

Let $N=4$, $p=\tfrac23$, and $q=\tfrac13$. Find the probability of reaching $4$ before $0$ from fortune $2$. 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$, $\tfrac13+\tfrac23=1$, $\tfrac13+\tfrac23=1$, $\tfrac13+\tfrac23=1$, and $1$, respectively, so this is a valid transition matrix.

Here $r=q/p=(\tfrac13)/(\tfrac23)=\tfrac12$. The formula gives $h_2=[1-(\tfrac12)^2]/[1-(\tfrac12)^4]=(\tfrac34)/(\tfrac{15}{16})=\tfrac45$. To check the calculation against the whole recurrence, the formula gives $h_0=0$, $h_1=\tfrac{8}{15}$, $h_2=\tfrac45$, $h_3=\tfrac{14}{15}$, and $h_4=1$. The interior equations are $$ \begin{aligned} \tfrac23 h_2+\tfrac13 h_0&=\tfrac23\cdot\tfrac45+\tfrac13\cdot0=\tfrac{8}{15}=h_1,\\ \tfrac23 h_3+\tfrac13 h_1&=\tfrac23\cdot\tfrac{14}{15}+\tfrac13\cdot\tfrac{8}{15} =\tfrac{28}{45}+\tfrac{8}{45}=\tfrac45=h_2,\\ \tfrac23 h_4+\tfrac13 h_2&=\tfrac23\cdot1+\tfrac13\cdot\tfrac45 =\tfrac{10}{15}+\tfrac{4}{15}=\tfrac{14}{15}=h_3. \end{aligned} $$ The starting fortune $2$ therefore has probability $\tfrac45$ of reaching the target first.

Worked Example: An Unfavorable Game

Keep $N=4$ and the starting fortune $i=2$, but take $p=\tfrac13$ and $q=\tfrac23$. In the same state order, the transition matrix is $$ P= \begin{bmatrix} 1&0&0&0&0\\ \tfrac23&0&\tfrac13&0&0\\ 0&\tfrac23&0&\tfrac13&0\\ 0&0&\tfrac23&0&\tfrac13\\ 0&0&0&0&1 \end{bmatrix}. $$ Its row sums are $1$, $\tfrac23+\tfrac13=1$, $\tfrac23+\tfrac13=1$, $\tfrac23+\tfrac13=1$, and $1$; every row is a probability distribution.

Now $r=q/p=(\tfrac23)/(\tfrac13)=2$, so $$ h_2=\frac{1-2^2}{1-2^4}=\frac{-3}{-15}=\frac15. $$ The formula gives $h_0=0$, $h_1=\tfrac1{15}$, $h_2=\tfrac15$, $h_3=\tfrac7{15}$, and $h_4=1$. Substitution checks every interior state: $$ \begin{aligned} \tfrac13 h_2+\tfrac23 h_0&=\tfrac13\cdot\tfrac15+\tfrac23\cdot0=\tfrac1{15}=h_1,\\ \tfrac13 h_3+\tfrac23 h_1&=\tfrac13\cdot\tfrac7{15}+\tfrac23\cdot\tfrac1{15} =\tfrac7{45}+\tfrac2{45}=\tfrac15=h_2,\\ \tfrac13 h_4+\tfrac23 h_2&=\tfrac13\cdot1+\tfrac23\cdot\tfrac15 =\tfrac5{15}+\tfrac2{15}=\tfrac7{15}=h_3. \end{aligned} $$ The lower success probability than in the first example is consistent with the lower chance of winning each round.

The Fair Limit

The formula for $p\ne q$ has a well-defined limit as the game becomes fair. For fixed $N$ and $i$, put $r=q/p$. If $p$ approaches $\tfrac12$ while $q=1-p$, then $r$ approaches $1$. Factoring $1-r^i$ and $1-r^N$ as finite geometric sums gives $$ \frac{1-r^i}{1-r^N} =\frac{1+r+\cdots+r^{i-1}}{1+r+\cdots+r^{N-1}} \longrightarrow \frac{i}{N}. $$ This argument includes $i=0$ and $i=N$: the sums have respectively zero terms in the numerator when $i=0$, or identical numerator and denominator when $i=N$. The limit is taken with $N$ and $i$ fixed. Without that condition, a limit need not exist: if $p=q=\tfrac12$, $i=1$, and $N$ alternates between $2$ and $3$, the probabilities alternate between $\tfrac12$ and $\tfrac13$.

Worked Example: Approaching a Fair Game

Take target $N=3$ and initial fortune $i=1$. For $0<p,q<1$, the probability is $$ h_1=\frac{1-r}{1-r^3}=\frac{1}{1+r+r^2},\qquad r=\frac{q}{p}, $$ where the second equality follows by factoring $1-r^3=(1-r)(1+r+r^2)$ when $r\ne1$. As $p$ approaches $\tfrac12$ with $q=1-p$, $r$ approaches $1$, and the expression tends to $1/(1+1+1)=\tfrac13$.

At the fair value itself, the state order $0,1,2,3$ gives $$ 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$, $\tfrac12+\tfrac12=1$, $\tfrac12+\tfrac12=1$, and $1$. The fair formula gives $h_0=0$, $h_1=\tfrac13$, $h_2=\tfrac23$, and $h_3=1$. Direct substitution confirms $\tfrac12h_2+\tfrac12h_0=\tfrac13=h_1$ and $\tfrac12h_3+\tfrac12h_1=\tfrac12+\tfrac16=\tfrac23=h_2$. The exact fair-game value agrees with the limit.

Boundary Cases and a Common Error

The formula with $q/p$ assumes $0<p,q<1$. If $p=0$, then $q=1$ and every interior path moves downward until it reaches $0$, so $h_i=0$ for $0\le i<N$, with $h_N=1$ by the boundary definition. If $q=0$, then $p=1$ and every interior path moves upward until it reaches $N$, so $h_i=1$ for $0<i\le N$, with $h_0=0$. These deterministic cases should be handled directly rather than by substituting into a formula that divides by $p$ or $q$. If $N=1$, there is no interior state, and the boundary values already give the answer.

Common mistake: using $p/q$ instead of $q/p$ as the geometric ratio. In the favorable example with $p=\tfrac23$, $q=\tfrac13$, $N=4$, and $i=2$, the incorrect ratio $p/q=2$ produces $(1-2^2)/(1-2^4)=\tfrac15$, rather than the correct $\tfrac45$. It fails the recurrence: that mistaken ratio gives $h_1=\tfrac1{15}$, $h_2=\tfrac15$, and $h_3=\tfrac7{15}$, but at state $2$ the required right-hand side is $\tfrac23\cdot\tfrac7{15}+\tfrac13\cdot\tfrac1{15}=\tfrac{15}{45}=\tfrac13$, not $\tfrac15$. The ratio comes from $p(h_{i+1}-h_i)=q(h_i-h_{i-1})$, so it is the downward probability divided by the upward probability.

The finite-game formula makes the effects of the starting fortune, the target, and the direction of the bias explicit. Its derivation depends on absorbing boundaries and one-step moves of size one; changing those rules changes the recurrence. For the stated game, the fair case is not a separate unexplained exception: it is exactly the continuous limit of the biased formula, and the recurrence confirms the value at fairness.

Check Your Understanding

Use the recurrence and boundary conditions to check each answer.

For $N=5$, $p=\tfrac34$, and $i=2$, write the geometric formula for $h_2$ and evaluate it exactly.
For $N=4$, $p=\tfrac14$, and $i=1$, calculate $h_1$. Does the direction of the bias agree with the size of this probability?
Starting from $p(h_{i+1}-h_i)=q(h_i-h_{i-1})$, identify the ratio between successive increments.
Explain why the fair limit $\tfrac{i}{N}$ is justified when $N$ and $i$ are fixed.
What are the success probabilities from interior states if $p=0$, and why should the geometric formula not be used directly?