A Simple Probability Puzzle

November 23rd, 2007 by Mark

Ever wonder why so many expert witnesses lead juries astray due to mathematical errors? Or why so many gamblers and investors are so bad at assessing relatively simple probability questions? First imagine that you consider yourself an expert (at something other than math), and then you encounter a question like this…

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. For example if we start flipping a coin for pattern 1 and we see:

tails, heads, heads, tails, heads, tails

Then we reached Pattern 1 after only six coin tosses. Sometimes it will take as few as three coin tosses, but other times it will take many more. If we were to repeat this test thousands of times and calculate the average number of tosses it takes to get Pattern 1 and compare it to the average number of tosses it takes to get Pattern 2, which be the bigger number?

On average, which pattern takes fewer coin tosses?

They’ll happen equally fast, on average. (78%)
Tails, Heads, Tails takes fewer tosses! (11%)
Tails, Heads, Heads takes fewer tosses! (9%)
I can’t figure it out. (2%)

Total Votes: 2,282

Loading …

The first correct answer with a valid explanation wins a beer (if you can make it to Taipei to collect).
Update: Two correct answers are in! Ray Myers, with some lisp code to brute force the answer, and Robin with a clear explanation of why. When and if you make it out to collect, drinks at the Taiwan Beer Factory are on me.

Tags: classic, fun, Geekery, math, puzzles, quiz

This entry was posted on Friday, November 23rd, 2007 at 5:19 am and is filed under Geekery. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

71 Responses to “A Simple Probability Puzzle”

1 Scott Says:
November 23rd, 2007 at 7:43 am
They’ll happen equally fast, and the probability of each one happening in only three coin tosses is 1/8, which is (1/2)^3.

We can also just look at it this way. After the second coin toss, assume you have already tossed Tails and Heads on your first two coin tosses. You then have an equal chance of getting either Tails or Heads on your third toss.
2 v Says:
November 23rd, 2007 at 11:15 am
total possible combinations: HTT,HHT,HHH,TTH,THH,HTH,THT,TTT= 8, so you have a one out of eight chance of getting one of the combinations. the chance of getting one (HTH) or the other (THH) is P(HTH) + P (THH) or 1/8 + 1/8 = 2/8 or 1/4. i don’t really know, i just got that formula from wikipedia.
3 Mark Says:
November 23rd, 2007 at 11:40 pm
For now, I’ll refrain from saying if anyone has a correct analysis. I don’t want to kill the thread pre-maturely.

This poll will end on Monday, as will the free beer offer if nobody wins it (or has won it) by that time.
4 James Says:
November 24th, 2007 at 12:37 am
I think V must have it right. Otherwise that Matt guy would have shown up and ripped the problem apart by now and probably presented a series of programs and statistical models too, like he did on the post about bluffing and game theory. Either that or he doesn’t drink beer.
5 Mark Says:
November 24th, 2007 at 5:03 am
That made me smile, James. I should email Matt and tell him his fame has spread on my little blog. I can assure you that everyone on the “old friends” part of my blogroll drinks.

Matt heads an IEEE group that publishes standards on encrypting data, though, and he’s consulting on the side, so he might be too busy to go after his old roommate’s beer. I’ve turned your comment into a hyper-link so people can see what post you’re talking about.
6 Sonia Says:
November 24th, 2007 at 5:14 am
Dammit, I’m late on the comment. Well, ditto what has already been said…There’s an equal change of either happening first. Good thing all my high school stats haven’t gone to waste.

And I can collect the beer! I’d rather have a Smirnoff Ice, though…
7 Sonia Says:
November 24th, 2007 at 5:15 am
equal *chance*, not change
8 nick Says:
November 24th, 2007 at 5:36 am
you guy WHAAATTT? consult IEEEEEE on WHAAATTT?

me name Serhey, i am from cracosia, one tos you get head or tail, no? second toss and you get head or tail RIGHT? by now you have HH, TT, HT or TH, next toss and you get either H or T, so if you already have TH then you either get THT or THH, right? you tossed 3 times every one 1/2 chanace? so 0.5 of 0.5 of 0.5 is 0.125 ? thats 1/8

me onlhy have 8 klas grammar school, maybe me too can consult IEEEEE, what? or i am not good enough for you?

regds kids, serhyei
9 Paul W. Homer Says:
November 24th, 2007 at 6:09 am
The correct mathematical answer — so I am told — is that all of the events are independent so the probably is identical.

