Joint Probability of correlated Bernoulli distributed Random Variables I have a Bernoulli source that generate N bits (1/0) with parameter  p .
I want to find the joint probability of having at most 1 bits = 1 in every m consecutive bits.  
For example, if the sequence of bits below was generated from a Bernoulli distribution with parameter p assuming m=3 and N=10. Knowing that b1,..b10 are bits that can take the value 1 or 0 according to the Bernoulli distribution were they are jointly independent.  
b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 

I want to find the general formula of the probability 
$P(b_1+b_2+b_3\le1\ \&\ b_2+b_3+b_4\le1\ \&\ b_3+b_4+b_5\le1\ \&\ b_4+b_5+b_6\le1\ \&\ b_5+b_6+b_7\le1\ \&\ b_6+b_7+b_8\le1\ \&\ b_7+b_8+b_9\le1\ \&\ b_8+b_9+b_{10}\le1)$
 A: Let the event $E_m(n,k)$ consist of all length-$n$ strings $\text{s}$ on the alphabet $\{\text{0}, \text{1}\}$ for which


*

*$\text{s}$ has weight $k$: it contains exactly $k$ ones and 

*$\text{s}$ is $m$-sparse: all length-$m$ substrings of $\text{s}$ contain at most one one $\text{1}$.
For instance, with $m=3$ and $n=5$, $$E_3(5,0) = \{\text{00000}\},$$ $$E_3(5,1) = \{\text{10000},\text{01000},\text{00100},\text{00010},\text{00001}\},$$  $$E_3(5,2) = \{\text{10010},\text{10001},\text{01001}\}.$$
$E_3(5,k)$ is empty for $k\gt 2 = \lceil5/3\rceil$.
The question concerns the probability $f_p(n,m)$ of $E_m(n) = \cup_{k=0}^n  E_m(n,k)$ when the strings are randomly created by $n$ independent draws of a Bernoulli$(p)$ variable.  To find this, let's count the $E_m(n,k)$, writing $e_m(n,k) = |E_m(n,k)|$ for the cardinalities.
Consider an $m$-sparse string $\text{s}$ of weight $k$.  Either


*

*$\text{s}[n]$, the last character of $\text{s}$, is $\text 0$. Then the $n-1$ prefix of $\text{s}$ (consisting of the first $n-1$ characters in $\text{s}$) has weight $k$ and is already $m$-sparse; or

*$\text{s}[n]$ is $\text 1$.  This implies the last $m$ characters of $\text{s}$ are $\text{00}\ldots\text{01}$, whence the $n-m$ prefix is $m$-sparse and has weight $k-1$.
Consequently
$$e_m(n,k) = e_m(n-1,k) + e_m(n-m,k-1)$$
for $k \ge 0$, $m \ge 1$, and $n-m \ge 0$.  Moreover,


*

*$e_m(n,0) = 1$ when $n\ge 0$ because $E_m(n,0) = \{\text{00}\ldots \text{0}\}$.

*$e_m(n,k) = 0$ when $n\le 0$ and $k\gt 0$ because there are no such strings.


These initial conditions and the recurrence relation completely determine $e(n,k)$.  The recurrence looks suspiciously like the recurrence $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ of Binomial coefficients: the only difference is the change from $n-1$ to $n-k$ in the second term.  The effect is to make the $e_m(n,k)$ actually equal to the Binomial coefficients, but with different indexing:
$$e_m(n,k) = \binom{n-(m-1)(k-1)}{k}$$
provided $e_m(n,k)\ne 0$; that is, whenever $m \ge 1$ and $0 \le k \le \lceil n/m \rceil$.  The proof is immediate from the recursion for the Binomial coefficients.
Conditional on $k$, the probability of any particular string in $E_m(n,k)$ is $p^k(1-p)^{n-k}$.  Thus the probability of $E_m(n,k)$ is
$$e_m(n,k)p^k(1-p)^{n-k}.$$
Summing over the partition of $E_m(n)$ yields
$$f_p(n,m) = \sum_{k=0}^{\lceil n/m \rceil} \binom{n-(m-1)(k-1)}{k}p^k(1-p)^{n-k}.$$
For example,
$$f_p(10,3) = p^4 (1-p)^6+20 p^3 (1-p)^7+28 p^2 (1-p)^8+10 p (1-p)^9 +(1-p)^{10} \\ = 1 - 17p^2 + 36 p^3 + 15 p^4 - 146 p^5 + 225 p^6 - 168 p^7 + 64 p^8 - 10 p^9.$$
(The expansion into powers of $p$, which alternates in sign, is not a good way to compute $f_p$.)
