Mathematics for Computer Science

Chapter 20 Random Walks842

same reasoning that every bet has fair worth. So, Albert’s expected worth at the
end of the game is the sum of the expectations of the worth of each bet, which is

0.^1
When Albert wins all of Eric’s chips his total gain is worth
nXCm

iDnC 1

ri;

and when he loses all his chips to Eric, his total loss is worth

Pn

iD 1 r

i. Lettingwn

be Albert’s probability of winning, we now have

0 DExŒworth of Albert’s payoffçDwn

nXCm

iDnC 1

ri.1wn/

Xn

iD 1

ri:

In the truly fair game whenr D 1 , we have 0 Dmwnn.1wn/, sown D
n=.nCm/, as claimed above.
In the biased game withr¤ 1 , we have

0 Dr

rnCmrn

r 1


wnr

rn 1

r 1


.1wn/:

Solving forwngives

wnD

rn 1

rnCm 1

D

rn 1

rT 1

(20.1)

We have now proved

Theorem 20.1.1.In the Gambler’s Ruin game with initial capital,n, target,T, and
probabilitypof winning each individual bet,

PrŒthe gambler winsçD

8

ˆˆ

ˆ<

ˆˆˆ

:

n

T

forpD

1

2

;

rn 1

rT 1

forp¤

1

2

;

(20.2)

whererWWDq=p.

(^1) Here we’re legitimately appealing to infinite linearity, since the payoff amounts remain bounded
independent of the number of bets.