However, it is far more fun to go with the ‘correct wacky’ answer: heads has more metal which unbalances the coin causing a bias. This causes THH to occur first, more often than not (I away bet heads just in case). Why settle for math, when intuition is far more entertaining
10 Michael Davies Says:
November 24th, 2007 at 6:14 am
I’m pretty sure it’s evens in the exercise as stated, as Scott said. But if you were asking the odds for one of two different triplets appearing first in a given sequence then the answer is more complex — eg TTH will on average appear before THT in a given sequence.
11 Ray Myers Says:
November 24th, 2007 at 6:36 am
The subtlety of this problem has to do with the way subsequences overlap with themselves over time. While all sequences of 3 flips have the same chance of occuring immediately (in the first 3), they can have a different chance of of happening first in a longer chain. I’ll leave a fuller statistical explaination to someone more eloquent. Here’s some Lisp code.
```
(defun flip ()
  (if (= (random 2) 0) 'heads 'tails))

(defun flips-needed-average (x y z trials)
  (float (/ (loop for i from 1 to trials sum
                  (flips-needed x y z)) trials)))

(defun flips-needed-helper (x y z f1 f2 f3 count)
  (if (and (eq x f1)
           (eq y f2)
           (eq z f3)) count
    (flips-needed-helper x y z
                         (flip) f1 f2 (1+ count))))

(defun flips-needed (x y z)
  (flips-needed-helper x y z (flip) (flip) (flip) 1))
```
So, running 10,000 trials on each:

* (flips-needed-average ‘tails ‘heads ‘heads 10000)
5.9696

* (flips-needed-average ‘tails ‘heads ‘tails 10000)
7.8799

I surmise that on average, pattern two — Tails, Heads, Heads — will appear first on average.
12 Ray Myers Says:
November 24th, 2007 at 6:44 am
I think I just said “on average” twice in the same sentence, whoops.

Also, it would make more sense to change the recursive call like so:
```
(defun flips-needed-helper (x y z f1 f2 f3 count)
  (if (and (eq x f1)
           (eq y f2)
           (eq z f3)) count
    (flips-needed-helper x y z
                         f2 f3 (flip) (1+ count))))
```
This does not change the answer.
13 Naruwan Says:
November 24th, 2007 at 7:16 am
I guess the “theory” behind the answer is that every time you toss the coin the odds are the same no matter what has gone before. There’s a connection here to China Airlines believe it or not. Every time CAL has an incident some passengers who are about to take a flight with CAL say they feel completely safe because they figure what are the odds of having two crashes in a row? Of course, as we know, the odds are exactly the same - theoretically speaking!
14 Robin Says:
November 24th, 2007 at 7:22 am
Maybe it’s THH which will have a lower average number of tosses. Here are my thoughts:

Let’s presume that the currently matching sequence is TH.

If we are looking for pattern 1 and the next toss is T, we have found it. If it’s H, we have to start over and our current match is empty.

If we are looking for pattern 2 and the next toss is H, we have found it. If it’s T, we have to start over but our current match is already T, not empty.

Does this make any sense?
15 K Says:
November 24th, 2007 at 7:34 am
As far as I can remember from school (sometime in the previous century), every combination has the same chance.
16 Mark Says:
November 24th, 2007 at 7:54 am
Well, I’d hoped to leave this open a bit longer, but Ray has thoroughly beaten the problem.

Most commenters were thinking along the right lines, in any sequence there are an equal number of THH and THT matches, but THT matches can overlap with each other. The sequence THTHT matches twice in only five coin tosses. THH sequences are spread out more and thus take less time, on average, to find. Robin’s explanation was excellent:

Regardless of which pattern we want to match, TH is the two-flip start we need. Obviously, if the third flip is what we want, the search is over. Where we see a difference is when we don’t get the flip we want.

If we’re searching for THT and the third flip is H, then we have THH and have to start over. If we’re searching for THH and the third flip is T, we have THT and we’re already 1/3 of the way to finding our sequence.
17 What is? Says:
November 24th, 2007 at 8:46 am
1/2 * 1/2 * 1/2 = 1/8 for Tails, Heads, Tails
1/2 * 1/2 * 1/2 = 1/8 for Tails, Heads, Heads

Same probability!
18 David Curran Says:
November 24th, 2007 at 9:01 am
This video explains why these mistakes happen. You question is so similar to the explanation i reckon you have already seen it.
Peter Donnelly: How juries are fooled by statistics
http://www.ted.com/index.php/talks/view/id/67
19 Peter Bromberg Says:
November 24th, 2007 at 10:17 am
It really depends on whether it is humans tossing actual coins or whether we are doing a mathematical simulation. There is a very big difference: even though humans are largely unpredictable coin flippers, there’s still a bias built in: If a coin starts out heads, it ends up heads when caught more often than it does tails.
Otherwise, each toss of the coin (mathematical toss, that is) has exactly the same odds. It doesn’t matter one bit what the “pattern” is. See my link.

20 Fred A. Says:
November 24th, 2007 at 2:37 pm

A suggestion for Ray’s solution.


(defun flips-needed (x y z)
  (flips-needed-helper x y z (flip) (flip) (flip) 3))

21 Sam Says:
November 24th, 2007 at 2:37 pm
The trouble with this poll is the options. All of the options are wrong, if you ask me.

It’s true that THH’s expected number of flips is going to be smaller. However, that doesn’t mean we’re more likely to see THH first than THT. The probability of seeing THH before THT in any given coin flip sequence is exactly one half. That’s not the question you asked (you asked for the smaller mean number of flips), but two of the poll options seems to refer to that question.

The options are:

> They’ll happen equally fast, on average. (79%)

Wrong because THH happens faster, on average.

