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 run
• p — probability of tossing heads
• u[n] — a success run (first or subsequent) of length r occurs at trial n
• f[n] — the first success run of length r occurs at trial n
• s[n] — at least one success run of length r occurs at or before trial n

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