Joint Probability of correlated Bernoulli distributed Random Variables

Question

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

Answer 1

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

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

2. $\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$.)