> We’ll see Tails, Heads, Tails first! (11%)

Wrong because we’ll see THT first with equal probability as we see THH first, in any given sequence.

> We’ll see Tails, Heads, Heads first! (8%)

Wrong because we’ll see THH first with equal probability as THT, in any given sequence.

The latter two options were not worded in a way that gives hem the meaning you intended.
22 William Says:
November 24th, 2007 at 2:38 pm
coin flipping see hth first or thh first? stat.

the average of seeing heads or tails is 50% each time. the odds of seeing any arrangement at all narrows by 50% each flip. the odds of seeing h1000 is just a likely as any other arrangement of 1000 heads or tails flips. it is merely at one end of a bell curve of sides organization which is unrelated to unique probability.

ǜ
23 Sam Says:
November 24th, 2007 at 3:09 pm
Also, to compute the exact expected number of flips we’ll have to wait:

Let E[|] equal the expected number of extra flips until we get given that we already have the prefix of that sequence in our hands.

Then:
E[THH|TH] = 0.5 * 1 + 0.5 * (1 + E[THH|T])
E[THH|T] = 0.5 * (1 + E[THH|TH]) + 0.5 * (1 + E[THH|T])
E[THH|] = 0.5 * (1 + E[THH|T]) + 0.5 * (1 + E[THH|])

This is a cute system to solve. Simplifying each line..
E[THH|TH] = 1 + 0.5 * E[THH|T]
0.5 * E[THH|T] = 1 + 0.5 * E[THH|TH]
0.5 * E[THH|] = 1 + 0.5 * E[THH|T]

E[THH|TH] = 1 + 0.5 * E[THH|T]
E[THH|T] = 2 + E[THH|TH]
E[THH|] = 2 + E[THH|T]

E[THH|T] = 2 + (1 + 0.5 * E[THH|T])
E[THH|] = 2 + E[THH|T]

0.5 * E[THH|T] = 3
E[THH|] = 2 + E[THH|T]
E[THH|] = 8

So the expected number of coin flips before reaching the sequence THH is exactly 8. And for THT…

E[THT|TH] = 0.5 * 1 + 0.5 * (1 + E[THT|])
E[THT|T] = 0.5 * (1 + E[THT|TH]) + 0.5 * (1 + E[THT|T])
E[THT|] = 0.5 * (1 + E[THT|T]) + 0.5 * (1 + E[THT|])

E[THT|TH] = 1 + 0.5 * E[THT|]
E[THT|T] = 1 + 0.5 * E[THT|TH] + 0.5 * E[THT|T]
E[THT|] = 1 + 0.5 * E[THT|T] + 0.5 * E[THT|]

E[THT|TH] = 1 + 0.5 * E[THT|]
0.5 * E[THT|T] = 1 + 0.5 * E[THT|TH]
0.5 * E[THT|] = 1 + 0.5 * E[THT|T]

E[THT|TH] = 1 + 0.5 * E[THT|]
0.5 * E[THT|] = 2 + 0.5 * E[THT|TH]

E[THT|TH] = 1 + 0.5 * E[THT|]
E[THT|] = 4 + E[THT|TH]

E[THT|] = 5 + 0.5 * E[THT|]

E[THT|] = 10

So the expected number of flips before having gotten THT is 10.

Ray Myer’s code should have started counting at 3 instead of 1.

24 Иван Says:
November 24th, 2007 at 3:35 pm

