Understanding Why We Assume P_i = r^i When Solving the Gambler’s Ruin Recurrence

When studying the Gambler’s Ruin problem, we often encounter the recurrence relation

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

where:

$P_i$ is the probability that a player eventually wins the game when starting with $i$ dollars.
$p$ is the probability of winning the next bet.
$q$ is the probability of losing the next bet.
$p + q = 1$ .

A natural question is: How do we solve this recurrence?

A Common First Attempt

Many students initially try a solution of the form

$P_i = i^r$

because powers of $i$ are familiar from algebra and calculus.

Substituting this into the recurrence gives

$i^r = p(i+1)^r + q(i-1)^r$

Unfortunately, this expression is difficult to simplify and does not lead to an easy way of determining the value of $r$ .

The Standard Approach

For linear recurrence relations with constant coefficients, we instead assume

$P_i = r^i$

where $r$ is an unknown constant.

This choice is powerful because shifting the index preserves the exponential form:

$P_{i+1}=r^{i+1}$

and

$P_{i-1}=r^{i-1}$

Substituting into the recurrence relation yields

$r^i = pr^{i+1} + qr^{i-1}$

Now divide every term by

$r^{i-1}$

to obtain

$r = pr^2 + q$

Rearranging gives

$pr^2-r+q=0$

This equation is called the characteristic equation of the recurrence.

Solving the Characteristic Equation

Factoring the quadratic,

latex(pr-q)=0[/latex]

we obtain two roots:

$r_1=1$

and

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

Therefore, the general solution of the recurrence is

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

where $A$ and $B$ are constants determined by the boundary conditions.

Why Does r^i Work So Well?

The key idea is that exponential functions behave nicely under index shifts.

For example,

$r^{i+1}=r\cdot r^i$

and

$r^{i-1}=\frac{1}{r}r^i$

This allows every term in the recurrence to be expressed in terms of the same quantity, making it possible to reduce the recurrence relation to an ordinary algebraic equation.

In contrast, using

$P_i=i^r$

produces terms such as

latex^r[/latex]

and

latex^r[/latex]

which do not simplify neatly.

Key Takeaway

Whenever you encounter a linear recurrence relation with constant coefficients such as

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

try a solution of the form

$P_i = r^i$

rather than

$P_i = i^r$

because exponential trial solutions transform the recurrence into a characteristic equation that can be solved using algebra.