Gambler’s ruin win probability
Monotonic draws
Manual estimation of flips
Monotonic draws
Manual estimation of flips
Statistics
Medium
Seen in real interview
Assume you are playing a fair coin flip game. You start with $7. If you flip heads, you win one dollar, but if you get tails, you lose one dollar. You keep playing until you run out of money (have 0) or until you win 10 dollars. What is the probability that you win 10 dollars?
The process of flipping a coin can be seen as a random walk, with two endpoints: 0 or 10. At each step in the walk, there are two possible states we can move to next: win one more dollar, or lose one dollar. Since the coin is fair, there is a 50% chance to either win one dollar or lose one dollar. Similar to the “Buy and sell stocks” question, we can estimate the earnings expectation recursively:
\[ E_n = p (E_{n-1} + 1) + (1-p) \bigg(E_{n-1} - 1\bigg) = 0 \]
Since the expected earnings are zero, this means that on expectation, the player of our game will maintain their value at $7. Assume that \(E[V]\) is the expected value of the player, and hence \(E[V]=7\). Since there are only two final outcomes (lose everything or win $10) we can write the following:
\[ E[V] = 7 \Leftrightarrow p_{win} 10 + (1-p_{win}) 0 = 7 \Leftrightarrow p_{win} = 0.7 \]
where we estimated the probability of winning $10 to be 70%.
If you have doubts or you think this is counterintuitive, let’s simulate these random walks:
np.random.seed(1)
def random_walk():
total = 7
while True:
if total == 10:
return 1
elif total == 0:
return 0
total += np.random.choice([-1,1])
ans = []
for _ in range(1000):
ans.append(random_walk())
print(f"Probability of winning: {np.mean(ans):.1f}")## Probability of winning: 0.7
You can find more about the Gambler’s ruin problem here: https://en.wikipedia.org/wiki/Gambler%27s_ruin
Gambler ruin, Random walk, Expectation
- Monotonic draws Hard (Expectation)
- Covariance of dependent variables Medium (Variance, Uniform, Covariance, Expectation)
- Number of draws to get greater than 1 Medium (Normal, Geometric, CDF, Expectation)
- Dynamic coin flips Hard (Expectation, Simulation)
- Buy and sell stocks Medium (Gambler ruin, Expectation, Recursion, Random walk)
Thank you, we have received your feedback.