10 replaced http://stats.stackexchange.com/ with https://stats.stackexchange.com/ edited Apr 13 '17 at 12:44 Warning: the following may not be considered as a proper answer in that it does not provide a closed form solution to the question, esp. when compared with the previous answersthe previous answers. I however found the approach sufficiently interesting to work out the conditional distribution. Consider the preliminary question of getting a sequence of $$N$$ heads out of $$k$$ throws, with probability $$1-p(N,k)$$. This is given by the recurrence formula $$p(N,k) = \begin{cases} 1 &\text{if } k Indeed, my reasoning is that no consecutive $$N$$ heads out of $$k$$ draws can be decomposed according to the first occurrence of a tail out of the first $$N$$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $$N$$th draw leads to this recurrence relation. 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\  p(N,m-N-1) \dfrac{1}{2^{N+1}} &\text{if } N