# Probability of at least one k-length run of heads in n coin flips

Question says it all - the flips are uniform, independent events that can be Heads or Tails. My strategy has been to find the probability of having no k-length runs of heads in n flips, and take 1 minus that. I think the solution has to do with recursion/induction, but I’m not sure exactly how it works...

• Well, a (sufficiently long) good string must end in one of $T, TH, TH^2, \cdots, TH^{k-1}$ so you can get a recursion. (Note: here a "good" string is one without a string of at least $k$ consecutive Heads). – lulu May 16 '18 at 20:12

The probability of any particular outcome of heads and tails in n flips is $0.5^n$. The number of outcomes is $\frac{1}{0.5^n}$. Obviously $0.5^n\cdot \frac{1}{0.5^n}=1$ so the probability of not getting a single k length run of heads is:

$$1 - (n-(k-1))0.5^n$$ Where $(n-(k-1))$ is the number of ways to get a k length run of heads in n flips.

In considering more than one run of k heads where k is considerably smaller than n, we add in extra terms to subtract from 1 until a maximum possible number of k runs is reached. The following is the probability for one and two runs of k. Another series of terms is required for the probability of more than two runs of k.

$$1 - (n-(k-1))0.5^n - ((n-(k+1))-(k-1))0.5^n - ((n-(k+2))-(k-1))0.5^n..........(1)0.5^n$$