Tossing a fair coin for $N$ times and we get a result series as $HTHTHHTT\dots~$, Here '$H$' denotes 'head' and '$T$' denotes 'tail' for a specific tossing each time.
What is the probability that the length of the longest streak of consecutive heads is greater than or equal to $k$? (that is we have a $HHHH\dots~$, which is the substring of our tossing result, and whose length is greater than or equal to $k$)
I came up with a recursive solution (though not quite sure), but cannot find a closed form solution.
Here is my solution.
Denote $P(N,k)$ as the probability for tossing the coin $N$ times, and the longest continuous heads is greater or equal than $k$.
Then (For $N>k$)
$$
P(N,k)=P(N-1,k)+\Big(1-P(N-k-1,k)\Big)\left(\frac{1}{2}\right)^{k+1}
$$
Best Answer
We can derive an explicit formula of the probability $P(N,k)$ based upon the Goulden-Jackson Cluster Method.
According to the paper (p.7) from Goulden and Jackson the generating function $f_k(s)$ is \begin{align*} f_k(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=|\mathcal{V}|=2$, the size of the alphabet and with $\mathcal{C}$ the weight-numerator with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[H^k]) \end{align*} We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[H^k])&=-\frac{s^k}{1+s+\cdots+s^{k-1}}=-\frac{s^k(1-s)}{1-s^k} \end{align*}
$$ $$
$$ $$
Comment:
In (3) we use the linearity of the coefficient of operator and $[s^N]s^mf(s)=[s^{N-m}]f(s)$
In (4) we change the limit of the left hand sum from $\infty$ to $N$ according to the maximum coefficient $[s^N]$. According to the factors $s^{kj}$ we consider in the following only summands with $m\equiv N(\bmod k)$
In (5) we reorganise the sums from the line above by extracting from the left hand sum the first summand and shifting in the right hand side the index by one and putting both sums together.