1
$\begingroup$

Suppose the sequence 1001111011011 has a total of $4$ "blocks" of one, because number of contiguous sequences made of ones (1, 1111,11 and 11) count to 4. Given a random bit array of length $N$, what's the expected value of the "number of 1 blocks"? Related to that, what is the probability there are $M$ blocks in a bit a array of length $N$?

$\endgroup$
1
$\begingroup$

Using $z$ for zeros and $w$ for ones and $u$ for runs we get the generating function

$$(1+z+z^2+\cdots) \\ \times \sum_{q\ge 0} u^{q} (w+w^2+\cdots)^q (z+z^2+\cdots)^q \\ \times (1+uw+uw^2+\cdots)$$

which is

$$\frac{1}{1-z} \\ \times \sum_{q\ge 0} u^{q} \frac{w^q}{(1-w)^q} \frac{z^q}{(1-z)^q} \\ \times \left(1+u\frac{w}{1-w}\right)$$

or

$$\frac{1}{1-z} \frac{1}{1-uwz/(1-z)/(1-w)} \frac{1-w+uw}{1-w} \\ = \frac{1-w+uw}{(1-z)(1-w)-uwz}.$$

As a sanity check we put $u=1$ and $w=z$ to obtain

$$\frac{1}{(1-z)^2 - z^2} = \frac{1}{1-2z}$$

and we see that we have accounted for all strings of length $N.$ We no longer need the distinction between zeros and ones here so we obtain

$$\frac{1-z+uz}{(1-z)^2-uz^2} = \frac{1-z+uz}{(1-z)^2}\frac{1}{1-uz^2/(1-z)^2} \\ = \left(\frac{1}{1-z} + \frac{uz}{(1-z)^2}\right) \frac{1}{1-uz^2/(1-z)^2}.$$

Extract the coefficient on $[u^M]$ to get

$$\frac{z^{2M}}{(1-z)^{2M+1}} + \frac{z^{2M-1}}{(1-z)^{2M}} \\ = \left(\frac{z}{1-z} + 1\right) \frac{z^{2M-1}}{(1-z)^{2M}} = \frac{z^{2M-1}}{(1-z)^{2M+1}}.$$

Continue with the coefficient on $[z^N]$ to obtain

$$[z^N] \frac{z^{2M-1}}{(1-z)^{2M+1}} = [z^{N+1-2M}] \frac{1}{(1-z)^{2M+1}} \\ = {N+1-2M+2M\choose 2M} = {N+1\choose 2M}$$

for a probability of

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2^N} {N+1\choose 2M}.}$$

We get for the expectation

$$\sum_{M=0, \; 2M\le N+1} M {N+1\choose 2M} = \sum_{M=1, \; 2M\le N+1} M {N+1\choose 2M} \\ = \frac{N+1}{2} \sum_{M=1, \; 2M\le N+1} {N\choose 2M-1} = \frac{N+1}{2} \sum_{q=0}^N {N\choose q} \frac{1-(-1)^q}{2} \\ = \frac{N+1}{4} 2^N.$$

Dividing by $2^N$ then yields

$$\bbox[5px,border:2px solid #00A000]{ \frac{N+1}{4}.}$$

This may also be obtained by linearity of expectation. We place a zero value at the front of the string and may then count runs of ones by the number of times a zero was followed by a one in the modified string, which gives $1/2 + (N-1)/4,$ the same answer ($N-1$ places where we transition from one bit to the next).

$\endgroup$
1
$\begingroup$

Hint: there are $N-1$ places between the bits, each of which either divides a block of 1s from a block of 0s or is inside a block. For each possible odd number of dividers between blocks, there is one possible value for the number of blocks of 1s. For each even number of dividers, there are two (equally likely) possible numbers of 1-blocks.

$\endgroup$
0
$\begingroup$

Concern an infinite string.

Let $X$ denote the location of the first character in this string that takes value $0$.

For $N\in\mathbb N$ let $S_N$ denote the substring that starts at the first character and has length $N$.

Let $B_N$ denote the number of "one-blocks" of substring $S_N$.

As an example: if we are dealing with $N=12$ and string $101110110111110111110\cdots$ then $X=2$, $S_{12}=101110110111$ and $B_{12}=4$.

Further denote $\mu_N=\mathbb EB_N$ and observe that:

  • $\mathbb E(B_N\mid X=1)=\mu_{N-1}$ and
  • $\mathbb E(B_N\mid X=k)=1+\mu_{N-k}$ for $k\in\{2,\dots,N-1\}$ and
  • $\mathbb E(B_N\mid X=k)=1$ for $k\geq N$

Then working out: $\mathbb EB_N=\sum_{k=1}^{\infty}\mathbb E[B_N\mid X=k]P(X=k)$ we find:$$\mu_N=\sum_{k=1}^{N-1}\mu_{N-k}2^{-k}+\frac12$$

Based on that we find:

$$\begin{aligned}\mu_{N+1} & =\frac{1}{2}\left[\mu_{N}+2^{-N}\sum_{k=1}^{N-1}\mu_{k}2^{k}\right]+\frac{1}{2}\\ & =\frac{1}{2}\left[\mu_{N}+\mu_{N}-\frac{1}{2}\right]+\frac{1}{2}\\ & =\mu_{N}+\frac{1}{4} \end{aligned} $$

This recursion equality leads easily to:$$\mu_N=\frac14N+\frac14$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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