TAOCP 3.5 Exercise 2

Section 3.5: What Is a Random Sequence?

Exercise 2. [10] Consider the periodic binary sequence 0, 0, 1, 1, 0, 0, 1, 1, $\ldots$. Is it "2-distributed"? Is it 3-distributed? Is it 3-distributed?

Verified: yes
Solve time: 1m12s

The sequence has period $4$:

$0,0,1,1,0,0,1,1,\ldots$

To test 2-distribution, examine the successive pairs:

$00,\ 01,\ 11,\ 10,\ 00,\ 01,\ 11,\ 10,\ldots$

Each of the four binary numbers $00$, $01$, $10$, $11$ occurs once in every period of four pairs. Hence each occurs with probability $1/4=1/2^2$. By Definition D, the sequence is 2-distributed.

For 3-distribution, examine the successive triples:

$001,\ 011,\ 110,\ 100,\ 001,\ 011,\ 110,\ 100,\ldots$

Only the four binary numbers $001$, $011$, $110$, and $100$ occur, each with probability $1/4$. The remaining four binary numbers $000$, $010$, $101$, and $111$ occur with probability $0$. Definition D requires every 3-digit binary number to occur with probability $1/8=1/2^3$. Therefore the sequence is not 3-distributed.

Hence the sequence is 2-distributed but not 3-distributed:

$\boxed{\text{2-distributed, but not 3-distributed.}}$