On average:
(’t', ‘h’, ‘t’) 10.02259
(’t', ‘h’, ‘h’) 8.00463


import psyco
psyco.full()
import random

coin = lambda: ['t','h'][random.randint(0,1)]

def test(p):        
    s=0.0
    n = 100000
    for k in range(n):
        c = (coin(),coin(),coin())
        k = 3
        while True:
            if p == c: 
                break
            c = ( c[1], c[2], coin() )
            k += 1
        s += k
    return s/n
    
p1,p2= ('t','h','t'), ('t','h','h')
    
for p in (p1,p2):
    print p, test(p)

25 Oatmeat Says:
November 24th, 2007 at 3:52 pm
Here’s a mathematical derivation of the expected waiting times for THT and THH.

Pattern: THT

We can think of a transition system with four states labelled: null, T, TH, and THT. Each state denotes the Hs and Ts we have seen lately which align with our pattern. Thus for example if we see the sequence TTHHT we would have the following state transitions,

Input: State: null
Input: T State: T
Input: TT State: T
Input: TTH State: TH
Input: TTHH State: null
Input: TTHHT State: T

Now let x be the expected time to reach state THT from state null. This is the quantity we are interested in. To help us compute this, let y be the expected time to reach state THT from state T and let z be the expected time to reach state THT from state TH. Then we can derive the following equation

x = 1 + (1/2)x + (1/2)y

Explanation: x is the expected number of steps to reach state THT from state null. How do we reach state THT from state null? First we take one step (thus the +1) then we are either in state null again or state T. More specifically, with probability 1/2 we read a H thus putting us in state null again where we have to take on average x more steps to reach state THT. With probability 1/2 we read a T thus putting us in state T from which we have to take on average y more steps to reach state THT.

By similar reasoning starting from state T (from which we can read a T to end up in T again or read an H to end up in TH) we have,

y = 1 + (1/2)y + (1/2)z

Finally, from state TH we can either read an H, in which case we move to state null, or we can read a T in which case we are done. Thus we have

z = 1 + (1/2)x

To summarize, we have

x = 1 + (1/2)x + (1/2)y
y = 1 + (1/2)y + (1/2)z
z = 1 + (1/2)x

Which has the solution x = 10, y = 8, z = 6. Thus we expect to need 10 flips to see the pattern THT.

Pattern: THH

As others have pointed out, the key difference here is that from the state TH if we read a T (thus missing our goal) we will go to state T rather than starting over at null. Using the same idea as before we can derive the equations

x = 1 + (1/2)x + (1/2)y
y = 1 + (1/2)y + (1/2)x
z = 1 + (1/2)y

To reiterate, the difference between this and the last case is in the final equation which has y instead of x on the right (since we go back to state T instead of state null). The solution to this system of equations is x = 8, y = 6, z = 4. Thus we expect to need 8 flips to see the pattern THH.

If you want to read more, this coin flipping exercise is an example of a Markov Chain, i.e. the future state of the system depends only on the current state and not on history of how we got to the current state.
26 Oatmeat Says:
November 24th, 2007 at 3:56 pm
Ray Myers: It appears your code is off by 2. In the line

(defun flips-needed (x y z)
(flips-needed-helper x y z (flip) (flip) (flip) 1))

You are doing three flips here thus your counter should start at 3 instead of 1. As the original post states, “For example if we start flipping a coin and we see:

heads, heads, tails, heads, heads

Then we reached Pattern 2 after only five coin tosses.”

27 Ryan Says:
November 24th, 2007 at 3:57 pm

It is late and I am tired but I’m posting some haskell code. I used the SAME coin toss list for both patterns. I ended up getting the SAME probabilities. Maybe i have a bug in my code (it is very late) but i am posting it anyways.

output:
Exp1: 799185
Exp2: 799741


import System.Random

data Coin = H | T deriving (Enum,Show,Eq)

genFlips::Int->[Coin]
genFlips seed = map toEnum (randomRs (0,1) (mkStdGen seed))

experiment::(Coin,Coin,Coin)->[Coin]->Int->Int
experiment (a,b,c) flips count = if (a == flips!!0 && b == flips!!1 && c == flips!!2) then
					count
				 else
					experiment (a,b,c) (tail flips) (count+1)

runExp::(Coin,Coin,Coin)->[Coin]->Int->Int
runExp _ _ 0 = 0
runExp pattern flips samples = count + (runExp pattern (drop count flips) (samples-1)) where
				 count = experiment pattern flips 1

numTrials::Int
numTrials = 10^5

main::IO()
main = do
	let flips = genFlips 42 --use same list for both patterns
	let exp1 = (runExp (T,H,T) flips numTrials)
	let exp2 = (runExp (T,H,H) flips numTrials)
	putStrLn $ "Exp1: " ++ (show exp1)
	putStrLn $ "Exp2: " ++ (show exp2)

28 Ryan Says:
November 24th, 2007 at 4:07 pm
Update for my post above.

I found that for low number of trials i get a bigger difference. It converges to equality as i increase. I should really work out the theory but my mind is mush right now. Time for sleep!

Exp1: 68
Exp2: 40

Exp1: 119
Exp2: 65

Exp1: 914
Exp2: 735

Exp1: 8128
Exp2: 7868
29 Gordon Says:
November 24th, 2007 at 4:32 pm
If I can complicate matters a bit… The original question was asked in two slightly different ways, and we’ve only correctly answered one of them. The collective answer so far applies to the question of which pattern occurs, on average, after the smaller number of flips. But the actual survey question was “On average, which will we see sooner?“, and the answer to that is that each has an equal chance of occurring first. The reason is that the trial will end exactly one flip after the first occurrence of TH, and at that point the probability of H and T are equal. I modified Ray’s Lisp code a bit to demonstrate this:
```
(defun flip ()
  (if (= (random 2) 0) 'heads 'tails))

(defun flips-first-percentage (a b trials)
  (float (/ (loop for i from 1 to trials sum
    (flips-first a b)) trials)))

(defun flips-first-helper (a b f1 f2 f3)
  (if (equal a (list f1 f2 f3))
    0
    (if (equal b (list f1 f2 f3))
      100
      (flips-first-helper a b f2 f3 (flip)))))

(defun flips-first (a b)
  (flips-first-helper a b (flip) (flip) (flip)))

(flips-first-percentage '(tails heads heads) '(tails heads tails) 1000000)
50.034
```
How can this not conflict with the already-established answer to the first version of the question? Because when THT occurs first, it can be followed only two flips later by THH; but when THH occurs first, the next possible time THT can occur is three flips later.

Note that this equal-probability-of-first-occurrance is not universal. For instance:
```
(flips-first-percentage '(heads heads tails) '(tails heads tails) 1000000)
37.452
```
30 Mark Says:
November 24th, 2007 at 5:33 pm
David, I watched that video at TED, and it was really interesting. Peter Donnelly is a surprisingly good speaker for a statistics geek. I chose this particular probability question because I thought it was fairly simple and novel, while everyone would already have encountered the “if the test for a rare disease is 99% accurate” scenario.
31 V.Wood Says:
November 24th, 2007 at 8:12 pm
THH will be more likely. Because if it fails, having got to the last part (until which the two outcomes are equal) it will have THT, the last flip of which is the start of its sequence. This is not the case for THT, which will have to wait for another Tails before it can start its sequence.
32 John Fremlin Says:
November 24th, 2007 at 8:22 pm
The problem is that the question was not framed precisely. In fact there are two questions:

If we were to do this again and again thousands of times and calculate the average number of tosses it takes to get Pattern 1 and compare it to the average number of tosses it takes to get Pattern 2, which be the bigger number?

In this case the answer is 8 and 10 tosses respectively (the Lisp program does not count the first two tosses).

Of course, on average, both patterns occur at the same frequency. So how can this be? As has already been pointed out the reason is that the matches with THH are less clumped together, so the spacing between them is more regular, so the mean tosses to the first one is less.

The other question is:

On average, which will we see sooner?

The correct answer is that they are equally likely to come up first.

To see this, note that they both start with the same prefix (TH). Once that occurs in the sequence there is 1/2 chance that you will get THH and 1/2 chance that you will get THH.

This is slightly surprising, but can be reconciled slightly with the former argument by noting that if THT comes up then THTHH is quite likely.

What is most interesting is that in a race between HHT and THT, HHT will come up first 5/8 of the time . . . and in a race between HHT and HTH, then HHT will win 2/3 of the time . . .
33 Uncle J Says:
November 24th, 2007 at 8:39 pm
Gordon got it right.

I guess the question was supposed to be HHT, not THH.
34 Thomas David Baker Says:
November 24th, 2007 at 8:56 pm
I too voted for equal chance and then wrote a program that showed that to be the correct answer. I ran 1 million simulations of a series of 100 coin flips and checked which sequence came first in each of the series. Having now read the comments I see what you were getting at, but the wording (of the poll in particular) is very misleading!
35 Mark Says:
November 24th, 2007 at 9:18 pm
John and Gordon and Tom, I guess you guys parse “On average, which will we see sooner?”, differently than I do.

Imagine you’ve got two co-workers. On half of all work days, guy A shows up to work at 9:00 and guy B shows up at work at 9:01. On the other half of work days guy B shows up at 9:00 and guy A shows up at noon. I’d say that on average guy B shows up sooner. Maybe you would say that on average they show up “equally soon”.

I’ve re-worded it in order to try to make it clearer, though. Language can be a blunt instrument, at least in my hands.
36 j Says:
November 24th, 2007 at 10:28 pm
Two words: Independent events.
37 dr-steve Says:
November 24th, 2007 at 10:36 pm
THH will occur more frequently in an arbitrary long sequence of flips, hence, will have the shortest time-to-hit.

Build a simple set of all possible flips:
TTT
TTH
THT
THH
etc.

Now, for each line, at the end of the set, determine how quickly the set sequence can be achieved. If it is already there, score it a 0, else use any partial patterns built.

For example, if TTH had just been flipped, it would take (minimally) three additional flips to hit THT. However, you could hit THH with one additional flip.

In the long run, the average time-to-hit after any given three flips is, for THT, 2 more flips. For THH, you will need an average of 1.875 more flips.

So, in the long run, you will hit more THHs than THTs.

(This is a common problem in optimal string matching in logn sequences and determining their restart point. I’ll refer to Aho Hopcroft Ullman: The Design and Analysis of Computer Algorithms, but that’s a bit out of print now…)

-Steve
38 Robin Says:
November 24th, 2007 at 10:53 pm
Mark: Yay! I won’t be in Taiwan in the foreseeable future, but maybe someday when I’ll be there to study Mandarin, I will remember and come back to your offer :).
39 StanislavZza Says:
November 24th, 2007 at 11:46 pm
If you interpret the problem as a flat out race–given the same input and simultaneous matching, which comes first–then the conditional probabilities are obviously the same. Nothing interesting happens until TH comes up, at which the conditionals are .5 for each pattern. If the races are separate (you can use the same input, but don’t compare simultaneously) the answers are different. Drawing a state diagram makes that easy to see.

Here’s an interesting followup question. What {T,F} string of length N has the highest and lowest probability of non-simultaneous match? The answers won’t be unique, of course. Seems like T^N (meaning a string of N Ts) would be the lowest probability, since it completely resets every time a H comes up. A string like HT^(N-1) increases match probability because it will never reset completely to the ’start’ state. Is this the best we can do?

Here’s a Perl sandbox (not the most efficient code):

$flip[0]=’H';
$flip[1]=’T';

$i=$N = 10000; # number of trials

$target_string1 = ‘HTHH’;
$target_string2 =’THHH’;

#flip some coins
while ($i–){
$outcome = $flip[int(rand()*2)];
$str .= $outcome;
$count{$outcome}++;
}

print “Flipped $count{H} heads and $count{T} tails\n\n”;

print “$target_string1 proportion: “, scalar($str =~ s/$target_string1//g)/$N, “\n” ;
print “$target_string2 proportion: “, scalar($str =~ s/$target_string2//g)/$N , “\n”;
40 Uncle J Says:
November 25th, 2007 at 12:27 am
What do you mean by “For example, if TTH had just been flipped, it would take (minimally) three additional flips to hit THT. However, you could hit THH with one additional flip.” ???

It will end up either TTHH or TTHT. Each will need only one additional flip.

I’m suspecting your simulations are lacking something…

On any given row of coin flips, there are equal number of rows with THT or THH. This means that on any given row of coin flips, both come up as soon.
41 Uncle J Says:
November 25th, 2007 at 12:37 am
Ok, now i got it.

The question can be understood in two ways.

1) One person flips a coin, and marks down both THT’s and THH’s.

2) Two persons flip a coin. Another marks down THT’s and another marks down THH’s only.

This is not a hard puzzle, pretty much anyone will get this. It is just unclearly worded. Sorry for ruining this.
42 John Fremlin Says:
November 25th, 2007 at 12:39 am
To Mark: thanks for your clarification.

To everyone else: I’m sorry for posting my answer repeating what everybody else said but I was off the Internet for a while and hadn’t realised that it had already been posted

Still let me emphasize what other people have been saying, that probably the original inspiration for the problem was about the cases with 2/3 and 5/8 which are much more fun to figure out.

Steve:

For example, if TTH had just been flipped, it would take (minimally) three additional flips to hit THT. However, you could hit THH with one additional flip.

If TTH had been flipped, you could hit THT in one flip by getting T.

In a long sequence where each element is a fair coin toss, all triples (HHH, …, TTT) are equally likely to come up at any three toss subsequence in the sequence.
43 Mark Says:
November 25th, 2007 at 12:49 am
Uncle J said:

This is not a hard puzzle, pretty much anyone will get this. It is just unclearly worded.

Don’t be too sure about that, Uncle J. There may be a few people who misunderstood this to be a race between two groups watching the same coin, but as of now, with over 1,000 voters, THT is beating THH by a sizable margin.

44 Mike H Says:
November 25th, 2007 at 1:04 am


require 'active_support'
SIMS = 10000

def flip
  rand() > 0.5 ? :H : :T
end

def times_till_pattern(pt)
  a = []
  while true
    a << flip
    return a.size if a[-3..-1] == pt
  end
end

def avg_times(pt)
  res = (1..SIMS).map { |x| times_till_pattern(pt) }.sum
  res = res.to_f / SIMS.to_f
  puts "#{pt.inspect}: #{res}"
end

avg_times [:T,:H,:T]
avg_times [:T,:H,:H]

[:T, :H, :T]: 10.1157
[:T, :H, :H]: 7.9193

45 Tim Mitchell Says:
November 25th, 2007 at 2:06 am
Some folks are making this way too complex: previous outcomes don’t effect future outcomes, if the flip is truly random.

Once you flip TH, the next flip is equally likely to be T or H.

So THH and THT are equally likely to occur.

Do I get points for simplicity?
46 StanislavZza Says:
November 25th, 2007 at 4:17 am
My Perl sandbox has a bug…

use

print “$target_string1 proportion: “, scalar($str =~ s/$target_string1/$target_string1/g)/$N, “\n” ;
print “$target_string2 proportion: “, scalar($str =~ s/$target_string2/$target_string2/g)/$N , “\n”;
47 Brian Szymański Says:
November 25th, 2007 at 4:37 am
Sheesh, if you’re going to do it in perl, at least do it optimized for code size (aka impossible to read):

perl -le ‘$p=THH;while(1){$s=”";$s.=rand()<0.5?T:H while($s!~/$p/);$l+=length($s);$i++;print$l/$i}’

That gives the average number of trials until you find Tails-Heads-Heads. s/THH/THT/ to see the average number needed for Tails-Heads-Tails
48 JFred Says:
November 25th, 2007 at 6:18 am
1) Bad grammar in problem statement, words missing:

Now imagine that we’re interested in seeing it takes to get a certain sequence of outcomes.

We naturally assume we know what the question is, but we don’t.

2) One version of the problem statement:

