A gambler starts with a fixed amount of money ($i) and bets $1 in a fair game (i.e., the probability of winning or losing is 0.5) each time until she has 0 or n dollars. What is the probability she ends up with $0, and what chance does she get $n?
This is a perfect example of a Markov process. This is because the only thing relevant to the gambler at any point in time is the money she has at that time. Imagine her end goal is to reach 5. Let’s assume she has p chance to win a dollar and q = 1-p chance to lose the bet amount. The Markov chain representation is as follows.
Here is the translation matrix.
Take two cases: a fair bet (p = 0.5, q = 0.5) and a favourable bet (p = 0.6, q = 0.4). She starts with $3, represented as X = [0, 0, 0, 1, 0, 0]. Note that the first element represents 0, then 1, etc, and the sixth element denotes 5 (the goal). After 50 steps, the end state probability is,
P50 * X
P50 * [0, 0, 0, 1, 0, 0] = [0.4, 0, 0, 0, 0, 0.6]. The answer has to be the fourth column of P50. There is a 40% chance she ends up 0 and a 60% chance it’s 5$.
By the way, for p = 0.5, the analytical solution for the probability of reaching n, starting from i, is,
ai = i/n; a3 = 3/5 = 60%.
For p does not equal 0.5, it is,
ai = (1 – ri)/(1 – rn)
r = (1-p)/p
Now, imagine the probability of winning is 0.6.
p = 0.6; r = 0.4/0.6 = 0.67
a3 = (1 – r3)/(1 – r5) = 0.81
See the fourth column of the matrix above.
L26.9 Gambler’s Ruin: MIT OpenCourseWare
