The votes from Friday’s Simple Probability Puzzle are in. Here was the question:

Imagine there’s a completely random event with two outcomes, say flipping a coin. Each flip has an equal probability of landing heads or tails. Now imagine that we’re interested in seeing how long it takes to get a certain sequence of outcomes.
Pattern 1

Pattern 2

Now, suppose we flip a coin until Pattern 1 is reached, note how many coin flips it took, and then we repeat the process many times and average how many flips it takes to get a tails-heads-tails sequence . After that, we go through the same process to see how many flips it takes to get Pattern 2, a tails-heads-heads sequence.

On average, which pattern takes fewer coin tosses?

• They'll happen equally fast, on average. (78%, 1,775 Votes)
• I can't figure it out. (2%, 36 Votes)

Total Voters: 2,282

The results weren’t exactly stellar. As expected, the sucker answer of “They’ll happen equally fast, on average.” got the vast majority of the votes. The correct answer of “Tails, Heads, Heads takes fewer tosses!” drew less than ten percent of the total. Worse still, the people who chose “Tails, Heads, Heads takes fewer tosses!”, outnumbered those who admitted defeat more than five-to-one.

It wasn’t all bad, though! Some commenters not only arrived at the correct answer, but produced programs to prove it. The very first such comment was well-formatted LISP code. I have to say, it’s great to be getting feedback back of this level of geek-cred.

Some commenters produced a mathematical derivation of the average number of coin flips that it takes to get a tails-heads-heads sequence vs. a tails-heads-tails sequence. The problem is tricky, but it really is a simple problem. Once it’s properly framed, it’s a first year high school algebra problem– two linear equations to be solved for two unknowns. Here’s a basic walk-through of the process to find out how many flips it takes, on average to get THT:

``````First, let's define a few terms:
N[THT|TH] is the average flips to get THT once we already have TH
N[THT|T] is the average flips to get THT once we already have T
N[THT|] is the average flips to get THT, starting from scratch

The easiest term to find is N[THT|TH].  There's a 50% chance that
we'll get tails on the next flip.  In that case, the number of flips
to match the pattern is 1.  If we get heads on the next flip, then
the number of flips is 1 + N[THT|]. Therefore,

N[THT|TH] = .5(1) + .5(1 + N[THT|]), or
N[THT|TH] = 1 + N[THT|]/2

If we already have N[THT|T], then we have a 50% chance of
getting heads, which would mean the total flips would be that flip,
plus N[THT|TH], and a 50% chance of getting tails, which would
mean that flip plus N[THT|T].  Therefore,

N[THT|T] = .5(1 + N[THT|TH]) + .5(1 + N[THT|T])
N[THT|T] = 1 + N[THT|TH]/2 + N[THT|T]/2
N[THT|T]/2 = 1 + N[THT|TH]/2
N[THT|T] = 2 + N[THT|TH]

If we're starting from scratch, i.e. N[THT|], we have a 50% chance
of tails, which would give us that flip plus N[THT|T], and a 50%
one flip plus N[THT|].  Therefore,

N[THT|] = .5(1 + N[THT|T]) + .5(1 + N[THT|])
N[THT|] = 1 + N[THT|T]/2 + N[THT|]/2
N[THT|]/2 = 1 + N[THT|T]/2              (subtracting N[THT|]/2)
N[THT|] = 2 + N[THT|T]                  (multiplying each side by 2)

Now, we know that starting from scratch takes two more flips than
starting from T, or four more flips than starting from TH.  We plug
this back in.

N[THT|TH] = 1 + N[THT|]/2               (our first equation)
N[THT|] = 4 + 1 + N[THT|]/2             (substituting for N[THT|T]
N[THT|]/2 = 5                           (subtracting N[THT|]/2)
N[THT|] = 10

On average, it takes ten flips to get tails-heads-tails.
``````

After getting the general idea, it’s very quick to solve for how many flips it takes to get THH:

``````Here are the basic equations for N[THH|TH], N[THH|T], and N[THH|]:
N[THH|TH] = .5(1) + .5(1 + N[THH|T])
N[THH|T] = .5(1 + N[THH|TH]) + .5(1 + N[THH|T])
N[THH|] = .5(1 + N[THH|]) + .5(1 + N[THH|T])

Solving for N[THH|]:
N[THH|]/2 = 1 + N[THH|T]/2
N[THH|] = 2 + N[THH|T]

Solving for N[THH|T]
N[THH|T] = 1 + N[THH|TH]/2 + N[THH|T]/2
N[THH|T]/2 = 1 + N[THH|TH]/2
N[THH|T] = 2 + N[THH|TH]

Solving for N[THH|TH]
N[THH|TH] = 1 + N[THH|T]/2
N[THH|TH] = 1 + (2 + N[THH|TH])/2
N[THH|TH] = 2 + N[THH|TH]/2
N[THH|TH]/2 = 2
N[THH|TH] = 4

Plugging in and solving for N[THH|], we get:

N[THH|T] = 4 +2
N[THH|] = 4 + 2 + 2 = 8