Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I keep tossing a fair coin until I see HTHT appears. What is the probability that I have already observed the sequence TTH before I stop?

Edit:

Okay. This problem is the same as before. I am trying to think of the following. Could anyone please tell me if this is also the same as before, and if not, how to solve it.

Two players A and B toss two different fair coins. A tosses his coin until he sees HTHT appearing for the first time, and records the number of tosses, $X$. B tosses his coin until he sees TTH appearing for the first time, and records the number of tosses made, $Y$. What is the probability that $Y<X$?

share|improve this question
3  
This question is much in the same flavor as both math.stackexchange.com/questions/18093/… and math.stackexchange.com/questions/18405/…; it seems you are not really following the answers you got then, since similar approaches should work here as well... –  Arturo Magidin Feb 4 '11 at 21:49
    
In fact, isn't this question equivalent to "I keep tossing a fair coin until I see HTHT or TTH appear. What is the probability that I got TTH?" Then exactly the same approach as in the second question Arturo links to will work. –  Mike Spivey Feb 4 '11 at 21:52
    
guys, don't be mad at me. I do not see how this question is the same or can be solved the same way as other questions I posted. This is of a much different flavor, if I am not mistaken. –  Qiang Li Feb 4 '11 at 22:08
    
@Qiang: See Mike's comment: it is equivalent to the previous question: assign one pattern to one player, the other pattern to the other player, and compute the probability that the player with the pattern TTH won. I'm not mad, but it really does seem that you aren't really understanding the ideas of the answers you have already "accepted" for other questions. There's little point to the site if you all you want is answers you don't understand. –  Arturo Magidin Feb 4 '11 at 22:09
    
@Mike: the question "I keep tossing a fair coin until I see HTHT or TTH appear. What is the probability that I got TTH?" is different from this one since this one is asking: when stopped with the appearance of the first pattern, we are asking for the prob. of the second pattern also appearing. –  Qiang Li Feb 4 '11 at 22:11
show 8 more comments

2 Answers

up vote 2 down vote accepted

By the standard techniques explained here in a similar context, one can show that the first time $T_A$ when the word A=HTHT is produced has generating function $$ E(s^{T_A})=\frac{s^4}{a(s)},\qquad a(s)=(2-s)(8-4s-s^3)-2s^3, $$ and that the first time $T_B$ when the word B=TTH is produced has generating function $$ E(s^{T_B})=\frac{s^3}{b(s)},\qquad b(s)=(2-s)(4-2s-s^2), $$ The next step would be to develop these as series of powers of $s$, getting $$ E(s^{T_A})=\sum_{n\ge4}p_A(n)s^n,\quad E(s^{T_B})=\sum_{k\ge3}p_B(k)s^k, $$ and finally, to compute the sum $$ P(T_B<T_A)=\sum_{k\ge3}\sum_{n\ge k+1}p_B(k)p_A(n). $$ An alternative solution is to consider the Markov chain on the space of the couples of prefixes of the words A and B and to solve directly the associated first hitting time problem for this Markov chain, as explained, once again, here.

(+1 to Arturo's and Mike's comments.)

Added later Introduce the decomposition into simple elements $$ \frac1{(1-s)b(s)}=\sum_{i=1}^4\frac{c_i}{1-s\gamma_i}. $$ Then, one can show that $$ P(T_B<T_A)=\sum_{i=1}^4\frac{c_i}{a(\gamma_i)}, $$ by decomposing the rational fractions $1/b(s)$ and $1/a(s)$ into simple elements, by relying on the fact that all their poles are simple, and by using some elementary algebraic manipulations.

At this point, I feel it is my duty to warn the OP that to ask question after question on math.SE or elsewhere along the lines of this post is somewhat pointless. Much more useful would be to learn once and for all the basics of the theory of finite Markov chains, for instance by delving into the quite congenial Markov chains by James Norris, and, to learn to manipulate power series, into the magnificent generatingfunctionology by Herbert Wilf.

share|improve this answer
    
@Didier: many thanks! I got the same generating functions. But it looks like that the double summation is still intractable, unless you can please teach me something more. –  Qiang Li Feb 5 '11 at 17:39
    
@Didier: thanks for the completed answer, and the warning too. –  Qiang Li Feb 5 '11 at 22:19
    
@Didier, I looked at the book by Herbert Wilf, but did not find where it talked about converting the double summation the way you did here. I only found one place he talked about partial fractions, but it is unlike what you did here. Would you please give me some more hint on how to get $$P(T_B \lt T_A)=\sum_{i=1}^4{\frac{c_i}{a(\gamma_i)}}$$? Many thanks again! –  Qiang Li Feb 6 '11 at 7:02
    
@Qiang Did you find a proof that $E(s^{T_A})$ and $E(s^{T_B})$ where as written in my post? After that, did you deduce from these expressions some formulas for $p_B(k)$ and $p_A(n)$? Hint: you can use the fact that the polynomials $a$ and $b$ have only simple roots without actually computing the values of these roots, like I did for the inverse of $(1-s)b(s)$. If you do all that, and if you remember what the sum of a geometric series is (and I am sure you do), the Graal will not be far away from your grasp... –  Did Feb 6 '11 at 10:09
    
Oops: were as written. –  Did Feb 6 '11 at 10:19
show 5 more comments

This answer addresses the question as originally posted; I made it a community wiki because it is really an extended comment that would not have fit as a comment.

The previous question asked, inter alia, the following: given a two-sided coin with probability $p$ of showing heads, and the coin is tossed until either HTHTH or HTHH appears, how to compute the probability that the pattern we got was HTHTH.

Mike Spivey's answer cast the problem as a two-player game, in which one player wins if the first pattern to show up is HTHTH, and the second player wins if the pattern that shows up first is HTHH, and showed how to obtain the probability that either the first player wins, or the second player wins.

The current problem has a fair coin, and asks that the coin be tossed until a particular pattern, HTHT, shows up, and then asks what is the probability that another pattern, TTH, actually occurs before HTHT shows up.

Think of this problem as a two-player game again: the coin is tossed, until either HTHT or TTH show up. The first player wins if HTHT shows up first, the second if TTH shows up first. The exact same approach as used in the previous question works here to obtain the probability that the second player wins, i.e., the probability that TTH will show up first.

Now, you state in comments that you don't see this problem as the same as that game, because in this problem you keep tossing until HTHT appears, instead of stopping if TTH shows up. Well, take the game described above, and then imagine that the two players are utterly bored and so, if player two wins, they keep tossing the coin until HTHT shows up. Will that change the probability that the second player wins? No. The second player still wins if TTH shows up first, regardless of whether you keep tossing the coin or not after he wins. So the probability that TTH showed up at least once before you hit HTHT is the same, whether you keep tossing after TTH shows up or not, because the number of sequences in which TTH shows up but HTHT never does is negligible, so it will not affect the probability. (The probability that a particular finite pattern never shows up is $0$).

So in the end, the answer to your question is still "the probability that TTH showed up before HTHT shows up is equal to the probability that Player Two wins the game".

share|improve this answer
    
let me think about this thoroughly. Thanks for the detailed writeup. I understood completely how to calculate the competing patterns in previous posts; if this problem is the same as before, that is great. :) –  Qiang Li Feb 4 '11 at 22:31
    
I have changed my original post a bit. Please let me know your thoughts. Many thanks. –  Qiang Li Feb 4 '11 at 23:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.