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

Tails, Heads, Tails
Pattern 2

Tails, Heads, Heads

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)
  • Tails, Heads, Tails takes fewer tosses! (11%, 258 Votes)
  • Tails, Heads, Heads takes fewer tosses! (9%, 213 Votes)
  • I can't figure it out. (2%, 36 Votes)

Total Voters: 2,282

Loading ... Loading ...

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%
chance of heads.  Since heads would be useless, that would mean
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

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

Even though the math involved is basic, it’s very easy to jump to the wrong conclusion. As one commenter mentioned, one of the brightest collections of people on the planet tanked on a logically equivalent question. Like me, the speaker of that video was also thinking about the long and ignoble history of experts bungling mathematics in courts. Our brains just aren’t really wired for mathematical abstraction.

Notes:
1) Only one vote per IP address was allowed, but the vote counts on this poll are just as unreliable as any other internet poll. I re-worded the poll options after about 150 votes had already been made, in order to make the question less ambiguous. People were also perfectly free to read all feedback from other visitors before voting.

2) This probability puzzle has a wide variety of applications, including in determining bankroll a successful gambler or investor will need, and in gene sequencing.

3) I’m in a sleep-deprived state as I post this. Please be gentle on any errors.