Suppose that I have a biased coin where $\Pr[head] = p$ is very small. Let's say I tossed this coin $n$ times and I saw $h$ heads. Then what is the probability that each pair of heads is separated by at least $\ell$ tails?

For example, let's say $(n, h, \ell) = (10, 2, 5)$.

  • 'Yes': T H T T T T T T H T
    There are two heads at location 1 and 9, but they are separated by 6 tails.
  • 'No': T T T T T H T H T T
    There are two heads at location 6 and 8, but they are separated by only one tail.

One possible approach is summing up all the probabilities of 'yes' events. Is there any closed form for this probability?


A generalization of the "stars and bars" technique will give you that the probability is $$\frac{\binom{n-\ell(h-1)}{h}}{\binom{n}{h}}$$

That assumes $h$ is a given. If you want the probability that you will get $h$ heads with this condition, that is:



These two different probabilities depend on your meaning. Let $L$ be the random variable equal to the least number of tails between consecutive heads, and let $H$ be the number of heads. Do you want the conditional probability:

$$P(L\geq \ell|H=h)$$


$$P(L\geq\ell\text{ and }H=h)$$

These correspond to the two answers above, respectively.

  • $\begingroup$ Hmmm, can you explain how you got the value $\binom{n-\ell(h-1)}{h}$? $\endgroup$ – Federico Magallanez Mar 6 '13 at 14:28
  • $\begingroup$ Select $h$ items from a sequence of $n-\ell(h-1)$ items, and call those heads. Mark the rest tails. Between the $h-1$ pairs of sequential heads, insert $\ell$ additional tails. Now you have a sequence like what you want, and you can get such a sequence by a this sort of selection in exactly one way. So they must have the same count. $\endgroup$ – Thomas Andrews Mar 6 '13 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.