Mathematics for Computer Science

20.1. Gambler’s Ruin 843

20.1.2 A Recurrence for the Probability of Winning

Fortunately, you don’t need to be as ingenuious Pascal in order to handle Gambler’s
Ruin, because linear recurrences offer a methodical approach to the basic problems.
The probability that the gambler wins is a function of his initial capital,n, his
target,T n, and the probability,p, that he wins an individual one dollar bet.
For fixedpandT, letwnbe the gambler’s probability of winning when his initial
capital isndollars. For example,w 0 is the probability that the gambler will win
given that he starts off broke andwTis the probability he will win if he starts off
with his target amount, so clearly

w 0 D0; (20.3)

wTD1: (20.4)

Otherwise, the gambler starts withndollars, where0 < n < T. Now suppose
the gambler wins his first bet. In this case, he is left withnC 1 dollars and becomes
a winner with probabilitywnC 1. On the other hand, if he loses the first bet, he is
left withn 1 dollars and becomes a winner with probabilitywn 1. By the Total
Probability Rule, he wins with probabilitywnDpwnC 1 Cqwn 1. Solving for
wnC 1 we have

wnC 1 D

wn

p

rwn 1 (20.5)

whererisq=pas in Section 20.1.1.
This recurrence holds only fornC 1 T, but there’s no harm in using (20.5) to
definewnC 1 for allnC1 > 1. Now, letting

W.x/WWDw 0 Cw 1 xCw 2 x^2 C

be the generating function for thewn, we derive from (20.5) and (20.3) using our
generating function methods that

W.x/D

w 1 x

rx^2 x=pC 1

: (20.6)

But it’s easy to check that the denominator factors:

rx^2 

x

p

C 1 D.1x/.1rx/:

Now ifp¤q, then using partial fractions we conclude that

W.x/D

A

1 x

C

B

1 rx

; (20.7)