A coin is biased with P(heads)=p.
What is the expected number of flips to get n consecutive heads?
For a fair coin, here is the original Many Heads.
p=1/3;
cHad=zeros(1,7);
for trial=1:1000000
had=zeros(1,7);
toss=0; noHad=0;
while had(7)==0
r=rand;
toss=toss+1;
if r<p
noHad=noHad+1;
if had(noHad) == 0
had(noHad) = toss;
cHad(noHad)=cHad(noHad)+toss;
end
else
noHad=0;
end
end
end
cHad=cHad/trial;
for i=1:7
disp([i cHad(i)])
end
finds after a million trials, the average number of tosses to get n in a row when p = 1/3 are:
n number of tosses
1 3.001766
2 12.000364
3 39.002595
4 119.839147
5 362.422748
6 1089.524599
7 3279.016219
Looking up 3, 12, 39, 120 in the OEIS we find A029858, a(n) = (3^n - 3)/2, leading to conjecture that E(n) = (1/p^n - 1/p) / 2.
For a fair coin (p = 1/2) we'd predict (2^n - 2) / 2 = 2^(n-1) - 1. But
n number of tosses (2^n - 2) / 2
1 2.00201 0
2 6.0366 1
3 13.92041 3
4 29.87251 7
5 61.89579 15
6 125.83007 31
7 255.76048 63
Perhaps the 2 in the denominator is actually 3-1. Then it would be 2-1 for the case of p = 1/2:
n number of tosses formula
1 2.0012 -1
2 6.02266 0
3 14.04181 2
4 30.03818 6
5 62.24075 14
6 126.41717 30
7 253.84761 62
Looks like we're getting the expected value for n-2. So instead of (1/p^(n-1) - 1/p) / (1/p - 1), try (1/p^(n+1) - 1/p) / (1/p - 1)
1 2.00426 2
2 5.98119 6
3 13.98262 14
4 29.94804 30
5 61.61188 62
6 125.33954 126
7 252.61914 254
OK, that works for p=1/2, what about back at p=1/3?:
1 3.01046 3
2 12.02261 12
3 39.25753 39
4 120.55419 120
5 365.10167 363
6 1092.11087 1092
7 3283.99898 3279
It still fits. For good measure, p=1/4:
1 3.99144 4
2 19.9314 20
3 83.80132 84
4 340.25499 340
5 1361.95732 1364
6 5473.16279 5460
7 21882.14931 21844
Well another, p = 1/5 (this time we'll leave out n=7; that'd take too long):
1 5.00394 5
2 30.04088 30
3 154.90385 155
4 779.05481 780
5 3897.8722 3905
6 19593.49331 19530
It looks like (1/p^(n+1) - 1/p) / (1/p - 1) is it.
Waiting for 7 would be expected to take 97655 trials, and we were trying 100,000 trials (down from a million for the smaller probabilities) each of these test runs. If we had been waiting to get 7, we'd have been waiting 9,765,500,000 tosses (expected).
|
|
Posted by Charlie
on 2021-08-02 13:36:56 |
trial and error with the computer
