Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Nov 23, 2013

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.


10 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