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.)
 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 102  6 1103 14 11104 30 111105 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
IF heads = n THEN EXIT DO
ELSE
END IF
LOOP
tot = tot + toss
NEXT
PRINT n, tot / tr
NEXT

where one run results in:

`1             1.993742             6.006783             14.064454             30.068765             61.87736             126.0582`

 Posted by Charlie on 2004-12-13 19:44:06

 Search: Search body:
Forums (0)