Mathematics for Computer Science

Chapter 20 Random Walks844

for some constantsA;B. To solve forA;B, note that by (20.6) and (20.7),

w 1 xDA.1rx/CB.1x/;

so lettingx D 1 , we getADw 1 =.1r/, and lettingx D1=r, we getB D
w 1 =.r1/. Therefore,

W.x/D

w 1

r 1



1

1 rx

1

1 x



;

which implies

wnDw 1

rn 1

r 1

: (20.8)

Finally, we can use (20.8) to solve forw 1 by lettingnDTto get

w 1 D

r 1

rT 1

:

Plugging this value ofw 1 into (20.8), we arrive at the solution:

wnD

rn 1

rT 1

;

matching Pascal’s result (20.1).
In the unbiased case wherepDq, we get from (20.6) that

W.x/D

w 1 x

.1x/^2

;

and again can use partial fractions to match Pascal’s result (20.2).

20.1.3 A simpler expression for the biased case

The expression (20.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 (20.1) are positive,
and the numerator is smaller. This implies that

wn<

rn

rT

D



1

r

Tn

and gives: