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 |
solution
