Register Guidelines E-Books Today's Posts Search

Go Back   MobileRead Forums > Miscellaneous > Lounge

Notices

View Poll Results: Which is the correct outcome on average?
THT and THH need the same number of coin tosses 6 50.00%
THT sequence needs more coin tosses 5 41.67%
THH sequence need more coin tosses 1 8.33%
Voters: 12. You may not vote on this poll

Reply
 
Thread Tools Search this Thread
Old 07-26-2010, 06:00 PM   #1
pdurrant
The Grand Mouse 高貴的老鼠
pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.
 
pdurrant's Avatar
 
Posts: 73,737
Karma: 315126578
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Oasis
Finding Sequences Puzzle

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.

Last edited by pdurrant; 07-27-2010 at 04:45 AM. Reason: edited for clarity
pdurrant is offline   Reply With Quote
Old 07-26-2010, 08:05 PM   #2
obs20
Wizard
obs20 ought to be getting tired of karma fortunes by now.obs20 ought to be getting tired of karma fortunes by now.obs20 ought to be getting tired of karma fortunes by now.obs20 ought to be getting tired of karma fortunes by now.obs20 ought to be getting tired of karma fortunes by now.obs20 ought to be getting tired of karma fortunes by now.obs20 ought to be getting tired of karma fortunes by now.obs20 ought to be getting tired of karma fortunes by now.obs20 ought to be getting tired of karma fortunes by now.obs20 ought to be getting tired of karma fortunes by now.obs20 ought to be getting tired of karma fortunes by now.
 
obs20's Avatar
 
Posts: 2,793
Karma: 29028512
Join Date: May 2010
Location: Florida
Device: Sony PRS 600, Nook ST, Toshiba Excite 10.1 AT 300
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.
obs20 is offline   Reply With Quote
Advert
Old 07-27-2010, 04:44 AM   #3
pdurrant
The Grand Mouse 高貴的老鼠
pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.
 
pdurrant's Avatar
 
Posts: 73,737
Karma: 315126578
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Oasis
Quote:
Originally Posted by obs20 View Post
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.)
pdurrant is offline   Reply With Quote
Old 07-27-2010, 09:31 AM   #4
clarknova
Addict
clarknova plays well with othersclarknova plays well with othersclarknova plays well with othersclarknova plays well with othersclarknova plays well with othersclarknova plays well with othersclarknova plays well with othersclarknova plays well with othersclarknova plays well with othersclarknova plays well with othersclarknova plays well with others
 
clarknova's Avatar
 
Posts: 241
Karma: 2617
Join Date: Mar 2009
Location: Greenwood, SC
Device: Kindle 2
Quote:
Originally Posted by pdurrant View Post
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.
clarknova is offline   Reply With Quote
Old 07-27-2010, 10:00 AM   #5
Lo Zeno
Addict
Lo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura about
 
Posts: 202
Karma: 4379
Join Date: May 2009
Location: Italy
Device: Hanlin V3 (with lBook firmware & OpenInkPot)
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

Lo Zeno is offline   Reply With Quote
Advert
Old 07-27-2010, 10:39 AM   #6
Format C:
Guru
Format C: ought to be getting tired of karma fortunes by now.Format C: ought to be getting tired of karma fortunes by now.Format C: ought to be getting tired of karma fortunes by now.Format C: ought to be getting tired of karma fortunes by now.Format C: ought to be getting tired of karma fortunes by now.Format C: ought to be getting tired of karma fortunes by now.Format C: ought to be getting tired of karma fortunes by now.Format C: ought to be getting tired of karma fortunes by now.Format C: ought to be getting tired of karma fortunes by now.Format C: ought to be getting tired of karma fortunes by now.Format C: ought to be getting tired of karma fortunes by now.
 
Posts: 753
Karma: 1496807
Join Date: Jul 2008
Location: The Third World
Device: iLiad + PRS-505 + Kindle 3
The answer is in the blog linked in the first post, and Lo Zeno got it right.

Format C: is offline   Reply With Quote
Old 07-27-2010, 11:21 AM   #7
pdurrant
The Grand Mouse 高貴的老鼠
pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.
 
pdurrant's Avatar
 
Posts: 73,737
Karma: 315126578
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Oasis
Quote:
Originally Posted by Lo Zeno View Post
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 is offline   Reply With Quote
Old 07-27-2010, 11:22 AM   #8
pdurrant
The Grand Mouse 高貴的老鼠
pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.
 
pdurrant's Avatar
 
Posts: 73,737
Karma: 315126578
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Oasis
Quote:
Originally Posted by clarknova View Post
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 is offline   Reply With Quote
Old 07-27-2010, 11:24 AM   #9
pdurrant
The Grand Mouse 高貴的老鼠
pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.
 
pdurrant's Avatar
 
Posts: 73,737
Karma: 315126578
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Oasis
Quote:
Originally Posted by Format C: View Post
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....
pdurrant is offline   Reply With Quote
Old 07-27-2010, 06:46 PM   #10
Lo Zeno
Addict
Lo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura aboutLo Zeno has a spectacular aura about
 
Posts: 202
Karma: 4379
Join Date: May 2009
Location: Italy
Device: Hanlin V3 (with lBook firmware & OpenInkPot)
I solved it because that puzzle is very, very similar to one that my statistics & probability teacher at university made us solve
Lo Zeno is offline   Reply With Quote
Old 07-29-2010, 06:49 AM   #11
pdurrant
The Grand Mouse 高貴的老鼠
pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.
 
pdurrant's Avatar
 
Posts: 73,737
Karma: 315126578
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Oasis
Once the poll closes on Monday, I'll post the answer, a verbal explanation, and mathematical way to calculate the answer.
pdurrant is offline   Reply With Quote
Old 08-02-2010, 03:14 AM   #12
pdurrant
The Grand Mouse 高貴的老鼠
pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.
 
pdurrant's Avatar
 
Posts: 73,737
Karma: 315126578
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Oasis
Quote:
Originally Posted by pdurrant View Post
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 is offline   Reply With Quote
Old 08-03-2010, 04:22 AM   #13
pdurrant
The Grand Mouse 高貴的老鼠
pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.pdurrant ought to be getting tired of karma fortunes by now.
 
pdurrant's Avatar
 
Posts: 73,737
Karma: 315126578
Join Date: Jul 2007
Location: Norfolk, England
Device: Kindle Oasis
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:
Quote:
Originally Posted by Lo Zeno View Post
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!
pdurrant is offline   Reply With Quote
Reply


Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
The Last Bean Puzzle pdurrant Lounge 26 06-30-2010 04:01 PM
Number Puzzle pdurrant Lounge 14 06-23-2010 01:02 PM
Gallon Puzzle pdurrant Lounge 31 06-16-2010 03:18 AM
Number Sequences pdurrant Lounge 8 06-11-2010 03:14 PM
Puzzle emonti8384 Lounge 60 02-08-2010 09:55 PM


All times are GMT -4. The time now is 05:58 PM.


MobileRead.com is a privately owned, operated and funded community.