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

  • $\begingroup$ Are the bits jointly independent? $\endgroup$ Jun 5, 2015 at 12:18
  • $\begingroup$ @AlecosPapadopoulos Yes, the bits are jointly independent $\endgroup$
    – Weijing Li
    Jun 5, 2015 at 12:23

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


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.