Opening Random Walks
Random Walks
- Length
- 1 h 18 min
- Level
- Undergraduate
- Recorded
- MIT2012
Chapter 1 of 10: Before the lecture
Solves the gambler's ruin recurrence and shows why drift dooms a roulette player even at nearly even odds.
Random walks on a line model a gambler who bets until reaching a target or going broke, the gambler's ruin problem. In session 25 of MIT 6.042J, Leighton sets up a linear recurrence for the probability of winning and solves its characteristic equation. For a biased game the solution is exponential, and drift overwhelms random swings even at nearly even odds. A fair game gives a double root and a winning probability of ; an inhomogeneous recurrence then yields the expected number of bets, in the fair case. A proof by contradiction shows that playing a fair game forever ends in ruin with probability one. Assumes discrete probability and linear recurrences.
Random walks on a line model a gambler who bets until reaching a target or going broke, the gambler's ruin problem. In session 25 of MIT 6.042J, Leighton sets up a linear recurrence for the probability of winning and solves its characteristic equation. For a biased game the solution is exponential, and drift overwhelms random swings even at nearly even odds. A fair game gives a double root and a winning probability of ; an inhomogeneous recurrence then yields the expected number of bets, in the fair case. A proof by contradiction shows that playing a fair game forever ends in ruin with probability one. Assumes discrete probability and linear recurrences.
This lecture
Lecture 25 of 25 of Mathematics for Computer Science.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in