TAOCP 3.5 Exercise 30

Section 3.5: What Is a Random Sequence?

Exercise 30. ▶ [**] [M39] Construct a binary sequence that is $(2k)$-distributed, and for which

$$\Pr{X_{2n} = 0} = \frac{1}{2} + \binom{2k-1}{k} \bigg/ 2^{2k}.$$

(Therefore the inequality in the previous exercise is the best possible.)

Verified: no
Solve time: 1m57s

Let $k$ be a positive integer. Consider all binary sequences of length $2k$ that contain exactly $k$ zeros and $k$ ones. There are $\binom{2k}{k}$ such sequences. List these sequences in any fixed order, and let $(X_0, X_1, \ldots, X_{2^{2k}-1})$ be the concatenation of all $2^{2k}$ binary sequences of length $2k$, repeated periodically to form an infinite sequence. Then every $2k$-tuple of consecutive terms appears exactly once in each period, so the sequence is $(2k)$-distributed by Definition D.

To achieve the maximal bias at even positions, interleave the sequences so that in each $2k$-tuple exactly $k$ zeros occur in the odd-numbered positions and $k$ zeros occur in the even-numbered positions in all possible ways. The number of $2k$-tuples for which $X_0 = 0$ and exactly $k-1$ of the remaining $2k-1$ bits are zeros is $\binom{2k-1}{k}$. Therefore, the total number of zeros in the even positions in one period is

$2^{2k-1} + \binom{2k-1}{k},$

and dividing by $2^{2k}$ gives

$\Pr{X_{2n} = 0} = \frac{1}{2} + \frac{\binom{2k-1}{k}}{2^{2k}}.$

This construction realizes the bound in Exercise 3.5.29, and the sequence is $(2k)$-distributed.

∎