Day 85: Coin success runs
What is the probability to see a success run of 10 heads if we toss a fair coin thousand times?
You might be tempted to answer 1/2¹⁰, but this problem is really non-trivial. Such an intuitive [mis]understanding of probability is often source of gambler’s fallacy.
Derivation and proof of the correct answer is way beyond this series. In this case I will only show a general solution and provide its implementation.
I would also like to express my gratitude to professor Santosh S. Venkatesh. His excellent lectures and book helped me to understand probability and statistics.
Let’s denote
r
— length of success runp
— probability of tossing headsu[n]
— a success run (first or subsequent) of lengthr
occurs at trialn
f[n]
— the first success run of lengthr
occurs at trialn
s[n]
— at least one success run of lengthr
occurs at or before trialn
To get an answer for the question I laid, we set r=10
, p=.5
and find s[1000]
. List of probabilities below gives the answer. Probability to see a success run of 10 heads within thousand tosses is 39%.
https://github.com/coells/100days
https://notebooks.azure.com/coells/libraries/100days
algorithm
def probability(n, k, p, all_probs=False):
F = np.zeros(n + 1)
U = np.zeros(n + 1)
R = np.float_power(p, np.arange(k + 1)) for i in range(k, n + 1):
U[i] = R[k] - R[1:k] @ U[i-k+1:i][::-1]
F[i] = U[i] - F[1:i] @ U[1:i][::-1] S = F.cumsum() return S if all_probs else S[-1]
run
n = 1000
print(n, 'tosses; probability to see at least ...')
for k in range(1, n + 1):
p = probability(n, k, .5)
print('%dx HEADS in row = %.4f' % (k, p))
if p < 1e-4:
break>>>1000 tosses; probability to see at least ...
1x HEADS in row = 1.0000
2x HEADS in row = 1.0000
3x HEADS in row = 1.0000
4x HEADS in row = 1.0000
5x HEADS in row = 1.0000
6x HEADS in row = 0.9997
7x HEADS in row = 0.9818
8x HEADS in row = 0.8611
9x HEADS in row = 0.6242
10x HEADS in row = 0.3854
11x HEADS in row = 0.2154
12x HEADS in row = 0.1140
13x HEADS in row = 0.0586
14x HEADS in row = 0.0297
15x HEADS in row = 0.0150
16x HEADS in row = 0.0075
17x HEADS in row = 0.0038
18x HEADS in row = 0.0019
19x HEADS in row = 0.0009
20x HEADS in row = 0.0005
21x HEADS in row = 0.0002
22x HEADS in row = 0.0001
23x HEADS in row = 0.0001