Probability of having at least $K$ consecutive zeros in a sequence of $0$s and $1$s

Question

I have a sequence of length $N$ consisting of $M$ ones and $N-M$ zeros. I am trying to find the number of possible arrangements that produce a sequence in which there exist at least K consecutive zeros.

Any input on how to approach this is appreciated.

Answer 1

Assuming $1$s and $0$s appear independent of each other, for $M$ ones, the probability that a $1$ appears is simply $p=\frac{M}{N}$ and for $0$ is simply $1-p$. The PDF of run of $K$ consecutive $0$s can then be calculated as follows:

$$ r(K) = \left\{ \begin{array}{rl} p(1-p)^K &\mbox{ $0\leq K\leq N$} \\ (1-p)^K &\mbox{ $K=N$} \end{array} \right. $$

Answer 2

First off, I do not think you mean the standard combinatorial definition of derangement as found here: http://en.wikipedia.org/wiki/Derangement as this requires that each item has its own "home" let's say. I'm going to solve this assuming that you mean arrangement instead.

We can solve the problem by creating one "super" subsequence of zeroes having length $K$. Then we can think of now having $M$ ones still but $N-M-K+1$ zeroes as a result of the combination. In total we now have $N-K+1$ items to arrange in sequences. Before combining there were $\binom{N}{M}$ different sequences and after combining there are $\binom{N-K+1}{M}$ sequences with at least $K$ consecutive zeroes. Thus the probability you seek is: $$p(K) = \frac{\binom{N-K+1}{M}}{\binom{N}{M}} ; \ K=1,2,...,N-M$$

A quick sanity check at the endpoints of $K$ shows that we get what intuition or a quick sketch would confirm. For $K =1$ we know that the probability should be $1$ which the above formula $\frac{\binom{N}{M}}{\binom{N}{M}}$ gives. Also for $K = N-M$ we can see that there are $M+1$ positions for our "super" subsequence to occupy in the following diagram:

$$(\underbrace{000\cdots0}_{N-M} \underbrace{111\cdots1}_{M})$$

If you think of the rightmost $0$ in the "super" subsequence and the positions it can occupy, you will see that there are $M+1$ possible subseqences when $K = N-M$. And so the probability agrees with our formula: $$\frac{\binom{M+1}{M}}{\binom{N}{M}} = \frac{M+1}{\binom{N}{M}}$$.