All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

What is the expected number of times you must toss a (fair) coin until you get n consecutive heads?

 See The Solution Submitted by e.g. Rating: 4.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 A harder problem | Comment 3 of 6 |

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.775390625100     9.99971252013595434930168411738809132184716150076356189994181145053171000    9.999999999999999999999999999999999999999999999999999997895062444062610000   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

 Search: Search body:
Forums (0)