Finding Sequences Puzzle

[pdurrant]

Here's a Simple Probability Puzzle, taken from http://toshuo.com/2007/a-simple-probability-puzzle/

You are monitoring an automatic coin flipping machine. It flips a coins every second, and you can see whether the coin lands show Heads (H) or Tails (T). You will be looking for non-overlapping sequences of three results. For instance, if you were looking for HTH, the sequence THTHTHHHTHTT would have only two HTH sequences in it (bold) THTHTHHHTHTT.

Your first task is to keep watch until 10 sequences of THT have appeared. After you've seen the 10th THT sequence, you note the total number of coin tosses you've observed while monitoring for THT

Once you've spotted 10 sequences of THT, you start monitoring again with the next coin toss after the last T of your tenth THT sequence. This time you're looking for sequences of THH. Again, after you've seen the 10th THH sequence, you note the total number of coin tosses you've observed while monitoring for THH.

The coin tossing machine is fair (H 50%, T 50%) and random. You are vigilant, and do not make any mistakes in your monitoring of the coin tosses.

On average, will the number of coin tosses you observe while monitoring for THT be greater, the same or less than the number of coins tosses you observe while monitoring for THH?

Please vote!

You may also give an argument for your vote in comment, in

Spoiler:

spoiler tags

please.

[obs20]

Spoiler:

I'd say the THH requires less tosses because as you finish the task of counting for THT the last element of T is already there.

[pdurrant]

Originally Posted by obs20

Spoiler:

I'd say the THH requires less tosses because as you finish the task of counting for THT the last element of T is already there.

Let me clarify. There is no overlap in the sequences, even when going from one task to the next. When you finish monitoring for THT, you start monitoring for THH starting with the next coin toss, not the last one of THT. (Question edited to clarify this point.)

[clarknova]

Originally Posted by pdurrant

Here's a Simple Probability Puzzle, taken from http://toshuo.com/2007/a-simple-probability-puzzle/

If this is simple then I must be a total moron.

Spoiler:

I need to change my vote, since I picked the first one.

Now I know that 10 THH sequences takes less than 10 THT sequences, but I have no idea why.

On average it takes 80 coin flips to get 10 THH sequences. And it takes 100 flips to get 10 THT sequences (non-overlapping). I really hope someone can explain to me why.

TTT/HHH = 140 flips
THT/HTH = 100 flips
THH/HTT/TTH/HHT = 80 flips

Interestingly, if you use the patterns as binary numbers, and shift left by 1 (multiply by 2), and then multiply by 10 (the number of patterns to detect), you get their average coin flip amounts:

TTT = 111b << 1 = 1110b = 14 (*10 = 140)
THT = 101b << 1 = 1010b = 10 (*10 = 100)
THH = 100b << 1 = 1000b = 8 (*10 = 80)

But I'm still left without the reason. I guess I'll go read the original website.

[Lo Zeno]

Spoiler:

The sequence that needs, ON AVERAGE, less coin tosses is THH.

I'll explain you why, trying to be as simple as I can be: each toss is an independent event, which means that each time I toss the coin I have 50% chances to get Head, and 50% chances to get Tail.
Following this logic, each sequence (THH and THT) should have the same chances to happen... BUT! There's one thing to consider: we're looking for specific sequences!

Let's assume that we are now trying to get the THT sequence, and we already got one Tail and one Head (TH). Now we toss the coin, and we have 50% chances to get Tail (and complete the THT), and 50% chances to get Head, so we have to continue tossing: in case we get Head, so we DON'T finish the sequence, we'll need AT LEAST three more tosses, because the latest two results we got would be Head-Head, so in the most lucky condition we would have to get another Tail followed by another Head and another Tail.

Let's assume now that we are trying to get the THH sequence, and once again we already got one Tail and one Head (TH). Once again, we have 50% chances to get Head (thus completing the sequence), and50% chances to get Tail (thus FAILING the sequence). But Wait! If we fail, our last toss resulted in a Tail (T), so in the most lucky condition we only would need TWO more tosses (two Heads) to complete the sequence, instead of three.

