Learn / Library / Probability

Race of coin patterns

ProbabilityHard

A fair coin is tossed repeatedly and independently. Pattern $HTH$ and pattern $HHT$ are both watched in the sequence of results ( $H$ is heads, $T$ is tails), and overlaps with earlier tosses count. What is the probability that $HTH$ appears before $HHT$ ? Give a fraction in lowest terms.

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

Hint

Use states describing the useful suffix of the sequence so far: nothing, $H$ , $H T$ . Note that after $H H$ the pattern $HHT$ is certain to come first.

Solution

Let $s$ be the probability that $HTH$ comes first from the start state, $h$ from state $H$ , and $t$ from state $H T$ .
From $H H$ the pattern $HHT$ must win, because more heads keep us in $H H$ until a tails arrives; so from $H$ , a heads gives $0$ and a tails leads to $H T$ : $h = (\frac{1}{2}) \cdot 0 + (\frac{1}{2}) \cdot t$ .
From $H T$ , a heads completes $HTH$ and a tails returns to the start: $t = \frac{1}{2} + \frac{s}{2}$ .
From the start, a tails keeps us at the start and a heads leads to $H$ : $s = \frac{s}{2} + \frac{h}{2}$ .
Substituting, $h = \frac{1}{4} + \frac{s}{4}$ , so $s = \frac{s}{2} + \frac{1}{8} + \frac{s}{8}$ , which gives $\frac{3 s}{8} = \frac{1}{8}$ .
Therefore the probability is $\frac{1}{3}$ .

Answer: $\frac{1}{3}$

Next question Back to the library