Intereting Posts

Identify the universal property of kernels
Extreme points of unit ball of Banach spaces $\ell_1$, $c_0$, $\ell_\infty$
Reinventing The Wheel – Part 1: The Riemann Integral
Proving functions are in $L_1(\mu)$.
The set of rational numbers of the form p/p', where p and p' are prime, is dense in $[0, \infty)$
Does there exist a sequence $\{a_n\}_{n\ge1}$ with $a_n < a_{n+1}+a_{n^2}$ such that $\sum_{n=1}^{\infty}a_n$ converges?
The Entscheidungsproblem and the notion of decidability in first order logic
Uncountable disjoint union of $\mathbb{R}$
Limit of argz and r
$\infty = -1 $ paradox
How can an ultrafilter be considered as a finitely additive measure?
Why is it useful to show the existence and uniqueness of solution for a PDE?
Why does $\lim_{n\to\infty} z_n=A$ imply $\lim_{n\to\infty}\frac{1}{n}(z_1+\cdots+z_n)=A$?
Rigour in mathematics
What is the sum of sum of digits of $4444^{4444^{4444}}$?

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.

- Does this double series converge?
- How many $n$-digit decimal sequences (using the digits $0 = 9$) are there in which the digits $1$, $2$ and $3$ all appear?
- Minimum distance of a binary linear code
- A question related to Pigeonhole Principle
- Repeatedly taking mean values of non-empty subsets of a set: $2,\,3,\,5,\,15,\,875,\,…$
- Nice application of the Cauchy?-Frobenius?-Burnside?-Pólya? formula

- Sum from 0 to n of $ n \choose i $?
- Prove $\sum_{k=0}^{58}\binom{2017+k}{58-k}\binom{2075-k}{k}=\sum_{k=0}^{29}\binom{4091-2k}{58-2k}$
- How Many Ways to Make a Pair Given Five Poker Cards
- Convolution Identity for Stirling Numbers
- Difference of random variables
- Alternative Expected Value Proof
- Size of a family of sets $F$ such that if $|A\cap X|=|B\cap X|$ for all $X\in F$, then $A=B$
- Counting binary sequences with no more than $2$ equal consecutive numbers
- The number of (non-equal) forests on the vertex set V = {1, 2, …,n} that contains exactly 2 connected components is given by
- Is there an elegant bijective proof of $\binom{15}{5}=\binom{14}{6}$?

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.

$$

- Convergence of $\sum \frac{(2n)!}{n!n!}\frac{1}{4^n}$
- What are the applications of functional analysis?
- How to find large prime factors without using computer?
- Showing that group of orientation preserving isometries of Icosahedron is a simple group
- An inequality $\,\, (1+1/n)^n<3-1/n \,$using mathematical induction
- relation of R-module homomorphisms with direct sums
- Decay of a Convolution
- Abelian category without enough injectives
- Classifying the factor group $(\mathbb{Z} \times \mathbb{Z})/\langle (2, 2) \rangle$
- Is quasi-isomorphism an equivalence relation?
- what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by 47?
- Discrete subgroups are lattices
- Newton's method for square roots 'jumps' through the continued fraction convergents
- Does “regular” implies collectionwise hausdorff?
- Peano arithmetic with the second-order induction axiom