Mathematics for Computer Science

Chapter 19 Random Processes664

expectations of his payoffs of each bet, namely 0. Here we’re legitimately appeal-
ing to infinite linearity, since the payoff amounts remain bounded independent of
the number of bets.
When Albert wins all of Eric’s chips his total payoff gain is

PnCm

iDnC 1 r

i, and

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

Pn

iD 1 r

i. Lettingwnbe

Albert’s probability of winning, we now have

0 DExŒAlbert’s payoffçD

(^) nCm
X
iDnC 1
ri

!

wn

(^) n
X
iD 1
ri

!

.1wn/:

In the truly fair game whenr D 1 , we have 0 Dmwnn.1wn/, sown D
n=.nCm/, proving the claim 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

(19.1)

We have now proved

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

PrŒthe gambler is a winnerçD

8

ˆˆ

ˆ<

ˆˆˆ

:

n

T

forpD

1

2

;

rn 1

rT 1

forp¤

1

2

;

(19.2)

whererWWDq=p.

The expression (19.1) for the probability that the Gambler wins in the biased
game is a little hard to interpret. There is a simpler upper bound which is nearly
tight when the gambler’s starting capital is large and the game is biasedagainstthe
gambler. Thenr > 1, both the numerator and denominator in (19.1) are positive,
and the numerator is smaller. This implies that

wn<

rn

rT

DrnT

and gives: