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

Home > Probability
Many heads (Posted on 2004-12-13) Difficulty: 3 of 5
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.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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information