This small, unique case makes the combination THH "quicker" than the combination THT on average

[Format C:]

The answer is in the blog linked in the first post, and Lo Zeno got it right.

[pdurrant]

Originally Posted by Lo Zeno

Spoiler:

The sequence that needs, ON AVERAGE, less coin tosses is THH.

I'll explain you why, trying to be as simple as I can be: each toss is an independent event, which means that each time I toss the coin I have 50% chances to get Head, and 50% chances to get Tail.
Following this logic, each sequence (THH and THT) should have the same chances to happen... BUT! There's one thing to consider: we're looking for specific sequences!

Let's assume that we are now trying to get the THT sequence, and we already got one Tail and one Head (TH). Now we toss the coin, and we have 50% chances to get Tail (and complete the THT), and 50% chances to get Head, so we have to continue tossing: in case we get Head, so we DON'T finish the sequence, we'll need AT LEAST three more tosses, because the latest two results we got would be Head-Head, so in the most lucky condition we would have to get another Tail followed by another Head and another Tail.

Let's assume now that we are trying to get the THH sequence, and once again we already got one Tail and one Head (TH). Once again, we have 50% chances to get Head (thus completing the sequence), and50% chances to get Tail (thus FAILING the sequence). But Wait! If we fail, our last toss resulted in a Tail (T), so in the most lucky condition we only would need TWO more tosses (two Heads) to complete the sequence, instead of three.

This small, unique case makes the combination THH "quicker" than the combination THT on average

Exactly right.

[pdurrant]

Originally Posted by clarknova

If this is simple then I must be a total moron.

Spoiler:

I need to change my vote, since I picked the first one.

Now I know that 10 THH sequences takes less than 10 THT sequences, but I have no idea why.

On average it takes 80 coin flips to get 10 THH sequences. And it takes 100 flips to get 10 THT sequences (non-overlapping). I really hope someone can explain to me why.

TTT/HHH = 140 flips
THT/HTH = 100 flips
THH/HTT/TTH/HHT = 80 flips

Interestingly, if you use the patterns as binary numbers, and shift left by 1 (multiply by 2), and then multiply by 10 (the number of patterns to detect), you get their average coin flip amounts:

TTT = 111b << 1 = 1110b = 14 (*10 = 140)
THT = 101b << 1 = 1010b = 10 (*10 = 100)
THH = 100b << 1 = 1000b = 8 (*10 = 80)

But I'm still left without the reason. I guess I'll go read the original website.

Lo Zeno has given a good verbal explanation.

[pdurrant]

Originally Posted by Format C:

The answer is in the blog linked in the first post, and Lo Zeno got it right.

The answer to any of the puzzles could probably be found by googling. But since the pleasure of puzzles is in trying to answer them without reading the answer....

[Lo Zeno]

I solved it because that puzzle is very, very similar to one that my statistics & probability teacher at university made us solve

[pdurrant]

Once the poll closes on Monday, I'll post the answer, a verbal explanation, and mathematical way to calculate the answer.

[pdurrant]

Originally Posted by pdurrant

Once the poll closes on Monday, I'll post the answer, a verbal explanation, and mathematical way to calculate the answer.

I just noticed that the poll closes at 11pm BST, so I'll post answer/explanation on Tuesday.

[pdurrant]

Answer:

Spoiler:

The THT sequence needs more coin tosses.

Less than 50% got it right! It shows how tricky even seemingly simply probability questions can be.

A bare answer doesn't really help those of you who got the answer wrong.

Here's an explanation

Spoiler:

I don't think I can do better for a verbal explanation of why THT needs more coin tosses that THH than the one Lo Zeno provided:

Originally Posted by Lo Zeno

Let's assume that we are now trying to get the THT sequence, and we already got one Tail and one Head (TH). Now we toss the coin, and we have 50% chances to get Tail (and complete the THT), and 50% chances to get Head, so we have to continue tossing: in case we get Head, so we DON'T finish the sequence, we'll need AT LEAST three more tosses, because the latest two results we got would be Head-Head, so in the most lucky condition we would have to get another Tail followed by another Head and another Tail.

