CSE Blog - quant, math, computer science puzzles

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

This comment has been removed by the author.

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.

Is the answer ~20.789?

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.

Is it 254?

This comment has been removed by the author.

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.

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.

I'm getting 29 steps

made 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

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.

The answer is 256