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.)
Solution solution | Comment 1 of 6

We start by finding the number of tosses expected to be necessary to get 1 head, and then base successive values on the preceding values of n.

The expected number of tosses to get 1 heads in a row is 2. This is based on a probability of 1/2 of getting heads on the first try, the probability of (1/2)^2 of requiring exactly 2 tries, (1/2)^3 of hitting the first heads at exactly 3 tries, etc., so E(1)= 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ..., as each probablity is multiplied by the length value to add into the expected value.

That this is equal to 2 can be shown:
x =      1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ...
2x = 1 + 2/2 + 3/4 + 4/8 + 5/16 + 6/32 + ...
then subtracting the top from the bottom equation:
x = 1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ...,
which equals 2.

To go from E(k) to E(k+1):
To get k+1 heads in a row, first you must get k heads in a row, and even then there's only a 1/2 probability of extending this to k+1.  So the probability of getting it on the first such try is 1/2, and the expected length of that is E(k)+1. But the probability of getting k+1 at the second go-round of k is 1/4, and the expected length in that event is 2*E(k)+2 (the added 2 representing the tails after the first k-in-a-row heads and the additional heads at the end).

So E(k+1) = (E(k)+1)/2 + (2*E(k)+2)/4 + (3*E(k)+3)/8 + (4*E(k)+4)/16 + ...

But this is E(k)/2 + 2*E(k)/4 + 3*E(k)/8 + 4*E(k)/16 + ... + 1/2 + 2/4 + 3/8 + 4/16 + ..., which, by the derivation above, is 2*E(k) + 2.

Tabulating expected values, it will be helpful to express them not only in decimal, but also in binary:

1  2 10
2  6 110
3 14 1110
4 30 11110
5 62 111110

You see that multiplying by 2 just shifts the binary representation one position to the left, leaving two zeros at the end, to which binary 10 (decimal 2) is added, creating a string of n 1's and a zero.

But that number is always 2^(n+1) - 1 - 1 = 2^(n+1) - 2.

So E(n) = 2^(n+1) - 2.

The following program simulates the process, and verifies the result:

RANDOMIZE TIMER
FOR n = 1 TO 6
  tot = 0: tr = 0
  FOR trial = 1 TO 100000
    tr = tr + 1
    toss = 0: heads = 0
    DO
     toss = toss + 1
     IF RND(1) > .5 THEN
      heads = heads + 1
      IF heads = n THEN EXIT DO
     ELSE
      heads = 0
     END IF
    LOOP
    tot = tot + toss
  NEXT
  PRINT n, tot / tr
NEXT

where one run results in:

1             1.99374
2             6.00678
3             14.06445
4             30.06876
5             61.8773
6             126.0582

  Posted by Charlie on 2004-12-13 19:44:06
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 (8)
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