Coin toss problem - which sequence will appear first?

Question

My original problem:

http://answers.yahoo.com/question/index;_ylt=Anr2nrTJ85YJWm4CKDAmXIg8.Bd.;_ylv=3?qid=20080825135226AAIsU0t

A follow up problem to my original problem:

http://answers.yahoo.com/question/index;_ylt=AgXNFP_0bzBrrcbjq6b3QVbsy6IX;_ylv=3?qid=20080825143625AAdmSPo&show=7#profile-info-AA10667595

Question is:

Imagine tossing a coin successfully and waiting until the first time a particular pattern appears, say HTT.

For example, if the sequence of tosses was

HHTHHTHHTTHHTTTHTH

The pattern HTT appears would appear after the 10th toss.

My problem compared the pattern THT and THH. The followup problem compared THT and TTH. We wanted to know which sequence on average would appear first (in my particular case, I also asked when they would appear on average)

Are the two problems any different (other than the obvious THH vs TTH difference). That is, do they have the same or different answer? And why?

Answer 1

Yes, they are different because of the way that the TTH pattern is constructed to overlap previous unsuccessful patterns.

Consider only the TTH case where TT has occurred. There is a 1/2 probability that a third toss will yield H and complete the pattern. But notice that a 3rd toss of T doesn't "reset" the pattern matching, since TT remains the previous two matches. Thus, there is a 1/2 probability that a 4th will complete the pattern. And if doesn't, a 1/2 probability that a 5th will, ad nauseum.

Now consider THT where TH has occurred. There is a 1/2 probability of flipping a T and completing the pattern. And there is a 1/2 probability of flipping H which *resets* the pattern. Now HH are the previous two characters. There is 0 probability that a 4th flip will complete, and zero probability that a fifth flip will complete. There is 1/8 probability that THT will occur on the 6th flip.

This will occur anytime the last two characters are the same in one pattern and not in the other.

UPDATE:

I should have pointed out that the reason the TTH pattern will succeed sooner and more often is because, given a sequence of more than a few tosses, there will be more opportunities for TTH to succeed than there will be for THT, even though the probability of success (given an opportunity) is the same at 1/2.

Answer 2

Before tossing any coins, the probability that THT will appear before TTH is 0.5.  All possible equal length combinations of Ts and Hs have an equal probability of happening before any coin is thrown.

Answer 3

There are two different questions and you are not making proper distinction. The difference is like this. In the first part of your problem (and in my problem), the two sequences are competing with each other. i.e. If THH appears, then you stop and THT never gets a chance to appear. And vice versa.

In the second part of your problem, they are competing individually. e.g. if you are trying to find how many tosses to get THT and you get

THHTHT

you would conclude that your answer is 6. But in the first part of the problem you would have stopped after 3 and never got to 6. THAT's the distiction you failed to make.

In your original problem if THT and THH are competing with each other, then you are guaranteed a result the first time you get TH. The next toss gives you either an H or T and ends the sequence. That's how the wording of your question led me to interpret it. If they are competing individually, then the average number of tosses will be different for each of them.

Anyway, to answer your latest question. Without going into the math, the expected number N of tosses for each combination (COMPETING INDIVIDUALLY) is shown below.

N(THT) = 10

N(TTH) = 8

N(THH) = 8

N(TTT) = 14

If THT and THH are competing with each other, and we stop whenever we get ONE of them, then

N(THT or THH whichever comes first) = 5

as I worked out in your previous question.