Waiting for HTHT

Idea. Run a fair casino. Because every bet is fair, the casino's expected profit at the stopping time is zero, so the expected number of tosses equals the expected total paid out at the end. That payout depends only on how the pattern overlaps with itself.

Step 1: the game. Before toss $n$, gambler $n$ arrives with 1 dollar and bets it on H. If she wins she has 2 dollars and bets it on T for the next toss, then 4 dollars on H, then 8 dollars on T. She leaves as soon as she loses. Each bet is fair.

Step 2: zero expected profit. The casino collects 1 dollar per toss and its net gain is a martingale. With $N$ the stopping time (it has finite mean), optional stopping gives $$\mathbb{E}[N]=\mathbb{E}[G],$$ where $G$ is the money held by the gamblers when $\text{HTHT}$ appears.

Step 3: the payout. At the moment $\text{HTHT}$ appears:

• the gambler who started at the first H of the pattern has won $4$ bets: 16 dollars;
• the gambler who started at the second H has won $2$ bets ($\text{HT}$): 4 dollars;
• the gamblers who started on a T have lost.

So $\mathbb{E}[N]=16+4=20$.

In general. $\mathbb{E}[N]=\sum 2^k$ over all $k$ such that the first $k$ letters of the pattern equal its last $k$ letters. For $\text{HHHH}$ this gives $2+4+8+16=30$; for $\text{HHTT}$, which has no overlap, just $16$.