Math Core

Many probability problems describe a process that could, in principle, go on forever: flip until a pattern appears, walk until you hit a wall, play until someone is two points ahead. You can't list all the outcomes, but you can describe where the process is right now with a small number of states and write one equation per state.

States and first-step analysis

A state records everything about the current situation that matters for the future. For "flip a coin until you see $HH$ ," the only thing that matters is whether the last flip was $H$ . So there are two live states, "start" (or last flip $T$ ) and "last flip $H$ ," plus the finished state.

First-step analysis

Let $x_s$ be the quantity you want (a probability or an expected count) starting from state $s$ . Look at one step of the process:

For a probability: $x_s = \sum_t P(s \to t)\, x_t$ , with $x = 1$ at winning states and $x = 0$ at losing states.
For an expected number of steps: $x_s = 1 + \sum_t P(s \to t)\, x_t$ , with $x = 0$ at finished states.

Solve the resulting system of linear equations.

The reason this works: after one step, the process "restarts" from the new state, and it has no memory of how it got there. So the future from state $t$ is worth $x_t$ , no matter what happened before.

Definition

Absorbing state

A state the process never leaves, such as "pattern found" or "player is broke." Probability problems ask which absorbing state you reach; expected value problems ask how long it takes to reach one.

Gambler's ruin

A player has $k$ dollars and repeatedly bets $1$ dollar, winning with probability $p$ and losing with probability $q = 1 - p$ , until reaching $0$ or $N$ . With $x_k$ the probability of reaching $N$ , first-step analysis gives $x_k = p x_{k+1} + q x_{k-1}$ , with $x_0 = 0$ and $x_N = 1$ . The solution is

$x_k = \frac{1 - r^k}{1 - r^N}, \qquad r = \frac{q}{p} \ (p \ne q), \qquad \text{and } x_k = \frac{k}{N} \text{ if } p = q.$

Patterns in coin flips

For waiting times of patterns, the states are "how much of the pattern have I matched so far?" The subtle part is what happens after a wrong flip: you may still have matched a shorter piece. For $HTH$ , if you have $HT$ and flip $T$ , you're back to nothing; but if you have $H$ and flip $H$ , you still have $H$ .

Common mistake

When a flip breaks a partial match, don't automatically drop back to the start. Ask what the longest ending of the flips so far is that is also a beginning of the pattern. Going back too far is the most common error in pattern problems.

Worked example: Waiting for HH

A fair coin is flipped until two heads in a row appear. Find the expected number of flips.

Let $a$ be the expected number of further flips from the start (or after a $T$ ) and $b$ the expected number after an $H$ .

$a = 1 + \tfrac{1}{2}b + \tfrac{1}{2}a, \qquad b = 1 + \tfrac{1}{2}\cdot 0 + \tfrac{1}{2}a.$

The first gives $a = 2 + b$ . Substituting, $b = 1 + \tfrac{1}{2}(2 + b)$ , so $b = 4$ and $a = 6$ .

Worked example: Gambler's ruin

A player starts with $1$ dollar and bets $1$ dollar at a time, winning each bet with probability $\dfrac{2}{3}$ . Play stops when the player has $0$ or $4$ dollars. What is the probability of reaching $4$ ?

Here $r = \dfrac{1/3}{2/3} = \dfrac{1}{2}$ , so $x_1 = \dfrac{1 - \frac{1}{2}}{1 - \frac{1}{16}} = \dfrac{1/2}{15/16} = \dfrac{8}{15}$ .

Check with equations: $x_1 = \tfrac{2}{3}x_2$ , $x_2 = \tfrac{2}{3}x_3 + \tfrac{1}{3}x_1$ , $x_3 = \tfrac{2}{3} + \tfrac{1}{3}x_2$ . Solving gives $x_1 = \dfrac{8}{15}$ .

Worked example: A pattern race

A fair coin is flipped until either $HT$ or $TT$ appears. What is the probability that $HT$ appears first?

Think about the first $H$ . Once any $H$ has appeared, the next $T$ completes $HT$ , and $TT$ can't happen before that (a $T$ right after an $H$ makes $HT$ , not $TT$ ). So $TT$ wins only if it appears before any $H$ , which means the first two flips are $TT$ . That has probability $\dfrac{1}{4}$ , so $HT$ wins with probability $\dfrac{3}{4}$ .

States would give the same answer, but look for this kind of shortcut first.

Tip

Symmetry cuts the number of states. On a cube, a bug's position only matters through its distance from the target ( $0$ , $1$ , $2$ , or $3$ edges), so eight vertices become four states.

Practice

Practice 1

A fair coin is flipped until the sequence $HHT$ appears for the first time. What is the expected number of flips?