which be the bigger number?

Followed by another, opposite version:

On average, which pattern takes fewer coin tosses?

And, ‘v’ misquotes the letter-triples to have different prefixes:

(HTH) or the other (THH)

Further leading us astray.

Plus, it was not at all clear to me that one was supposed to search for one sequence only, then for the other sequence only. Although it can be interpreted that way.

This is not an obvious question, as I did not even think to look if the two patterns had the same two-letter prefix. I just noticed they were different.

The two strings TTH and THH, varying only the middle letter, take equally long to show up, by the definitions of this puzzle.

But the two patterns THT and TTT, also varying only the middle letter, take different amounts of time to show up, on the average.

These last two cases prove that this is not a ’simple puzzle’. I think if it were advertised as a ‘tricky puzzle’ you would have gotten a greater percentage of correct votes, but fewer votes overall.

Robins explanation is probably right, but is incomplete.

49 YRU2L8 Says:
November 25th, 2007 at 6:56 am

import random

def s010():
  x=''
  while not x.endswith('010'):
    x += random.choice('01')
  return len(x)

def s011():
  x=''
  while not x.endswith('011'):
    x += random.choice('01')
  return len(x)

l = 0
for i in xrange(1000000):
  l += s010()
print '010 %9.6f' % (l/1e6)

