ET News & Sponsor Info
General Topics
Markets
Technical Topics
Brokerage Firms
Company Specific
Tools of the Trade
Trading for a Living
Community Lounge
Site Support

# Probability of 5+ consecutive heads in 20 coin tosses

Discussion in 'Automated Trading' started by blueraincap, Oct 25, 2019.

1. ### blueraincap

It's possible to work this out, though time consuming:

- work out how many possible sequences of heads and tails there are (2^20 = 1,048,576)
- work out how many of these contain runs of at least 5 heads (262,008)
- divide the second number by the first (0.2498699426030839)

Here's some python code that does this by counting in binary from 0 up to 2^20-1 and converting the resulting number into a coin flip sequence.

I also wrote this code which does the same thing but generates flips randomly. This could be useful if you're looking at very large sequences, are happy with an approximation, and don't want to blow up your computer.

GAT

Last edited: Oct 25, 2019
TooEffingOld, VPhantom, yg10 and 3 others like this.
3. ### elt894

To get 26.6% I assume you're doing 1/2^5 + 15*(1/2)^6. The problem with that is it double counts sequences that have two separate 5+ runs.

I have a non brute force approach that agrees with GAT's (though there are 262008 sequences that contain 5+ runs, not 524105). I can post it this evening if you want it.

Quite right, edited my post.

GAT

5. ### notagain

bpr likes this.
6. ### panzerman

Real world distributions have skew and kurtosis. Add some positive skew and assume some leptokurtosis, and then do the calculation again.

7. ### blueraincap

You are right, it is 25% after eliminating 1 of the previously double-counted sequence (at the very beginning or end)

8. ### Turveyd

1 in 32 rolling 5 in a row, but it's got to start before / at 16, which means 50% chance of it happening.

9. ### elt894

Here's a script that works iteratively on increasingly long sequences. It looks like a closed form solution is possible, but my algebraic combinatorics is too rusty.

Code:
```import numpy as np

flips      = 20 # total number of coin flips
run_length = 5  # minimum number of heads in a row

# comments below assume run_length == 5

# a[i] is the number of sequences of length i that have a run of 5 heads
a = np.zeros(flips + 1)

# N[i] is the total number of sequences of length i
N = 2**np.arange(flips + 1)

# b[i] is the number of sequences of length i that do not have a full run
# but end in 4 heads
b = np.zeros(flips + 1)
b[run_length - 1] = 1

# fill in the arrays iteratively
for i in range(run_length, flips + 1):
# Each sequence of length i - 1 with a valid run generates two sequences with runs on the ith flip
# Also, each sequence of length i - 1 without a run but ending in 4 heads
# generates one sequence with a run of 5 heads on the ith flip
a[i] = a[i - 1]*2 + b[i - 1]

# The number of sequences of length i not containing a run of 5 but ending in 4 heads
# is just the number of sequences of length (i - 5) that don't contain a run,
# because each of these can be followed by one tails and 4 heads
b[i] = N[i - run_length] - a[i - run_length]

print("%f%% of sequences of length %d have runs of at least %d heads (%d out of %d)" % (
100.*a[-1]/N[-1],
flips,
run_length,
a[-1],
N[-1]
))
```

That double counts runs of 6+ heads, or sequences with two separate 5+ runs. Following that logic, a sequence of 100 flips would have a 300% chance.

blueraincap likes this.
10. ### BlueWaterSailor

Tisk, tisk. You guys. Didn't you forget something?

#10     Oct 25, 2019
ET IS FREE FOR TRADERS BECAUSE OF THE FINANCIAL SUPPORT FROM THESE SPONSORS: