The original question was: Recently I’ve come across a task to calculate the probability that a run of at least K successes occurs in a series of N (K≤N) Bernoulli trials (weighted coin flips), i.e. “what’s the probability that in 50 coin tosses one has a streak of 20 heads?”. This turned out to be a very difficult question and the best answer I found was a couple of approximations.
So my question to a mathematician is: “Why is this task so difficult compared e.g. to finding the probability of getting 20 heads in 50 coin tosses solved easily using binomial formula? How is this task in fact solved – is there an exact analytic solution? What are the main (preferably simplest) approximations and why are they used instead of an analytic solution?”
Physicist: What follows was not obvious. It was the result of several false starts. It’s impressive in the same sense that a dude with seriously bruised legs, who can find anything in his house with the lights off, is also impressive. If you’re looking for the discussion of the gross philosophy, and not the detailed math, skip down to where you find the word “Jabberwocky” in bold. If you want specific answers for fixed, small numbers of coins, or you want sample computer code for calculating the answer, go to the bottom of the article.
The short answer: the probability, S, of getting K or more heads in a row in N independent attempts (where p is the probability of heads and q=1-p is the probability of tails) is:
Note that here 
Originally this was a pure math question that didn’t seem interesting to a larger audience, but we both worked for long enough on it that it seems a shame to let it go to waste. Plus, it gives me a chance to show how sloppy (physics type) mathematics is better than exact (math type) mathematics.
Define {Xi}j as the list of results of the first j trials. e.g., if j=4, then {Xi}j might be “{Xi}4=HTHH” or “{Xi}4=TTTH” or something like that, where H=heads and T=tails. In the second case, X1=T, X2=T, X3=T, and X4=H.
Define “Ej” as the event that there is a run of K successes (heads) in the first j trials. The question boils down to finding P(EN).
Define “Aj” as the event that the last K terms of {Xi}j are T followed by K-1 H’s ({Xi}j = X1X2X3X4…THHH…HHH). That is to say, if the next coin (Xj+1) is heads, then you’ve got a run of K.
Finally, define p = P(H) and q = P(T) = 1-p. Keep in mind that a “bar” over an event means “not”. So “
The probability of an event is the sum of the probabilities of the different (disjoint) ways that event can happen. So:
![\begin{array}{ll}&P(E_{j+1})\\i)&=P(E_{j+1}\cap E_j\cap A_j)+P(E_{j+1}\cap E_j\cap \overline{A_j})+P(E_{j+1}\cap \overline{E_j}\cap A_j)+P(E_{j+1}\cap \overline{E_j}\cap \overline{A_j})\\ii)&=\left[P(E_{j+1}\cap E_j\cap A_j)+P(E_{j+1}\cap E_j\cap \overline{A_j})\right]+P(E_{j+1}\cap \overline{E_j}\cap A_j)+P(E_{j+1}\cap \overline{E_j}\cap \overline{A_j})\\iii)&=\left[P(E_{j+1}\cap E_j)\right]+P(E_{j+1}\cap \overline{E_j}\cap A_j)+P(E_{j+1}\cap \overline{E_j}\cap \overline{A_j})\\iv)&=P(E_j)+P(E_{j+1}\cap \overline{E_j}\cap A_j)+P(E_{j+1}\cap \overline{E_j}\cap \overline{A_j})\\v)&=P(E_j)+P(E_{j+1}\cap \overline{E_j}\cap A_j)+0\\vi)&=P(E_j)+P(E_{j+1}|\overline{E_j}\cap A_j)P(\overline{E_j}\cap A_j)\\vii)&=P(E_j)+pP(\overline{E_j}\cap A_j)\\viii)&=P(E_j)+pP(\overline{E_j}| A_j)P(A_j)\\ix)&=P(E_j)+pP(\overline{E_j}| A_j)qp^{K-1}\\x)&=P(E_j)+qp^KP(\overline{E_{j-k}})\\xi)&=P(E_j)+qp^K\left[1-P(E_{j-k})\right]\\xii)&=P(E_j)+qp^K-qp^KP(E_{j-k})\end{array}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7Bll%7D%26P%28E_%7Bj%2B1%7D%29%5C%5Ci%29%26%3DP%28E_%7Bj%2B1%7D%5Ccap+E_j%5Ccap+A_j%29%2BP%28E_%7Bj%2B1%7D%5Ccap+E_j%5Ccap+%5Coverline%7BA_j%7D%29%2BP%28E_%7Bj%2B1%7D%5Ccap+%5Coverline%7BE_j%7D%5Ccap+A_j%29%2BP%28E_%7Bj%2B1%7D%5Ccap+%5Coverline%7BE_j%7D%5Ccap+%5Coverline%7BA_j%7D%29%5C%5Cii%29%26%3D%5Cleft%5BP%28E_%7Bj%2B1%7D%5Ccap+E_j%5Ccap+A_j%29%2BP%28E_%7Bj%2B1%7D%5Ccap+E_j%5Ccap+%5Coverline%7BA_j%7D%29%5Cright%5D%2BP%28E_%7Bj%2B1%7D%5Ccap+%5Coverline%7BE_j%7D%5Ccap+A_j%29%2BP%28E_%7Bj%2B1%7D%5Ccap+%5Coverline%7BE_j%7D%5Ccap+%5Coverline%7BA_j%7D%29%5C%5Ciii%29%26%3D%5Cleft%5BP%28E_%7Bj%2B1%7D%5Ccap+E_j%29%5Cright%5D%2BP%28E_%7Bj%2B1%7D%5Ccap+%5Coverline%7BE_j%7D%5Ccap+A_j%29%2BP%28E_%7Bj%2B1%7D%5Ccap+%5Coverline%7BE_j%7D%5Ccap+%5Coverline%7BA_j%7D%29%5C%5Civ%29%26%3DP%28E_j%29%2BP%28E_%7Bj%2B1%7D%5Ccap+%5Coverline%7BE_j%7D%5Ccap+A_j%29%2BP%28E_%7Bj%2B1%7D%5Ccap+%5Coverline%7BE_j%7D%5Ccap+%5Coverline%7BA_j%7D%29%5C%5Cv%29%26%3DP%28E_j%29%2BP%28E_%7Bj%2B1%7D%5Ccap+%5Coverline%7BE_j%7D%5Ccap+A_j%29%2B0%5C%5Cvi%29%26%3DP%28E_j%29%2BP%28E_%7Bj%2B1%7D%7C%5Coverline%7BE_j%7D%5Ccap+A_j%29P%28%5Coverline%7BE_j%7D%5Ccap+A_j%29%5C%5Cvii%29%26%3DP%28E_j%29%2BpP%28%5Coverline%7BE_j%7D%5Ccap+A_j%29%5C%5Cviii%29%26%3DP%28E_j%29%2BpP%28%5Coverline%7BE_j%7D%7C+A_j%29P%28A_j%29%5C%5Cix%29%26%3DP%28E_j%29%2BpP%28%5Coverline%7BE_j%7D%7C+A_j%29qp%5E%7BK-1%7D%5C%5Cx%29%26%3DP%28E_j%29%2Bqp%5EKP%28%5Coverline%7BE_%7Bj-k%7D%7D%29%5C%5Cxi%29%26%3DP%28E_j%29%2Bqp%5EK%5Cleft%5B1-P%28E_%7Bj-k%7D%29%5Cright%5D%5C%5Cxii%29%26%3DP%28E_j%29%2Bqp%5EK-qp%5EKP%28E_%7Bj-k%7D%29%5Cend%7Barray%7D&bg=ffffff&fg=000000&s=0 "\begin{array}{ll}&P(E_{j+1})\\i)&=P(E_{j+1}\cap E_j\cap A_j)+P(E_{j+1}\cap E_j\cap \overline{A_j})+P(E_{j+1}\cap \overline{E_j}\cap A_j)+P(E_{j+1}\cap \overline{E_j}\cap \overline{A_j})\\ii)&=\left[P(E_{j+1}\cap E_j\cap A_j)+P(E_{j+1}\cap E_j\cap \overline{A_j})\right]+P(E_{j+1}\cap \overline{E_j}\cap A_j)+P(E_{j+1}\cap \overline{E_j}\cap \overline{A_j})\\iii)&=\left[P(E_{j+1}\cap E_j)\right]+P(E_{j+1}\cap \overline{E_j}\cap A_j)+P(E_{j+1}\cap \overline{E_j}\cap \overline{A_j})\\iv)&=P(E_j)+P(E_{j+1}\cap \overline{E_j}\cap A_j)+P(E_{j+1}\cap \overline{E_j}\cap \overline{A_j})\\v)&=P(E_j)+P(E_{j+1}\cap \overline{E_j}\cap A_j)+0\\vi)&=P(E_j)+P(E_{j+1}|\overline{E_j}\cap A_j)P(\overline{E_j}\cap A_j)\\vii)&=P(E_j)+pP(\overline{E_j}\cap A_j)\\viii)&=P(E_j)+pP(\overline{E_j}| A_j)P(A_j)\\ix)&=P(E_j)+pP(\overline{E_j}| A_j)qp^{K-1}\\x)&=P(E_j)+qp^KP(\overline{E_{j-k}})\\xi)&=P(E_j)+qp^K\left[1-P(E_{j-k})\right]\\xii)&=P(E_j)+qp^K-qp^KP(E_{j-k})\end{array}")
iv) comes from the fact that 
The other steps are all probability identities (specifically 
Rewriting this with some N’s instead of j’s, we’ve got a kick-ass recursion:
And just to clean up the notation, define S(N,K) as the probability of getting a string of K heads in N trials (up until now this was P(EN)).
S(N,K)=S(N-1,K)+qpK-qpKS(N-K-1,K). We can quickly figure out two special cases: S(K,K) = pK, and S(l,K) = 0 when l<K, and that there’s no way of getting K heads without flipping at least K coins. Now check it:
![\begin{array}{ll}&S(N,K)\\i)&=S(N-1,K)+qp^K-qp^KS(N-K-1,K)\\ii)&=\left[S(N-2,K)+qp^K-qp^KS(N-K-2,K)\right]+qp^K-qp^KS(N-K-1,K)\\iii)&=S(N-2,K)+2qp^K-qp^K\left[ S(N-K-1,K)+S(N-K-2,K)\right]\\iv)&=S(N-3,K)+3qp^K-qp^K\left[ S(N-K-1,K)+S(N-K-2,K)+S(N-K-3,K)\right]\\v)&=S(N-(N-K),K)+(N-K)qp^K-qp^K\left[ S(N-K-1,K)+\cdots+S(N-K-(N-K),K)\right]\\vi)&=S(K,K)+(N-K)qp^K-qp^K\left[ S(N-K-1,K)+\cdots+S(0,K)\right]\\vii)&=p^K+(N-K)qp^K-qp^K\sum_{r=0}^{N-K-1} S(r,K)\\viii)&=p^k+(N-K)qp^K-qp^K\sum_{r=K}^{N-K-1} S(r,K)\end{array}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7Bll%7D%26S%28N%2CK%29%5C%5Ci%29%26%3DS%28N-1%2CK%29%2Bqp%5EK-qp%5EKS%28N-K-1%2CK%29%5C%5Cii%29%26%3D%5Cleft%5BS%28N-2%2CK%29%2Bqp%5EK-qp%5EKS%28N-K-2%2CK%29%5Cright%5D%2Bqp%5EK-qp%5EKS%28N-K-1%2CK%29%5C%5Ciii%29%26%3DS%28N-2%2CK%29%2B2qp%5EK-qp%5EK%5Cleft%5B+S%28N-K-1%2CK%29%2BS%28N-K-2%2CK%29%5Cright%5D%5C%5Civ%29%26%3DS%28N-3%2CK%29%2B3qp%5EK-qp%5EK%5Cleft%5B+S%28N-K-1%2CK%29%2BS%28N-K-2%2CK%29%2BS%28N-K-3%2CK%29%5Cright%5D%5C%5Cv%29%26%3DS%28N-%28N-K%29%2CK%29%2B%28N-K%29qp%5EK-qp%5EK%5Cleft%5B+S%28N-K-1%2CK%29%2B%5Ccdots%2BS%28N-K-%28N-K%29%2CK%29%5Cright%5D%5C%5Cvi%29%26%3DS%28K%2CK%29%2B%28N-K%29qp%5EK-qp%5EK%5Cleft%5B+S%28N-K-1%2CK%29%2B%5Ccdots%2BS%280%2CK%29%5Cright%5D%5C%5Cvii%29%26%3Dp%5EK%2B%28N-K%29qp%5EK-qp%5EK%5Csum_%7Br%3D0%7D%5E%7BN-K-1%7D+S%28r%2CK%29%5C%5Cviii%29%26%3Dp%5Ek%2B%28N-K%29qp%5EK-qp%5EK%5Csum_%7Br%3DK%7D%5E%7BN-K-1%7D+S%28r%2CK%29%5Cend%7Barray%7D&bg=ffffff&fg=000000&s=0 "\begin{array}{ll}&S(N,K)\\i)&=S(N-1,K)+qp^K-qp^KS(N-K-1,K)\\ii)&=\left[S(N-2,K)+qp^K-qp^KS(N-K-2,K)\right]+qp^K-qp^KS(N-K-1,K)\\iii)&=S(N-2,K)+2qp^K-qp^K\left[ S(N-K-1,K)+S(N-K-2,K)\right]\\iv)&=S(N-3,K)+3qp^K-qp^K\left[ S(N-K-1,K)+S(N-K-2,K)+S(N-K-3,K)\right]\\v)&=S(N-(N-K),K)+(N-K)qp^K-qp^K\left[ S(N-K-1,K)+\cdots+S(N-K-(N-K),K)\right]\\vi)&=S(K,K)+(N-K)qp^K-qp^K\left[ S(N-K-1,K)+\cdots+S(0,K)\right]\\vii)&=p^K+(N-K)qp^K-qp^K\sum_{r=0}^{N-K-1} S(r,K)\\viii)&=p^k+(N-K)qp^K-qp^K\sum_{r=K}^{N-K-1} S(r,K)\end{array}")
ii) Plug the equation for S(N,K) in for S(N-1,K). iii-vi) is the same thing. vii) write the pattern as a sum. viii) the terms up to K-1 are all zero, so drop them.
Holy crap! A newer, even better recursion! It seems best to plug it back into itself!
![\begin{array}{ll}i)&S(N,K)=p^K+(N-K)qp^K-qp^K\sum_{r=K}^{N-K-1} S(r,K)\\ii)&=p^K+(N-K)qp^K-qp^K\sum_{r=K}^{N-K-1} \left[p^k+(r-K)qp^K-qp^K\sum_{\ell=K}^{r-K-1} S(\ell,K)\right]\\iii)&=p^K+(N-K)qp^K-qp^K\sum_{r=K}^{N-K-1}p^k-qp^K\sum_{r=K}^{N-K-1}(r-K)qp^K+\left(qp^K\right)^2\sum_{r=K}^{N-K-1}\sum_{\ell=K}^{r-K-1} S(\ell,K)\\iv)&=p^K+(N-K)qp^K-qp^K\sum_{r=1}^{N-2K}p^k-\left(qp^K\right)^2\sum_{r=0}^{N-2K-1}r+\left(qp^K\right)^2\sum_{r=2K+1}^{N-K-1}\sum_{\ell=K}^{r-K-1} S(\ell,K)\\v)&=p^K+(N-K)qp^K-p^k(N-2K)qp^K-\left(qp^K\right)^2\frac{(N-2K)(N-2K-1)}{2}+\left(qp^K\right)^2\sum_{r=2K+1}^{N-K-1}\sum_{\ell=K}^{r-K-1} S(\ell,K)\\vi)&=p^K+{N-K\choose 1}qp^K-p^K{N-2K\choose 1}qp^K-{N-2K\choose 2}\left(qp^K\right)^2+\left(qp^K\right)^2\sum_{r=2K+1}^{N-K-1}\sum_{\ell=K}^{r-K-1} S(\ell,K)\end{array}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7Bll%7Di%29%26S%28N%2CK%29%3Dp%5EK%2B%28N-K%29qp%5EK-qp%5EK%5Csum_%7Br%3DK%7D%5E%7BN-K-1%7D+S%28r%2CK%29%5C%5Cii%29%26%3Dp%5EK%2B%28N-K%29qp%5EK-qp%5EK%5Csum_%7Br%3DK%7D%5E%7BN-K-1%7D+%5Cleft%5Bp%5Ek%2B%28r-K%29qp%5EK-qp%5EK%5Csum_%7B%5Cell%3DK%7D%5E%7Br-K-1%7D+S%28%5Cell%2CK%29%5Cright%5D%5C%5Ciii%29%26%3Dp%5EK%2B%28N-K%29qp%5EK-qp%5EK%5Csum_%7Br%3DK%7D%5E%7BN-K-1%7Dp%5Ek-qp%5EK%5Csum_%7Br%3DK%7D%5E%7BN-K-1%7D%28r-K%29qp%5EK%2B%5Cleft%28qp%5EK%5Cright%29%5E2%5Csum_%7Br%3DK%7D%5E%7BN-K-1%7D%5Csum_%7B%5Cell%3DK%7D%5E%7Br-K-1%7D+S%28%5Cell%2CK%29%5C%5Civ%29%26%3Dp%5EK%2B%28N-K%29qp%5EK-qp%5EK%5Csum_%7Br%3D1%7D%5E%7BN-2K%7Dp%5Ek-%5Cleft%28qp%5EK%5Cright%29%5E2%5Csum_%7Br%3D0%7D%5E%7BN-2K-1%7Dr%2B%5Cleft%28qp%5EK%5Cright%29%5E2%5Csum_%7Br%3D2K%2B1%7D%5E%7BN-K-1%7D%5Csum_%7B%5Cell%3DK%7D%5E%7Br-K-1%7D+S%28%5Cell%2CK%29%5C%5Cv%29%26%3Dp%5EK%2B%28N-K%29qp%5EK-p%5Ek%28N-2K%29qp%5EK-%5Cleft%28qp%5EK%5Cright%29%5E2%5Cfrac%7B%28N-2K%29%28N-2K-1%29%7D%7B2%7D%2B%5Cleft%28qp%5EK%5Cright%29%5E2%5Csum_%7Br%3D2K%2B1%7D%5E%7BN-K-1%7D%5Csum_%7B%5Cell%3DK%7D%5E%7Br-K-1%7D+S%28%5Cell%2CK%29%5C%5Cvi%29%26%3Dp%5EK%2B%7BN-K%5Cchoose+1%7Dqp%5EK-p%5EK%7BN-2K%5Cchoose+1%7Dqp%5EK-%7BN-2K%5Cchoose+2%7D%5Cleft%28qp%5EK%5Cright%29%5E2%2B%5Cleft%28qp%5EK%5Cright%29%5E2%5Csum_%7Br%3D2K%2B1%7D%5E%7BN-K-1%7D%5Csum_%7B%5Cell%3DK%7D%5E%7Br-K-1%7D+S%28%5Cell%2CK%29%5Cend%7Barray%7D&bg=ffffff&fg=000000&s=0 "\begin{array}{ll}i)&S(N,K)=p^K+(N-K)qp^K-qp^K\sum_{r=K}^{N-K-1} S(r,K)\\ii)&=p^K+(N-K)qp^K-qp^K\sum_{r=K}^{N-K-1} \left[p^k+(r-K)qp^K-qp^K\sum_{\ell=K}^{r-K-1} S(\ell,K)\right]\\iii)&=p^K+(N-K)qp^K-qp^K\sum_{r=K}^{N-K-1}p^k-qp^K\sum_{r=K}^{N-K-1}(r-K)qp^K+\left(qp^K\right)^2\sum_{r=K}^{N-K-1}\sum_{\ell=K}^{r-K-1} S(\ell,K)\\iv)&=p^K+(N-K)qp^K-qp^K\sum_{r=1}^{N-2K}p^k-\left(qp^K\right)^2\sum_{r=0}^{N-2K-1}r+\left(qp^K\right)^2\sum_{r=2K+1}^{N-K-1}\sum_{\ell=K}^{r-K-1} S(\ell,K)\\v)&=p^K+(N-K)qp^K-p^k(N-2K)qp^K-\left(qp^K\right)^2\frac{(N-2K)(N-2K-1)}{2}+\left(qp^K\right)^2\sum_{r=2K+1}^{N-K-1}\sum_{\ell=K}^{r-K-1} S(\ell,K)\\vi)&=p^K+{N-K\choose 1}qp^K-p^K{N-2K\choose 1}qp^K-{N-2K\choose 2}\left(qp^K\right)^2+\left(qp^K\right)^2\sum_{r=2K+1}^{N-K-1}\sum_{\ell=K}^{r-K-1} S(\ell,K)\end{array}")
You can keep plugging the “newer recursion” back in again and again (it’s a recursion after all). Using the fact that 
![\begin{array}{l}S(N,K)=p^K\left[1-{N-2K\choose 1}qp^K+{N-3K\choose 2}\left(qp^K\right)^2\cdots\right]+\left[{N-K\choose 1}qp^K-{N-2K\choose 2}\left(qp^K\right)^2+{N-3K\choose 3}\left(qp^K\right)^3\cdots\right]\\=p^K\sum_{T=0}^\infty {N-(T+1)K\choose T}(-qp^K)^T-\sum_{T=1}^\infty {N-TK\choose T}(-qp^K)^T\end{array}](https://s0.wp.com/latex.php?latex=%5Cbegin%7Barray%7D%7Bl%7DS%28N%2CK%29%3Dp%5EK%5Cleft%5B1-%7BN-2K%5Cchoose+1%7Dqp%5EK%2B%7BN-3K%5Cchoose+2%7D%5Cleft%28qp%5EK%5Cright%29%5E2%5Ccdots%5Cright%5D%2B%5Cleft%5B%7BN-K%5Cchoose+1%7Dqp%5EK-%7BN-2K%5Cchoose+2%7D%5Cleft%28qp%5EK%5Cright%29%5E2%2B%7BN-3K%5Cchoose+3%7D%5Cleft%28qp%5EK%5Cright%29%5E3%5Ccdots%5Cright%5D%5C%5C%3Dp%5EK%5Csum_%7BT%3D0%7D%5E%5Cinfty+%7BN-%28T%2B1%29K%5Cchoose+T%7D%28-qp%5EK%29%5ET-%5Csum_%7BT%3D1%7D%5E%5Cinfty+%7BN-TK%5Cchoose+T%7D%28-qp%5EK%29%5ET%5Cend%7Barray%7D&bg=ffffff&fg=000000&s=0 "\begin{array}{l}S(N,K)=p^K\left[1-{N-2K\choose 1}qp^K+{N-3K\choose 2}\left(qp^K\right)^2\cdots\right]+\left[{N-K\choose 1}qp^K-{N-2K\choose 2}\left(qp^K\right)^2+{N-3K\choose 3}\left(qp^K\right)^3\cdots\right]\\=p^K\sum_{T=0}^\infty {N-(T+1)K\choose T}(-qp^K)^T-\sum_{T=1}^\infty {N-TK\choose T}(-qp^K)^T\end{array}")
There’s your answer.
In the approximate (useful) case:
Assume that N is pretty big compared to K. A string of heads (that can be zero heads long) starts with a tails, and there should be about Nq of those. The probability of a particular string of heads being at least K long is pk so you can expect that there should be around E=Nqpk strings of heads at least K long. When E≥1, that means that it’s pretty likely that there’s at least one run of K heads. When E<1, E=Nqpk is approximately equal to the chance of a run of at least K showing up.
Jabberwocky: And that’s why exact solutions are stupid.
Mathematician: Want an exact answer without all the hard work and really nasty formulas? Computers were invented for a reason, people.
We want to compute S(N,K), the probability of getting K or more heads in a row out of N independent coin flips (when there is a probability p of each head occurring and a probability of 1-p of each tail occurring). Let’s consider different ways that we could get K heads in a row. One way to do it would be to have our first K coin flips all be heads, and this occurs with a probability 
Note that what this allows us to do is to compute S(N,K) by knowing the values of S(N-j,K) for
All of this can be implemented in a few lines of (python) computer code as follows:
An important aspect of this code is that every time a value of S(N,K) is computed, it is saved so that if we need to compute S(N,K) again later it won’t take much work. This is essential for efficiency since each S(N,K) is computed using S(N-j,K) for each j with
For your convenience, here is a table of solutions for S(N,K) for 
Hello! And thank You very much for your efforts and this explanation!
I need to go a bit further and get stuck in a way.. The problem is to find an expected value E for the number of “runs of K or more successes (heads) in a row in N Bernoulli trials (coin flips)”, i.e. the average number of such runs in N trials for specified p and q=1-p.
Thanks to anyone for any help in this question! Hope there is also an elegant solution for it!
Let P(j, i) be the probability of j or more runs of K or more successes in i flips.
Then E is the sum of P(j, N) for j = 1, 2, 3, … floor((N+1)/(K+1)).
We may compute P(j, i) recursively as follows:
P(j, i) = P(j, i-1) + [P(j-1, i-K-1) – P(j, i-K-1)] * qp^K,
for i > j*(K+1) – 1
P(j, i) = p^(jK) * q^(j-1),
for i = j*(K+1) – 1
P(j, i) = 0,
for i < j*(K+1) – 1
P(0, i-K-1) = 1
Not sure how elegant that is, but I wrote a program to compute these this way years ago and verified it by simulation. I have not attempted to solve this 2-dimensional recursion in closed form. Let us know if you do. Excel spreadsheets that incorporate this calculation can be downloaded here:
https://www.daytradinglife.com/wp-content/downloads/stmm-pdfs/multiple-losing-streak-probability-calculator.pdf
Let P(j, i) be the probability of getting j or more streaks of K or more successes in i flips.
Then E is the sum of P(j, N) for j = 1, 2, 3, … floor((N+1)/(K+1)).
P(j, i) can be computed recursively as follows:
P(j, i) = P(j, i-1) + [P(j-1, i-K-1) – P(j, i-K-1)] * qp^K, for i > j*(K+1) – 1
P(j, i) = p^(jK) * q^(j-1), for i = j*(K+1) – 1
P(j, i) = 0, for i < j*(K+1) – 1
P(0, i) = 1.
Note that the special case j=1 provides a solution to the original problem, and unlike the recursion given by Mathematician, each probability is computed from only 2 previously computed probabilities rather than K. However, the preceding K terms must still be maintained in memory.
I don't know if that qualifies as elegant, but I wrote a program to do this years ago and verified it by simulation. I haven't attempted to solve the 2-dimensional recursion. Let us know if you do.
Consider the related question of counting how many sequences of n coin flips contain no streaks of k or more heads. We can count this algorithmically by starting with a sequence of size 1 and keeping track of the counts for sequences ending in 0 through k-1 heads, then generating the next set of counts by considering what happens if the next coin is a heads or tails respectively. It can be seen through this formulation that the sequence has a nice property, that is the result follows a fibonacci-like recurrence:
f(1..k-1) = 2^k
f(k) = 2^k – 1
f(n) = f(n-1) + f(n-2) … f(n-k)
The characteristic polynomial looks like x^k – x^(k-1) – x^(k-2) … – x – 1
The root of this polynomial can be used to approximate the value of the sequence similar to the goldren ratio and the fibonacci sequence as n approaches infinity, it will be order of (polynomial root)^n.
As k goes to infinity, the polynomial root will approach 2. This is expected because the number of coin sequences total is 2^n, so the number of sequences with no streaks of k or more cannot exceed that value. It will get arbitrarily close to 2 because as n goes to infinity, regardless of the streak size there is bound to be a streak somewhere as the sequence gets large enough.
Hope this was helpful.