Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
Hmmm, can you explain how you got the value $\binom{n-\ell(h-1)}{h}$? – Federico Magallanez Mar 6 '13 at 14:28
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. – Thomas Andrews Mar 6 '13 at 14:47
Thanks! That makes sense! – Federico Magallanez Mar 6 '13 at 17:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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