A harder problem is to find the expected number of times you must toss a fair coin until you get the consecutive sequence heads, tails, heads.
The following program simulates this:
tot = 0: tr = 0
FOR trial = 1 TO 1000000
tr = tr + 1
toss = 0
ppR = 0: pR = 0: rslt = 0
ppR = pR
pR = rslt
toss = toss + 1
rslt = INT(RND(1) * 2)
IF ppR = 1 AND pR = 0 AND rslt = 1 THEN EXIT DO
tot = tot + toss
PRINT tot, tr, tot / tr
and in a couple of runs, of 1 million trials each, got average number of tosses needed as 10.00433 and 9.991598, hinting that the expectation might be 10.
To get an analytic solution, we need to do a Markov chain of the possible states of the system. There are four significant states: having achieved HTH, having the previous two tosses be HT, having the previous toss be T not immediately preceded by a H (or the initial state of no tosses), and previous toss being H (but not HTH).
Once having achieved HTH, it stays in that state, and HT has 1/2 probability of becoming HTH. HT also has 1/2 probability to become T (i.e., TT). The T state has 1/2 probability to stay in that state and 1/2 probability to become the H state. The H state has 1/2 probability to stay in that state and 1/2 probability of becoming HT.
The following UBASIC program tracks successive generations of the Markov chain. Heads is designated "one" and tails, "zero". A separate track is kept of WinNow, referring to having achieved HTH (101) exactly on this turn. That is multiplied by the turn number to add into the expected value. Ng stands for next generation.
5 point 14
20 for I=1 to 10000
84 if I=10 or I=100 or I=1000 or I=10000 then
85 :print I,Expect
As the expected value is being built, progress is tabulated after 10, 100, 1000 and 10,000 tosses:
So this infinite sum does indeed seem to be converging to 10.
This is a shorter expected time than that for three heads, which had been calculated as 2^4 - 2 = 14. This can be understood in terms of, for example, how many ways provide for success within the first four tosses: for HHH they have to be either HHHH, THHH or HHHT; for HTH it can be HTHH, HTHT, TTHT or HTHT.
Edited on December 15, 2004, 2:24 pm
Posted by Charlie
on 2004-12-15 14:08:14