Mathematics for Computer Science

17.5. Linearity of Expectation 615

Proof.

ExŒR 1 
R 2 ç

D

X

r 2 range.R 1 
R 2 /

r
PrŒR 1 
R 2 Drç

D

X

ri 2 range.Ri/

r 1 r 2 
PrŒR 1 Dr 1 and R 2 Dr 2 ç

D

X

r 12 range.R 1 /

X

r 22 range.R 2 /

r 1 r 2 
PrŒR 1 Dr 1 andR 2 Dr 2 ç

D

X

r 12 range.R 1 /

X

r 22 range.R 2 /

r 1 r 2 
PrŒR 1 Dr 1 ç
PrŒR 2 Dr 2 ç

D

X

r 12 range.R 1 /

0

@r 1 PrŒR 1 Dr 1 ç

X

r 22 range.R 2 /

r 2 PrŒR 2 Dr 2 ç

1

A

D

X

r 12 range.R 1 /

r 1 PrŒR 1 Dr 1 ç
ExŒR 2 ç

DExŒR 2 ç

X

r 12 range.R 1 /

r 1 PrŒR 1 Dr 1 ç

DExŒR 2 ç
ExŒR 1 ç:



Problem 17.16.
A gambler bets $10 on “red” at a roulette table (the odds of red are 18/38 which
slightly less than even) to win $10. If he wins, he gets back twice the amount of his
bet and he quits. Otherwise, he doubles his previous bet and continues.

(a)What is the expected number of bets the gambler makes before he wins?

(b)What is his probability of winning?

(c)What is his expected final profit (amount won minus amount lost)?

(d)The fact that the gambler’s expected profit is positive, despite the fact that the
game is biased against him, is known as theSt. Petersberg paradox. The paradox
arises from an unrealistic, implicit assumption about the gambler’s money. Explain.

Hint:What is the expected size of his last bet?