Problem #98 HARD
The Coin Flip and the Gambler's Ruin
Paradox Probability Game Theory Limits
Problem Statement
A gambler plays a fair coin-flip game. He wins ₹1 on heads and loses ₹1 on tails. He starts with ₹10 and plays until he either reaches ₹100 (he walks away rich) or goes broke. What is the probability he reaches ₹100? Now suppose the coin is slightly unfair — tails has probability 0.51. How dramatically does this tiny bias change his odds of success?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
Fair coin: P(success) = 10/100 = 10%. With p=0.49 (1% house edge): P ≈ 0.87% — over 11 times worse. Formula: P = (1−(q/p)^k)/(1−(q/p)^N). Any house edge, no matter how small, makes eventual ruin almost certain with enough play.
WOW Moment:
- Fair coin, start ₹10, target ₹100: 10% chance of success.
- Change the coin so tails is 51% instead of 50%. Just ONE extra percent for the house. Success chance drops from 10% to under 1%.
- Start with ₹50 (halfway to the goal): fair coin gives 50%. With 51% tails: success drops to about 12%.
- Real casino roulette in India: house edge ≈ 2.7%. Starting with ₹1000, trying to reach ₹10000: Probability of success ≈ 0.000006%. Effectively zero.
- The mathematics of gambling is not 'you might get lucky.' It is: any tiny bias, compounded over enough bets, makes ruin mathematically certain. The house always wins — not sometimes. Always.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
The Gambler's Ruin is a classic problem in probability theory modeled as a random walk with absorbing barriers. It demonstrates how a seemingly negligible bias in favor of the house compounds over time to make the gambler's ruin almost certain.
The Mathematical Formulation:
Let the gambler start with capital k, and play until his capital reaches 0 (ruin) or N (success).
In each round:
- The gambler wins ₹1 with probability p.
- The gambler loses ₹1 with probability q = 1 - p.
Case 1: The Fair Coin (p = q = 0.5):
By the Optional Stopping Theorem for martingales, the expected value of the gambler's fortune remains constant.
E[Fortune_final] = E[Fortune_start]
P(success) × N + P(ruin) × 0 = k
P(success) × N = k => P(success) = k / N.
For k = 10 and N = 100:
P(success) = 10 / 100 = 10% (or 0.1).
Case 2: The Biased Coin (p ≠ 0.5):
The probability of success P(k) satisfies the recurrence relation:
P(k) = p * P(k+1) + q * P(k-1)
Solving this second-order linear difference equation with boundary conditions P(0) = 0 and P(N) = 1 yields:
P(success) = (1 - (q/p)^k) / (1 - (q/p)^N).
Let's plug in the biased coin values (p = 0.49, q = 0.51, k = 10, N = 100):
1. Ratio: q/p = 0.51 / 0.49 ≈ 1.040816.
2. (q/p)^10 ≈ 1.040816^10 ≈ 1.4929.
3. (q/p)^100 ≈ 1.040816^100 ≈ 56.38.
4. P(success) = (1 - 1.4929) / (1 - 56.38) = -0.4929 / -55.38 ≈ 0.0089 (or 0.89%).
To explain the WOW part:
- A mere 1% shift in favor of the house (from 50% to 51% tails) collapses the gambler's probability of reaching ₹100 from 10% to 0.89% — a decrease of more than 11 times!
- If the gambler starts with ₹50 (halfway to his goal):
- Fair coin: P(success) = 50 / 100 = 50%.
- Biased coin: P(success) = (1 - 1.040816^50) / (1 - 1.040816^100) = (1 - 7.509) / (1 - 56.38) ≈ -6.509 / -55.38 ≈ 11.75%.
- Why does this happen? The number of steps required to reach the boundary is large. As the random walk continues, the drift toward the lower barrier (ruin) dominates. The exponential term (q/p)^N grows extremely fast with N, making it nearly impossible to escape the downward drift. In a casino, the house edge (like 2.7% in single-zero roulette) acts as a mathematical guarantee of the player's eventual bankruptcy.