# biased coin tossing where each pair of heads is separated by at least l tails.

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:

$$p^h(1-p)^{n-h}\binom{n-\ell(h-1)}{h}$$

Note

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)$$

or

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

These correspond to the two answers above, respectively.

• 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