Let's assume now that we are trying to get the THH sequence, and once again we already got one Tail and one Head (TH). Once again, we have 50% chances to get Head (thus completing the sequence), and 50% chances to get Tail (thus FAILING the sequence). But Wait! If we fail, our last toss resulted in a Tail (T), so in the most lucky condition we only would need TWO more tosses (two Heads) to complete the sequence, instead of three.

This small, unique case makes the combination THH "quicker" than the combination THT on average

Indeed, as ClarkNova found in his computer simulation of the problem, on average, you'll need to monitor 100 coin tosses to spot 10 THT sequences, but only 80 coin tosses to spot 10 THH sequences.

and an analysis.

Spoiler:

There is a way to work this out mathematically, but we need to introduce a little notation to make it concise.

We want a way to represent the average number of additional coin tosses to get a particular sequence of coin tosses, given that we've already seen some coin tosses. We're going to use N(sequence|previous sequence) for this.

For example, N[TH|T] is the average number of additional coin tosses we'd need to observe to see a sequence of Tails followed by Heads, after we've just seen a Tails.

Note that
N[Tsequence|previoussequenceH] = N[Tsequence|]
That is, if the sequence we're looking for starts with a Tails, and the coin tosses we've just seen ended with a Heads, the average number of additional coin tosses needed to see what we're looking for is that same as if we hadn't seen any coin tosses yet.

Also
N(sequence|sequence) = 0
That is, if we've just seen the sequence we're looking for, we don't need any more coin tosses to see the sequence.

We want to know N[THH|] (seeing Tails, Heads, Heads, without having seen any coin tosses yet) and N[THT|] (seeing Tails, Heads, Heads, without having seen any coin tosses yet).

We can write N[THH|] like this

N[THH|] = 0.5*(1 + N[THH|H]) + 0.5*(1 + N[THH|T])

That is, the average sequence length is half of one plus the average sequence length given we've seen a Heads and half of one plus the average sequence length given we've seen a Tails. Remembering that N[THH|H] = N[THH|], this simplifies to

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

Now, we can also work out that

N[THH|T] = 0.5*(1 + N[THH|TH]) + 0.5*(1 + N[THH|TT])

simplifying again (note that N[THH|TT] = N[THH|T]) , we get

N[THH|T] = 2 + N[THH|TH]

and substituting back, we get

N[THH|] = 4 + N[THH|TH]

And similarly, we can see that

N[THH|TH] = 0.5*(1 + N[THH|THH]) + 0.5(1 + N[THH|THT])

simplifying again (note that N[THH|THT] = N[THH|T]), we get

N[THH|TH] = 1 + 0.5*N[THH|T]

and using our previous result that N[THH|T] = 2 + N[THH|TH], we find

N[THH|TH] = 4

and so

N[THH|] = 8.



Similarly for N[THT|]:

N[THT|] = 0.5*(1 + N[THT|H]) + 0.5*(1 + N[THT|T])
simplifies (as N[THT|H] = N[THT|]) to
N[THT|] = 2 + N[THT|T]

Now, we can also work out that
N[THT|T] = 0.5*(1 + N[THT|TH]) + 0.5*(1 + N[THT|TT])
simplifying again (note that N[THH|TT] = N[THH|T]) , we get
N[THT|T] = 2 + N[THT|TH]

Substituting back, we get
N[THT|] = 4 + N[THT|TH]

NB This is all identical to the reasoning for THH

And similarly, we can see that
N[THT|TH] = 0.5*(1 + N[THT|THH]) + 0.5(1 + N[THT|THT])
simplifies (noting that N[THT|THH] = N[THT] and N[THT|THT] = 0) to
N[THT|TH] = 1 + 0.5*N[THT|]

NB Here is the difference from the THH case. For THH we saw that N[THH|THT] = N[THH|T], but here we see that N[THT|THH] = N[THT|]

and using our previous result that N[THT|] = 4 + N[THT|TH], we find

N[THT|TH] = 6

and so

N[THT|] = 10.

Whew! Hopefully I haven't made too many typos in that!