Gambler’s Ruin, Recurrence Relations, and Why the General Solution Has Two Constants

Last Updated on June 19, 2026 by Statnzee Team

The Big Idea

While studying Probability Theory, you may encounter the famous Gambler’s Ruin Problem.

Imagine two gamblers repeatedly betting against each other. Each round:

Gambler A wins with probability p
Gambler A loses with probability q
$p + q = 1$

The game continues until one gambler loses all their money.

A natural question is:

What is the probability that Gambler A eventually wins?

To answer this, we define a sequence of probabilities and derive a recurrence relation.

Step 1: Define the Probability

Let

$P_i$

represent the probability that a gambler eventually wins if they currently have $i$ dollars.

After the next bet:

With probability $p$ , they move to state $i+1$
With probability $q$ , they move to state $i-1$

Therefore,

$P_i = pP_{i+1} + qP_{i-1}$

This is a second-order linear recurrence relation.

Step 2: Guess a Solution

A common technique for solving recurrence relations is to assume a solution of the form

$P_i = x^i$

Substituting into the recurrence gives

$x^i = px^{i+1} + qx^{i-1}$

Divide both sides by $x^{i-1}$ :

$x = px^2 + q$

Rearranging:

$px^2 - x + q = 0$

We now have a quadratic equation.

Step 3: Apply the Quadratic Formula

Using

$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

with

$a=p,\quad b=-1,\quad c=q$

gives

$x = \frac{1 \pm \sqrt{1-4pq}}{2p}$

Step 4: Simplify the Discriminant

Since

$p+q=1$

we have

$1-4pq</h1> <p>(p+q)^2-4pq$

which simplifies to

$p^2-2pq+q^2</h1> <p>(p-q)^2$

Therefore,

$\sqrt{1-4pq}=|p-q|$

Substituting:

$x=\frac{1\pm|p-q|}{2p}$

Step 5: Find the Two Roots

First Root

$x=\frac{1+(p-q)}{2p}$

Since

$1+p-q=(p+q)+p-q=2p$

we get

$x=1$

Second Root

$x=\frac{1-(p-q)}{2p}$

Using

$1-p+q=2q$

gives

$x=\frac{q}{p}$

Therefore the two roots are

$x_1=1,\qquad x_2=\frac{q}{p}$

Why Are There Two Solutions?

We have found two sequences that satisfy the recurrence relation:

Solution 1

$P_i = 1$

Solution 2

$P_i = \left(\frac{q}{p}\right)^i$

Both satisfy

$P_i = pP_{i+1}+qP_{i-1}$

Why Can We Add Them Together?

The recurrence relation is linear.

Suppose

$A_i$

and

$B_i$

are solutions.

Then

$A_i=pA_{i+1}+qA_{i-1}$

and

$B_i=pB_{i+1}+qB_{i-1}$

Multiplying by constants $C_1$ and $C_2$ and adding gives

$p(C_1A_{i+1}+C_2B_{i+1})+q(C_1A_{i-1}+C_2B_{i-1})$

Therefore,

$P_i=C_1A_i+C_2B_i$

is also a solution.

This property is called the Principle of Superposition.

The General Solution

Since the recurrence has two independent solutions,

$1$

and

$\left(\frac{q}{p}\right)^i$

the most general solution is

$P_i=A(1)^i+B\left(\frac{q}{p}\right)^i$

which simplifies to

$P_i=A+B\left(\frac{q}{p}\right)^i$

The constants $A$ and $B$ are determined using boundary conditions such as

$P_0=0$

and

$P_N=1$

What Area of Mathematics Is This?

This topic belongs primarily to Probability Theory and Stochastic Processes.

However, the solution uses tools from several mathematical disciplines:

Probability Theory

Gambler’s Ruin
Random Walks
Markov Chains

Algebra

Quadratic equations
Factoring and simplification

Difference Equations

Recurrence relations
Discrete mathematics

Linear Algebra Concepts

Linear combinations
Independent solutions

Difference Equations vs Differential Equations

Many students notice similarities with calculus.

A differential equation works with derivatives:

$y''+y=0$

A difference equation works with shifted terms:

$P_i=pP_{i+1}+qP_{i-1}$

Differential Equations	Difference Equations
Continuous variables	Discrete variables
Derivatives	Shifts
Calculus	Discrete Mathematics

In fact, recurrence relations are often called the discrete analogue of differential equations.

Key Takeaway

The Gambler’s Ruin problem is fundamentally a probability problem, but solving it requires a powerful technique from discrete mathematics:

Build a recurrence relation.
Guess a solution of the form $x^i$ .
Solve the characteristic equation.
Find the roots.
Combine independent solutions.
Apply boundary conditions.

The final form

$P_i=A+B\left(\frac{q}{p}\right)^i$

is the general solution from which the gambler’s probability of eventual success can be determined.

Discover more from Statnzee

Subscribe to get the latest posts sent to your email.

Search

Gambler’s Ruin, Recurrence Relations, and Why the General Solution Has Two Constants

The Big Idea

Step 1: Define the Probability

Step 2: Guess a Solution

Step 3: Apply the Quadratic Formula

Step 4: Simplify the Discriminant