Two Coin Tossing Puzzle - Expected Number of Tosses

Source: Mailed to me by Vashist Avadhanula (PhD Student at Columbia Business School, EE IITB 2013 Alumnus)

Problem:
Consider a case where you flip two fair coins at once (sample space is HH, HT, TH & TT) you repeat this experiment many times and note down the outputs as a sequence. What is the expected number of flips (one flip includes tossing of two coins) to arrive at the sequence HHTHHTT.


Comments

  1. Is there a typo? I guess the last word ("HHTHHTT"), should be HH TH HT TT ?

    ReplyDelete
    Replies
    1. No typo. Its a length 7 string. That's what makes the problem interesting :)

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Quick attempt: Is the answer 512?
    Let S be the string HHTHHTT?. Then S = HHTHHTTT with prob 1/2 and S = HHTHHTTH with prob 1/2. So we have S = HHTHHTT? with prob (1/2)^7. Let X be the expected number of tosses (with each toss being the toss of both coins). Then we have X = 4*(1/2)^7 + (X + 4)*(1 - (1/2)^7) as if we don't get HHTHHTT? first time round we have X agin with an addition 4 tosses where we weren't successful. Rearranging S we get 512.

    ReplyDelete
  4. I'm getting 2^(14)/255 = 64 + 64/255, i.e. about 64.25

    [Warning -- I really should latex this, but I'm inclined to do it quickly in pseudo-latex. Maybe I'll clean it up later]

    If I understand the question correctly [when two coins are tossed simultaneously, the result
    of coin A is always written before the result of coin B, i.e. you don't get to choose whether to write
    HT or TH when one coin lands heads and one langs tails. Also I assume if you OVERSHOOT
    the sequence [i.e. you've rolled HH TH HT on the first 3 rolls, and then roll TH you'd say "we've arrived
    at the sequence HHTHHTT in 4 rolls even though we actually went past it. with an extra T]]

    Let S stand for the sequence HHTHHTT

    I think it's easier to describe the idea than write it out, certainly than to write it out in ASCII -- it's just a markov chain with about 7 states (8 including the finished state), based on the length of the current longest initial segment of S that you can form from the most recent rolls (i.e. working backward from the roll you are about to make). Once you have that, there are various ways to solve for the expected value, maybe the simplest to describe is the system of linear equations for the expected value until arrival from state n.

    That is, in more detail:

    State 0: [state before first role, or state when most recent rolls are not an initial segment of string S]
    results of rolling in this state: 1/2 chance remain in state 0 (roll TT or HT); 1/4 chance chance of state 1 (TH);
    1/4 chance of state 2 (HH)

    State 1: the longest initial segement of S in the previous rolls is -H
    results of rolling in this state: 1/4 chance state 0 (TT); 1/4 chance state 1 (TH); 1/4 chance state 2 (HH); 1/4 chance state 3 (HT)

    State 2: previous rolls longest initial segment of S is -HH
    results of rolling in this state: 1/4 chance state 0 (TT);1/4 chance state 2 (HH);1/4 chance state 3 (HT);1/4 chance state 4 (TH)

    State 3: previous rolls longest initial segment of S is -HHT
    results of rolling in this state: 1/2 chance state 0 (TT, HT); 1/4 chance state 1 (TH);1/4 chance state 5 (HH)

    State 4: previous rolls longest initial segment of S is -HHTH
    results of rolling in this state: 1/4 state 0 (TT); 1/4 state 1 (TH);1/4 state 2 (HH);1/4 chance state 6 (HT)

    State 5: previous rolls longest initial segment of S is -HHTHH
    results of rolling in this state: 1/4 chance state 2 (HH);1/4 chance state 3 (HT);1/4 chance state 4(TH);1/4 chance FINISH! (TT)

    State 6: previous rolls longest initial segment of S is -HHTHHT
    results of rolling in this state: 1/4 chance state 0 (HT);1/4 chance state 5 (HH);1/2 chance FINISH (TH or TT)

    So if E_n is the expected number of flips to finish if in state n
    E_0=1+ 1/2 * E_0 + 1/4*E_1 + 1/4*E_2
    E_1= 1+1/4 * E_0 + 1/4*E_1 + 1/4*E_2 + 1/4*E_3
    E_2= 1+1/4 * E_0 + 1/4*E_2 + 1/4*E_3 + 1/4*E_4
    E_3=1+1/2 * E_0 + 1/4*E_1 + 1/4*E_5
    E_4=1 + 1/4 * E_0 + 1/4*E_1 + 1/4*E_2+ 1/4*E_6
    E_5= 1+ 1/4 * E_2 + 1/4*E_3 + 1/4*E_4 + 1/4*0
    E_6= 1+1/4 * E_0 + 1/4 * E_5 + 1/2*0
    seven linear equations in seven variables. There are undoubtably ways to simplify this, but I was happy just to type it into a spreadsheet and be done.

    ReplyDelete
    Replies
    1. Just a try : Is it 13 flips ??

      Delete
    2. Can i know when and how do i get to know the right answer ?? Sorry, i am new to this blog.

      Delete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Here usually any sequence should be of even length because I am seeing two coin tosses at one go, the question is asking the expected number to see an odd length sequence, so for finding the answer we need to find the expected number of coin tosses required to see the first one among H(HHTHHTT), T(HHTHHTT), (HHTHHTT)T, (HHTHHTT)H.
    Lets mark HH by 0, HT by 1, TH by 2, TT by 3

    Lets rephrase the problem to expected number of 4-sided die throws to get one of the following sequences:
    0103 2103 0213 0212 where probability of getting a 0,1,2,3 at any throw is 1/4

    This can be solved by drawing a state diagram and assigning probabilities.






    ReplyDelete
    Replies
    1. Please elaborate on your approach a bit more. I was thinking the same way until I realized this problem has four absorbing states, which means the usual approach to finding the expected time to an absorbing state in an MC is hard to apply. On the other hand, if you work out the transition matrix for the four new states, it will only give you the probabilities of future states rather than expected time.

      Delete
  7. 67
    Let S = HHTHHTT
    P(S) = P(aS) + P(Sa) = (1/2)^7 + (1/2)^7 = (1/2)^6 = (1/64)
    X = 4*(1/64) + 5*(63/64)*(1/64) + 6*(63/64)^2*(1/64) + . . .

    It may be solved using
    X = 4*(1/64) + (X+1)*(63/64)
    which gives X = 67.

    ReplyDelete
  8. I'm getting 29 steps

    made a markov chain consisting of 5 states, start->HH->TH->HT->finish(TT or TH)

    ReplyDelete
  9. i am getting 128 . firstly i used linearity of expectation on different states of the transition diagram . secondly i verified my answer through simulation it came out to be same

    ReplyDelete
  10. The answer is 64+64/255, as given by Ted in his solution. But, there is a shorter way to reach the answer using linearity of expectation and placing bets before every throw on the desired outcomes. One just needs to make sure that the bets are placed in such a way that the return is the same in all the 4 cases.

    ReplyDelete

Post a Comment