Mathematics for Computer Science
Graph with probable transitions
MIT 6.042J/18.062J
4/7
1/6
1/6
1/7 2/7 3/5
Random Walks 5/9
4/9
2/3
2/5
Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.1 Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.2
Graph with probable transitions Random Walks
Questions Applications
• Pr{blue reaches orange before green}
• Finance – Stocks, options
• Pr{blue ever reaches orange}
• E[#steps blue to orange] • Algorithms – web search, clustering
• Average fraction of time at blue • Physics – Brownian Motion
Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.3 December 14, 2005
lec 15w.4
Copyright ©Albert R. Meyer, 2005.
1-Dimensional Walk Gambler’s Ruin
" " T
p
$$$
q
Gambler’s Ruin n
0
# of bets
December 14, 2005
lec 15w.5 December 14, 2005
lec 15w.6
Copyright ©Albert R. Meyer, 2005. Copyright ©Albert R. Meyer, 2005.
1
Gambler’s Ruin Gambler’s Ruin
Parameters: Three general cases:
n ::= initial capital (stake) • Biased against p < 1/2
T ::= gambler’s Target • Biased in favor p > 1/2
p ::= Pr{win $1 bet} • Unbiased (Fair) p = 1/2
q ::=1– p
m ::= intended profit = T – n
Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.7 Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.8
Fair Case: p = q = 1/2 Fair Case: p = q = 1/2
Let w ::= Pr{reach Target} Let w ::= Pr{reach Target}
E[$$] = w·(T – n) + (1 – w)·(–n)
= wT – n n
But game is fair, so E[$$ won] = 0 w=
n T
w=
December 14, 2005
T lec 15w.9
Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.10
Copyright ©Albert R. Meyer, 2005.
Fair Case Biased Against: p < 1/2 < q
Consequences
n=500, T=600 Betting red in US roulette
Pr{win $100} = 500/600 ≈ 0.83
n=1,000,000, T=1,000,100
p = 18/38 = 9/19 < 1/2
Pr{win $100} ≈ 0.9999
December 14, 2005
lec 15w.11 December 14, 2005
lec 15w.12
Copyright ©Albert R. Meyer, 2005. Copyright ©Albert R. Meyer, 2005.
2
Biased Against: p < 1/2 < q Biased Against: p < 1/2 < q
More amazing still!
Astonishing Fact!
Pr{win $100 starting with $1M}
Pr{win $100 starting with $500}
< 1/37,000
< 1/37,000 !
Pr{win $100 starting w/ any $n stake}
(was 5/6 in the unbiased case.)
< 1/37,000
Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.13 Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.14
Winning in the Unfair Case Winning in the Unfair Case
Team Problem: for p < q, for p < q: m
⎛ p⎞
⎜ ⎟
⎝q⎠
is exponentially decreasing in m,
where m ::= T−n = intended profit the intended profit.
December 14, 2005
lec 15w.18 December 14, 2005
lec 15w.19
Copyright ©Albert R. Meyer, 2005. Copyright ©Albert R. Meyer, 2005.
Losing in Roulette Losing in Roulette
p = 18/38, q = 20/38
Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.20 Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.21
3
Gambler’s Ruin Gambler’s Ruin
T T
T-n
$$$ $$$
n
0 0
# of bets # of bets
Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.22 Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.23
Fair Case Fair Case for T = ∞
Pr {lose starting with n | T = ∞}
pr {lose starting with $n}
≥ Pr{lose starting with n | T < ∞}
= pr{win starting with $(T - n)} T −n
= →∞ as T → ∞
T −n T
=
T So if the gambler keeps betting,
he is sure to go broke.
Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.24 December 14, 2005
lec 15w.25
Copyright ©Albert R. Meyer, 2005.
Return to the origin. How Many Bets?
If you start at the origin and
What is the expected number of
move left or right with equal
bets for the game to end?
probability, and keep moving in
– either by winning $(T-n) or
this way,
by going broke (losing $n).
Pr{return to origin} = 1
Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.26 Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.27
4
How Many Bets? Fair Case Fair Case for T = ∞
E[# bets] = n(T−n) = Likewise,
E[#bets for T = ∞]
(initial stake)⋅(intended profit) ≥ E[#bets for T < ∞]
proof by solving linear recurrence: = n(T-n) → ∞ (as T → ∞)
So the expected #bets to go broke is
en = p(1 + en+1) + q(1 + en-1)
infinite!
Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.30 Copyright ©Albert R. Meyer, 2005. December 14, 2005
lec 15w.31
Team Problems
Problems 1−3
December 14, 2005
lec 15w.32
Copyright ©Albert R. Meyer, 2005.
