The Stack Overflow podcast is back! Listen to an interview with our new CEO.
5 of 10 added 52 characters in body

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $p(N,k)$. This is given by the recurrence formula $$ p(N,k) = \begin{cases} 0 &\text{if } k<N\\ \dfrac{1}{2^N} + \sum_{m=0}^{\min(N-1,k-N-1)} \dfrac{1}{2^N}\dfrac{1}{2} + \sum_{m=N}^{k-N-1} \{1-p(N,m)\} \dfrac{1}{2^N}\dfrac{1}{2} &\text{else} \end{cases} $$ (with the convention that sums are equal to zero if the upper bound is strictly less than the lower bound). Indeed, my reasoning is that the first consecutive N heads have to be preceded by a tail and no other consecutive N heads before. If there are $m<N$ steps before, this is not possible so any sequence of $m$ throws can occur. When $m\ge N$, it is possible and has to be excluded.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ \dfrac{1}{2^N}\dfrac{1}{2} &\text{if } N<m<2N+1\\ \{1-p(N,m-N-1)\} \dfrac{1}{2^N}\dfrac{1}{2} &\text{else} \end{cases} $$

Now, the probability to get $M$ heads first and $N$ heads in exactly $m\ge N$ throws is $$ r(M,N,m) = \begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ \dfrac{1}{2^M}q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2^{M+N+1}}\sum_{r=1}^{N-M}\dfrac{1}{2}\{1-p(N,m-N-1-M-r)\}&\text{if } m\ge 2N-M \end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} \dfrac{1}{2^{N-M}} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2N+2}\sum_{r=1}^{N-M}\{1-p(N,m-N-1-M-r)\}&\text{if } m\ge 2N-M \end{cases} $$ The expected number can then be derived by $$ \mathfrak{E}(M,N)= \sum_{m=N}^\infty m\, s(M,N,m) $$ or $\mathfrak{E}(M,N)-M$ for the number of additional steps...