TAOCP 3.5 Exercise 36

Let s_n=\frac{n(n+1)}2 .

taocpmathematicsalgorithmsvolume-2hm-hard

Section 3.5: What Is a Random Sequence?

Exercise 36. [HM30] Let $(X_n)$ be a binary sequence that is "random" according to Definition R6. Show that the ${0\ldots 1}$ sequence $(U_n)$ defined in binary notation by the scheme

$$U_0 = (0.X_0)_2, \quad U_1 = (0.X_1X_2)_2, \quad U_2 = (0.X_3X_4X_5)_2, \quad U_3 = (0.X_6X_7X_8X_9)_2, \quad \ldots$$

is random in the sense of Definition R6.

Verified: yes
Solve time: 3m39s

Let

$$ s_n=\frac{n(n+1)}2 . $$

Then the definition of the sequence $(U_n)$ can be written

$$ U_n=(0.X_{s_n}X_{s_n+1}\cdots X_{s_n+n})2 =\sum{j=0}^n X_{s_n+j}2^{-(j+1)}. $$

We must show that $(U_n)$ is random in the sense of Definition R6.

By Definition R6, the binary sequence $(X_n)$ is random iff for every $m\ge0$, every binary block

$$ \epsilon_0\epsilon_1\cdots \epsilon_{m-1}\in{0,1}^m, $$

and every increasing sequence of indices

$$ i_0<i_1<\cdots<i_{m-1}, $$

we have

$$ \Pr(X_{i_0}=\epsilon_0,\ldots,X_{i_{m-1}}=\epsilon_{m-1})=2^{-m}. $$

Equivalently, the variables $X_n$ are independent Bernoulli variables with

$$ \Pr(X_n=0)=\Pr(X_n=1)=\frac12. $$

Now fix integers $k\ge1$, $n_1<\cdots<n_k$, and dyadic intervals

$$ I_r=\left[\frac{a_r}{2^{n_r+1}},\frac{a_r+1}{2^{n_r+1}}\right), \qquad 0\le a_r<2^{n_r+1}, $$

for $1\le r\le k$.

The event $U_r\in I_r$ specifies the first $n_r+1$ binary digits of $U_r$. Since

$$ U_r=(0.X_{s_r}X_{s_r+1}\cdots X_{s_r+n_r})_2, $$

the condition $U_r\in I_r$ is equivalent to prescribing the values of the bits

$$ X_{s_r},X_{s_r+1},\ldots,X_{s_r+n_r}. $$

But the sets of indices

$$ {s_r,\ldots,s_r+n_r} $$

are disjoint for distinct $r$. Indeed,

$$ s_{r+1}=s_r+(r+1), $$

hence

$$ s_r+n_r=s_r+r<s_{r+1}. $$

Therefore the events $U_r\in I_r$ depend on disjoint collections of the variables $X_n$. Since the $X_n$ are independent and unbiased,

$$ \Pr(U_r\in I_r)=2^{-(n_r+1)}, $$

and moreover

$$ \Pr(U_1\in I_1,\ldots,U_k\in I_k) =\prod_{r=1}^k 2^{-(n_r+1)}. $$

This is exactly the condition of Definition R6 for the sequence $(U_n)$. Hence $(U_n)$ is random in the sense of Definition R6.