l = 0
for i in xrange(1000000):
  l += s011()
print '011 %9.6f' % (l/1e6)

# 010 10.0...
# 011  8.0...

50 Naruwan Says:
November 25th, 2007 at 9:56 am
The question is asking which pattern will be arrived at first, right? Then I agree with Tim. Once you have reached the pattern TH, the odds of then getting a head or a tail are equal. Simple, no perl required.

If you think this is the wrong explanation, then please explain why. Thanks!
51 Mark Says:
November 25th, 2007 at 10:21 am
It’s not quite that simple. The question was about averages. It takes about 8 flips to reach THH on average, while it takes about 10 for THT. Both sequences depend on starting with TH, and both could match in only three flips. The reason the above numbers are different is because of what happens after not matching on the third flip.

When trying to match THT, if the third flip fails to match, you’ve got THH, and the soonest possible match would be 6 flips (THHTHT).

When trying to match THH, if the third flip fails to match, you’ve got THT, and the soonest possible match would be 5 flips (THTHH).

Half of the time, THT will match first and half of the time THH will match first, but the average number of flips required to get THH is 2 fewer than the number required to get THT. Aren’t probabilities fun?
52 Andrew Baine Says:
November 25th, 2007 at 10:37 am
Let F represent expected number of flips until THT. F = .5(1 + F) + .5(1 + X) where X is expected time to THT given you start with a T before you make your first flip.
Of course, X = .25(2 + F) + .25(2) + .5(1 + X). Two equations in two unknowns. F = 10. We expect it takes 10 flips to get THT.

