Learn / Library / Probability

Waiting for a coin pattern

ProbabilityHard

A biased coin lands heads with probability $\frac{1}{3}$ and tails with probability $\frac{2}{3}$ , with independent flips. What is the expected number of flips until the pattern heads, tails, heads first appears in $3$ consecutive flips? Give a fraction a/b in lowest terms.

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Track the longest suffix of the flips that matches the start of the pattern: nothing, heads, or heads then tails.

Solution

Let $E 0$ , $E 1$ , $E 2$ be the expected further flips when the matched suffix is empty, heads, or heads then tails.
From empty: $E 0 = 1 + (\frac{1}{3}) E 1 + (\frac{2}{3}) E 0$ , so $E 0 = 3 + E 1$ .
From heads: a head keeps us there and a tail moves on, so $E 1 = 1 + (\frac{1}{3}) E 1 + (\frac{2}{3}) E 2$ , giving $E 1 = \frac{3}{2} + E 2$ .
From heads then tails: a head finishes, a tail resets, so $E 2 = 1 + (\frac{2}{3}) E 0$ .
Combining gives $E 0 = 3 + \frac{3}{2} + 1 + (\frac{2}{3}) E 0$ , so $\frac{E 0}{3} = \frac{11}{2}$ and $E 0 = \frac{33}{2}$ .

Answer: $\frac{33}{2}$

Next question Back to the library