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

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.

Solutions Collecting From Web of "Probability of having at least $K$ consecutive zeros in a sequence of $0$s and $1$s"

Let’s compute $C(N,M,k)$ the number of sequences of length $N$, with $M$ zeros, and with all runs of zeros having length up to $k$. Say we have $\ell$ runs of zeroes: $z_1,z_2 \cdots z_\ell$ with $1\le z_i \le k$ , $\sum_{i=1}^\ell z_i=Z=N-M$, and $ \lceil Z/k \rceil \le \ell \le M+1$

Then $$C(N,M,k)=\sum_{\ell=\lceil M-N/k \rceil}^{M+1} c_r(M-N,\ell,k) \, c(M-\ell+1,\ell+1)$$

where $c(A,B)={A+B-1\choose B-1}$ is the number of weak compositions, and $c_r(A,B,k)$ is the number of (strict) compositions restricted to a maximum size $k$. This later problem is solved here.

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}}$$.

I think what you are looking for is covered [here][1]: https://stats.stackexchange.com/questions/21825/probability-over-multiple-blocks-of-events

There are 2 types of approaches given in the answers to that question – either a dynamic programming solution or a Markov Chain model should lead to the answer you are seeking in any particular case. If you are up to attempting to find a general formula you should study these methods.

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