Let G represent expected number of flips until THH. Again, G = .5(1 + G) + .5(1 + Y) where Y is expected time to THH given you start with a T before you make your first flip. Of course, Y = .25(2 + Y) + .25(2) + .5(1 + Y). Now Y = 6 so G = 8. We expect it takes 8 flips to get to THH.

QED
53 Tim Mitchell Says:
November 25th, 2007 at 11:38 am
I understand what you are saying, and you put it quite elegantly.

The problem is that, in both of your examples, what you are trying to do is irrelevant, if I’m reading the problem correctly.

Regardless of what you want, in both of your examples, THT or THH come on the third flip, and the game is over.
54 Tim Mitchell Says:
November 25th, 2007 at 11:59 am
Sorry, don’t know how to edit here.

First off, my answer above reread kind of sarcastic, or worse, condescending. In fact, I was sincere about the elegance of your explanation, and I’m still letting it rattle around in my head.

Thus, ’cause of the rattling: ONLY the set of the winning three coin flips will matter at all for the game. Even given an infinite number of flips, and a perfect random generator, only the set of three flips that ends in THH or THT matter.

The set of winning flips will always begin with “TH” and end with “H” or “T”.

“TH” may be more favored by previous sequences (and I think that’s part of what you were getting at), as in HHH vs. HHT. But, as I hope I’ve shown above, the problem, by definition, assumes the the first two numbers of the set.
55 chee tji hun Says:
November 25th, 2007 at 3:43 pm
THTHTHT matches THT 3 consecutive times with just an 8 character long string, while THHTHHTHH requires 9 chars to match THH 3 consecutive times

considering this THT should match more times in an infinitely long sequence i think it should match 1/8 times more than THH
56 JFred Says:
November 25th, 2007 at 5:57 pm
Tim Mitchell is still interpreting the question differently than our puzzle-poser, Mark. I take this as further proof that there is a problem with the way the question is posed.
57 Mark Says:
November 25th, 2007 at 6:22 pm
How would you pose the question, JFred?
58 JFred Says:
November 25th, 2007 at 10:51 pm
I don’t have a fully worked out text. It should include the phrases “two lists of flips like ‘hthht’ each being searched by two different people searching for different things” to emphasize the main idea that lots of people simply missed.

It should give a warning like ‘it’s not what you think’ or ‘tricky answer’ to make sure people think before they vote. Or maybe just ‘think before you vote’.

Say ‘Hint: the first two letters are the same’. This is a fair hint since it really gives no new information but may wake up the reader.

Your original text had some very clear stuff in it, but once the reader has formed the wrong idea of the question it skips right by. So I’d change:
’start flipping a coin for pattern 1′
to
’start flipping a coin ONLY looking for pattern 1′. And so on.

Since kids read the web, you could say there is Mr. Thomas H Howard looking for his initials (thh) and Mrs Teresa Hope Trask looking for her initials (tht). Personalizing things make things clearer, especially for kids.

