In another question the user was determining the probability of having a streak of 6 heads or 6 tails in 100 coin flips. To find the probability they would generate 100 random coin flips and determine if there was a streak. They would test 10,000 such sequences of 100 flips to find that there was about an 80% chance of there being a streak in 100 coin flips.
I decided to compute the exact probability. For 100 flips there are \$2^{100}\$ possible outcomes. To determine the percentage I compute how many of them have a streak, and then divide by \$2^{100}\$.
My naive solution gets me the number for 20 flips in few seconds:
from itertools import product
def naive(flips, streak):
return sum('h' * streak in ''.join(p) or
't' * streak in ''.join(p)
for p in product('ht', repeat=flips))
Result:
>>> naive(20, 6)
248384
My fast solution gets me the number for 100 flips instantly:
from collections import Counter
def fast(flips, streak):
needles = 'h' * streak, 't' * streak
groups = {'-' * streak: 1}
total = 0
for i in range(flips):
next_groups = Counter()
for ending, count in groups.items():
for coin in 'ht':
new_ending = ending[1:] + coin
if new_ending in needles:
total += count * 2**(flips - 1 - i)
else:
next_groups[new_ending] += count
groups = next_groups
return total
The idea is to have a pool of still ongoing games, but grouped by the last six flips, and counts for how often that group has appeared. Then do the 100 flips one at a time, updating the groups and their counts. Any group that at some point ends with a streak doesn't continue playing, instead I add it to the total result. The group occurred count
times, there are flips - 1 - i
flips left, and they can be anything, so multiply count
with 2flips - 1 - i.
Results (note that the result for 20 flips is the same as with the naive solution):
>>> fast(20, 6)
248384
>>> fast(100, 6)
1022766552856718355261682015984
And dividing by 2100 gives me the percentage similar to those of the linked-to experiments:
>>> 100 * fast(100, 6) / 2**100
80.68205487163246
Any comments, suggestions for improvement?