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:
RANDOMIZE TIMER
DEFDBL A-Z
tot = 0: tr = 0
FOR trial = 1 TO 1000000
tr = tr + 1
toss = 0
ppR = 0: pR = 0: rslt = 0
DO
ppR = pR
pR = rslt
toss = toss + 1
rslt = INT(RND(1) * 2)
IF ppR = 1 AND pR = 0 AND rslt = 1 THEN EXIT DO
LOOP
tot = tot + toss
NEXT
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
10 Zero=1
20 for I=1 to 10000
30 NgWin=1/2*OneZero+NgWin
35 NgWinNow=1/2*OneZero
40 NgOneZero=1/2*One
50 NgZero=1/2*Zero+1/2*OneZero
60 NgOne=1/2*One+1/2*Zero
70 Win=NgWin:WinNow=NgWinNow
80 Zero=NgZero:OneZero=NgOneZero:One=NgOne
81 Expect=Expect+I*WinNow
84 if I=10 or I=100 or I=1000 or I=10000 then
85 :print I,Expect
90 next
As the expected value is being built, progress is tabulated after 10, 100, 1000 and 10,000 tosses:
10 3.775390625
100 9.9997125201359543493016841173880913218471615007635618999418114505317
1000 9.9999999999999999999999999999999999999999999999999999978950624440626
10000 9.9999999999999999999999999999999999999999999999999999999999999630028
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 |
A harder problem