By the way, the puzzle is great and I did learn something. With all the hints I suggest, however, I still would have gotten it wrong unless I coded a simulation. But with all those hints I am much more likely to have coded a simulation instead of leaping ahead.

When the ‘Monty Hall’ problem was popular a few years ago, and was highlighted in the New York Times, I coded a simulation in C and found the answer in the writing of the program, not the running. Here, even the running left me still working on it.
59 Mark Says:
November 26th, 2007 at 12:20 am
Thanks for the feedback.
60 Tim Mitchell Says:
November 26th, 2007 at 12:30 am
I see where I misunderstood, and here was my problem:

Then we reached Pattern 1 after only six coin tosses. Sometimes it will take as few as three coin tosses, but other times it will take many more.

The “sometimes it will only take three tosses” part led me to believe that, in the example, if you hit THT after three flips, you were done.
61 Max Khesin Says:
November 26th, 2007 at 1:14 am
Same answer as already published, but slightly different reasoning.

Basically, I thought backwards. If the pattern of interest is “THT”, it implies that the previous 2 throws were NOT “TH” (otherwise the pattern would have already occured). “THH” occuring does not assume anything about the preceeding sequence. So if you look at it as 5-sequence run, the run
“NOT T, NOT H, T, H, T” is more rare than the run “ANYTHING, ANYTHING, T, H, H”.
62 william Says:
November 26th, 2007 at 1:25 am
any specific three-toss pattern will happen with the same average number of tosses. tails tails tails the same as heads tails heads, whatever. it is 2 x 2 x 2 =ing 8 tosses on average for each pattern. kissy
63 Tim Mitchell Says:
November 26th, 2007 at 3:19 am
Mark,

Not trying to be a pain, honest. I’ve enjoyed toying with this puzzle, even when I misunderstood.

See if I get the problem with this description (note that I’m still starting with THH and THT as givens for the beginning of the sequences. If that doesn’t work out, I’m still missing something).

1. Start with THH. Flip until you get THT.
2. Start with THT, flip until you get THH.
Which sequence will, on average, be longer?

If I’m stating it correctly, then THH to THT will be the longer sequence on average. Starting with THT, it’s possible to get your “TH” on the next flip, whereas it’s impossible starting with THH.

I know I’m way past the point of telling my wife, “Well, I’m off to Taipei for a free beer!” But if you’re ever in Minneapolis, I’ll buy you an entire dinner.

Even when I’m wrong, I have fun.
64 Mark Says:
November 26th, 2007 at 3:55 am
I’ll keep your offer in mind. Thanks! It sounds like you’ve basically got it. Another way of thinking of your analogy would be this:

1. Start with THH. Flip until you get THT.
2. Start with THT, flip until you get THH, or HH right away (since you’ve already got the initial T)

Which takes longer?
65 wayne Says:
November 26th, 2007 at 1:46 pm
I was trying to wrack my brain trying to think of how to mathematically derive the average number of flips it would require to get to THT or THH, but I couldn’t come up with anything. I agree with Robin’s intuition and the brute force Monte Carlo program bears out that reasoning, but that’s not enough.

Anyhow, I guess you could state that for any sequence of heads and tails aBc (where a and c denote one head or tail and B denotes any number of heads and tails), you will reach a1Bc1 before a2Bc2 if a1 doesn’t equal c1 and a2 equals c2.

For instance, you will reach THHHHHHHHHH in a fewer number of flips than you will reach THHHHHHHHHT.
66 Giavasan » Un semplice quiz sulle probabilità Says:
November 26th, 2007 at 1:53 pm
[...] Link: A Simple Probability Puzzle. [...]
67 Mark Says:
November 27th, 2007 at 12:31 am
Wayne, Sam’s comment #23 might be what you’re looking for. It’s a mathematical derivation of how many flips it will take to get the sequence
68 Even Simple Probabilty Puzzles Can Be Tricky | Doubting to shuo: Chinese, Investing, EFL and Being a Geek in Taiwan Says:
November 27th, 2007 at 6:33 am
[...] votes from Friday’s Simple Probability Puzzle are in. Here was the question: Imagine there’s a completely random event with two outcomes, say [...]
69 Michael Turton Says:
November 27th, 2007 at 1:37 pm
Very interesting puzzle, Mark. Very enjoyable.

Michael

70 JD Huntington Says:
November 29th, 2007 at 6:36 am

FYI: The rough probabilities for all 8 three coin flips are as follows:


(((H H H) 13.76811111111111)
 ((H H T) 8.067777777777778)
 ((H T H) 9.979)
 ((H T T) 8.085888888888888)
 ((T H H) 8.022222222222222)
 ((T H T) 9.956666666666667)
 ((T T H) 7.963111111111111)
 ((T T T) 14.158444444444445))

71 Mark Says:
November 30th, 2007 at 2:18 am
See the follow-up post. It goes through how to calculate them exactly.

http://toshuo.com/2007/even-simple-probabilty-puzzles-can-be-tricky/