As in the gambler’s ruin problem, two gamblers, A and B, make a series of bets, until one of the gamblers goes bankrupt. Let A start out with i dollars and B start out with N -i dollars, and let p be...

1 Gambler’s Ruin Problem
Consider a gambler who starts with an initial fortune of $1 and then on each successive gamble
either wins $1 or loses $1 independent of the past with probabilities p and q = 1−p respectively.
Let Rn denote the total fortune after the nth gamble. The gambler’s objective is to reach a total
fortune of $N , without first getting ruined (running out of money). If the gambler succeeds,
then the gambler is said to win the game. In any case, the gambler stops playing after winning
or getting ruined, whichever happens first. There is nothing special about starting with $1,
more generally the gambler starts with $i where 0 < i < N .
While the game proceeds, {Rn : n ≥ 0} forms a simple random walk
Rn = ∆1 + · · ·+ ∆n, R0 = i,
where {∆n} forms an i.i.d. sequence of r.v.s. distributed as P (∆ = 1) = p, P (∆ = −1) = q =
1− p, and represents the earnings on the succesive gambles.
Since the game stops when either Rn = 0 or Rn = N , let
τi = min{n ≥ 0 : Rn ∈ {0, N}|R0 = i},
denote the time at which the game stops when R0 = i. If Rτi = N , then the gambler wins, if
Rτi = 0, then the gambler is ruined.
Let Pi = P (Rτi = N) denote the probability that the gambler wins when R0 = i. Clearly
P0 = 0 and PN = 1 by definition, and we next proceed to compute Pi, 1 ≤ i ≤ N − 1.
The key idea is to condition on the outcome of the first gamble, ∆1 = 1 or ∆1 = −1, yielding
Pi = pPi+1 + qPi−1. (1)
The derivation of this recursion is as follows: If ∆1 = 1, then the gambler’s total fortune
increases to R1 = i+1 and so by the Markov property the gambler will now win with probability
Pi+1. Similarly, if ∆1 = −1, then the gambler’s fortune decreases to R1 = i − 1 and so
by the Markov property the gambler will now win with probability Pi−1. The probabilities
corresponding to the two outcomes are p and q yielding (1). Since p + q = 1, (1) can be
re-written as pPi + qPi = pPi+1 + qPi−1, yielding
Pi+1 − Pi =
q
p
(Pi − Pi−1).
In particular, P2 − P1 = (q/p)(P1 − P0) = (q/p)P1 (since P0 = 0), so that
P3 − P2 = (q/p)(P2 − P1) = (q/p)2P1, and more generally
Pi+1 − Pi = (
q
p
)
i
P1, 0 < i < N.
Thus
Pi+1 − P1 =
i∑
k=1
(Pk+1 − Pk)
=
i∑
k=1
(
q
p
)
k
P1,
1
yielding
Pi+1 = P1 +...