Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 36 ยท Markov Chains

First-Step Analysis and Gambler's Ruin

Solve expected hitting times and ruin probabilities with first-step analysis, derive the gambler's ruin formulas and verify them with linear algebra and simulation.

First-step analysis is the master technique for Markov chains. You condition on the first move, use the Markov property to say "from the new state, we start afresh", and get a system of linear equations. The classic example is the gambler's ruin: a gambler plays until reaching a goal or going broke. It models insurance risk, random fluctuations and countless "race to a boundary" problems.

Expected hitting times

Let A be a set of target states, and k_i the expected number of steps to reach A starting from i. First-step analysis gives

Text
k_i = 0                              if i is in A
k_i = 1 + ฮฃ_j p_ij k_j               otherwise

The 1 is the cost of the first step; then you are in state j and the rest is k_j. Written in matrix form for the non-target states, (I - Q) k = 1, where Q is P restricted to non-target states. This is the same N = (I - Q)^(-1) of the previous lesson.

Example: waiting for rain

In the weather chain (S, C, R) with rows S = (0.7, 0.2, 0.1), C = (0.3, 0.4, 0.3), R = (0.2, 0.3, 0.5), how long until the next rainy day? With target :

Text
k_S = 1 + 0.7 k_S + 0.2 k_C
k_C = 1 + 0.3 k_S + 0.4 k_C
Python Expected time to the next rainy day

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Gambler's ruin

A gambler starts with i dollars and bets one dollar per round. Each round is won with probability p and lost with probability q = 1 - p. The gambler stops on reaching N dollars (the goal) or 0 (ruin). The fortune is a Markov chain on 0, 1, ..., N with absorbing ends.

Let h_i be the probability of reaching N before 0 from i. First-step analysis gives

Text
h_i = p h_(i+1) + q h_(i-1)        for 0 < i < N,     h_0 = 0,  h_N = 1

Solving it

For the fair game (p = q = 1/2) the equation says h_(i+1) - h_i = h_i - h_(i-1): the differences are constant, so h is linear. With h_0 = 0 and h_N = 1:

Text
h_i = i / N

Your chance of winning is exactly your fraction of the goal.

For the unfair game, let r = q / p. The solution, found by writing h_(i+1) - h_i = r (h_i - h_(i-1)) and summing, is

Text
h_i = (1 - r^i) / (1 - r^N)            when p โ‰  1/2

The expected duration d_i (number of rounds) satisfies d_i = 1 + p d_(i+1) + q d_(i-1) with d_0 = d_N = 0. The solutions are

Text
fair game:   d_i = i (N - i)
unfair game: d_i = i / (q - p) - (N / (q - p)) ร— (1 - r^i) / (1 - r^N)
Python Gambler's ruin: formulas versus linear algebra

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two columns agree for every p. Look at the unfair games: for p = 0.45, even though each bet costs you only a small edge, your chance of reaching 10 dollars from 5 is well below one half.

The house always wins

When the game is slightly unfavorable (p < 1/2) and the goal is far away, the gambler is almost sure to be ruined. If the gambler plays forever with no upper goal (N โ†’ โˆž):

  • If p <= 1/2, ruin is certain (probability 1).
  • If p > 1/2, ruin has probability (q/p)^i < 1.
flowchart LR
    A["fair game<br/>h_i = i/N"] --> B["linear in starting fortune"]
    C["unfair game<br/>h_i = (1 - r^i)/(1 - r^N)"] --> D["exponentially tilted<br/>toward the house"]

Fair games favor nobody; unfair ones punish the player exponentially fast.

Simulation check

Python Simulate 20,000 gamblers starting with 5 dollars

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For p = 0.5, theory gives probability 0.5 and mean duration 5 ร— 5 = 25.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a fair gambler's ruin game with goal N, starting from i dollars, what is the probability of reaching N before 0?

    The harmonic equation forces h to be linear: h_i = i/N.
  2. 2. What is the expected duration of a fair gambler's ruin game from i with goal N?

    Solving d_i = 1 + (d_(i+1) + d_(i-1))/2 with d_0 = d_N = 0 gives d_i = i (N - i).
  3. 3. First-step analysis for expected hitting times gives which equation for a non-target state i?

    You pay one step, then continue from the next state j with expected remaining time k_j.
  4. 4. If the game is unfair against you (p < 1/2) and there is no upper goal, ruin is...

    With negative drift the fortune drifts to minus infinity, so it hits 0 with probability 1.

Summary

  • First-step analysis conditions on the first move and yields linear equations.
  • Expected hitting times solve k_i = 1 + ฮฃ p_ij k_j; hitting probabilities solve h_i = ฮฃ p_ij h_j.
  • Gambler's ruin: fair game h_i = i/N, d_i = i(N - i); unfair game h_i = (1 - r^i)/(1 - r^N) with r = q/p.
  • Linear algebra and simulation both confirm the formulas.

Next: Stationary Distributions