**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.

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?

ReplyDelete64?

ReplyDelete