Mathematics for Computer Science

20.1. Gambler’s Ruin 847

For fixedpandT, letenbe the expected number of bets until the game ends
when the gambler’s initial capital isndollars. Since the game is over in zero steps
ifnD 0 orT, the boundary conditions this time aree 0 DeT D 0.
Otherwise, the gambler starts withndollars, where0 < n < T. Now by the
conditional expectation rule, the expected number of steps can be broken down
into the expected number of steps given the outcome of the first bet weighted by
the probability of that outcome. But after the gambler wins the first bet, his capital
isnC 1 , so he can expect to make anotherenC 1 bets. That is,

ExŒenjgambler wins first betçD 1 CenC 1 :

Similarly, after the gambler loses his first bet, he can expect to make anotheren 1
bets:
ExŒenjgambler loses first betçD 1 Cen 1 :

So we have

enDpExŒenjgambler wins first betçCqExŒenjgambler loses first betç

Dp.1CenC 1 /Cq.1Cen 1 /DpenC 1 Cqen 1 C1:

This yields the linear recurrence

enC 1 D

1

p

en

q

p

en 1 

1

p

: (20.10)

The routine solution of this linear recurrence yields:

Theorem 20.1.3.In the Gambler’s Ruin game with initial capitaln, targetT, and
probabilitypof winning each bet,

ExŒnumber of betsçD

8

ˆˆˆ

ˆˆˆ

ˆˆ

ˆ<

ˆˆˆ

ˆˆˆ

ˆˆˆ

:

n.Tn/ forpD

1

2

;

wn
Tn

pq

forp¤

1

2

wherewnD.rn1/=.rT1/

DPrŒthe gambler winsç:

(20.11)

In the unbiased case, (20.11) can be rephrased simply as

ExŒnumber of fair betsçDinitial capital
intended profit: (20.12)

For example, if the gambler starts with $10 dollars and plays until he is broke or
ahead $10, then 10
10 D 100 bets are required on average. If he starts with $500
and plays until he is broke or ahead $100, then the expected number of bets until
the game is over is 500  100 D50;000. This simple formula (20.12) cries out for
an intuitive proof, but we have not found one (where are you, Pascal?).