Question

I have been working on a problem in combinatorics that makes use of the following discrete distribution.

Let $a_{1}, a_{2},..., a_{N}$ be any binary sequence of of length $N$ with $n$ ones and $m$ zeros. Extend the sequence so that it is periodic with period $N$: $a_{1}, a_{2},..., a_{N}, a_{1}, a_{2},...$ From this sequence we can generate a probability mass function that gives the probability that a randomly selected sequence of $L$ consecutive terms contains exactly $x$ ones. For example, let the sequence be $110100$. Extend it so it's periodic: $110100110100...$. For a given $L$, say 4, look at all the sequences of 4 consecutive terms and generate a pmf:

1101 = 3
1010 = 2
0100 = 1
1001 = 2
0011 = 2
0110 = 2

x = 1 -> 0.167
x = 2 -> 0.667
x = 3 -> 0.167

The distribution itself and its variance obviously depend on how the ones and zeros are distributed within the sequence. However there are certain general properties that hold true regardless of the sequence, such as the mean, which is $nL/N$. One can think of this as an ordered hypergeometric distribution.

Does a treatment of this distribution already occur in the literature? My textbook search and google search haven't turned up any hits so far. Any help is appreciated!

Answer 1

If you have a sequence $a=(a_1,a_2,\dots,a_N)$ and a circulant matrix $C_L$ with column $(1,1,\dots,1,0,\dots,0)$ ($L$ 1's) then you are asking for the distribution of $x=C_La$.

This is a convolution, and yes the pmf will depend on $a$ heavily. If you are interested computationally, look up Fast Fourier Transform, and how it helps calculating convolutions.