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.
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.
Is there a typo? I guess the last word ("HHTHHTT"), should be HH TH HT TT ?
ReplyDeleteNo typo. Its a length 7 string. That's what makes the problem interesting :)
DeleteThis comment has been removed by the author.
ReplyDeleteQuick attempt: Is the answer 512?
ReplyDeleteLet 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.
Is the answer ~20.789?
ReplyDeleteI'm getting 2^(14)/255 = 64 + 64/255, i.e. about 64.25
ReplyDelete[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.
Just a try : Is it 13 flips ??
DeleteCan i know when and how do i get to know the right answer ?? Sorry, i am new to this blog.
DeleteIs it 254?
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteHere 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.
ReplyDeleteLets 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.
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.
Delete67
ReplyDeleteLet 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.
I'm getting 29 steps
ReplyDeletemade a markov chain consisting of 5 states, start->HH->TH->HT->finish(TT or TH)
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
ReplyDeleteThe 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.
ReplyDeleteCan you elaborate on your approach?
DeleteThe answer is 256
ReplyDelete