In a linear string of N elements, each element independently takes the value 1 with probability p and 0 with probability 1-p.

probability/ones.in.window New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

In a linear string of N elements, each element independently takes
the value 1 with probability p and 0 with probability 1-p.  What is the
probability P(N,M,K) that in any window of M consecutive elements there
are at most K 1's?

In particular, what is the value of P(N^2, N, K)?

Show solution

This probability (if each element is independent) is independent of N.

If P(M,K) = Prob{ at most K 1's in M elements } we have

P(M,K) = p * P(M-1,K-1) + (1-p) * P(M-1,K)

with the boundary conditions

P(1,1) = p  and  P(M,K) = 0 if K > M

For example P(K,K) = p^K.

This recurrence can be solved using generating functions or other
standard method.

-- Ricardo Baeza-Yates <rabaeza@watmum.uwaterloo.ca>

[ Editor: P(K,K) = p^K and P(M,K) = 0 for K > M are the values for
  exactly K 1's in a single window of M elements; the probability of at
  most K 1's would be 1 in both cases.  The reply also treats a single
  window, while the question asks that every window of M consecutive
  elements have at most K 1's. ]