An exact answer to the problem can be computed using dynamic programming; reframe the problem from calculating the probability, into counting the number of sequences of length
n which don’t contain any streak of
k in a row. The probability of getting no streaks of length
k or more is that number divided by
2**n; of course, if you want the probability of getting at least one streak, you can subtract that result from 1. This gives an exact probability (subject to floating point precision), rather than an estimate by sampling.
The algorithm works by maintaining a “state” which is a list of the current number of sequences ending with a streak of length
r is the index in the list, ranging from 0 to
k - 1 where
k is the forbidden streak length. To update the state, each current streak can either be broken by a “different” flip, resulting in a new streak of length 1, or it can be continued by a “same” flip, resulting in a new streak of length
r + 1. We should only count “continued” streaks if the resulting streak length is less than
k. The initial state has a single streak of length 0, because no flips have been made yet.
Here’s an implementation:
def probability_of_no_runs(n, k): state =  +  * (k-1) for i in range(n): new_state =  * k for r, c in enumerate(state): new_state += c if r < k - 1: new_state[r + 1] += c state = new_state return sum(state) / 2**n
>>> probability_of_no_runs(10, 3) 0.173828125 >>> probability_of_no_runs(100, 6) 0.19317945128367534 >>> probability_of_no_runs(100, 10) 0.9133409556516383
By viewing the state transition as a linear transformation, it’s possible to improve on this algorithm by writing the whole thing as a matrix product
A**n * s where
A is the transition matrix and
s is the initial state. This could be more efficient because the matrix power can be computed in
log n steps instead of
n steps as this loop uses.
The algorithm above could also be adapted to count the distribution of how many streaks occur; in that case, the state should be a two-dimensional grid where one index is the current streak length and the other index is the number of streaks so far. You would need to decide what to do about overlapping streaks.