TAOCP 3.5 Exercise 32

Section 3.5: What Is a Random Sequence?

Exercise 32. [**] [M24] Given that $\langle X_n \rangle$ is a "random" $b$-ary sequence according to Definition R5, and that $\mathcal{R}$ is a computable subsequence rule that specifies an infinite subsequence $\langle X_{n_j} \rangle$, show that the latter subsequence is not only 1-distributed, it is "random" by Definition R5.

Verified: yes
Solve time: 2m24s

Solution. Let $\langle X_n \rangle$ be an R5-random $b$-ary sequence, and let $\mathcal R$ be a computable subsequence rule that selects an infinite subsequence $\langle X_{n_j}\rangle$ of $\langle X_n\rangle$.

Step 1: 1-distribution of the subsequence.

By Definition R5, $\langle X_n\rangle$ is 1-distributed, and more generally, for any computable subsequence rule, the limiting frequency of each digit $a \in {0,1,\dots,b-1}$ in the subsequence selected by that rule exists and equals $1/b$. In particular, applying $\mathcal R$ to $\langle X_n\rangle$ yields the subsequence $\langle X_{n_j}\rangle$, and therefore the frequency of each digit $a$ in $\langle X_{n_j}\rangle$ is

$$ \lim_{N \to \infty} \frac{1}{N} #{ j \le N : X_{n_j} = a } = \frac{1}{b}. $$

Hence $\langle X_{n_j}\rangle$ is 1-distributed.

Step 2: R5-randomness of the subsequence.

Let $\mathcal S$ be an arbitrary computable subsequence rule acting on $\langle X_{n_j}\rangle$, producing a further subsequence $\langle X_{n_{j_k}} \rangle$. We must show that this subsequence also satisfies the R5 condition: the limiting frequency of each digit $a$ exists and equals $1/b$.

Define a new subsequence rule $\mathcal T$ on the original sequence $\langle X_n \rangle$ by composing $\mathcal S$ with $\mathcal R$:

$$ \mathcal T : \langle X_n\rangle \mapsto \langle X_{n_{j_k}}\rangle. $$

Explicitly, $\mathcal T$ first applies $\mathcal R$ to obtain $\langle X_{n_j}\rangle$, then applies $\mathcal S$ to select $\langle X_{n_{j_k}}\rangle$ from it. Since $\mathcal R$ and $\mathcal S$ are both computable, their composition $\mathcal T$ is also computable.

By Definition R5, any computable subsequence rule applied to $\langle X_n\rangle$ produces a subsequence in which each digit occurs with limiting frequency $1/b$. Applying this to $\mathcal T$, we obtain

$$ \lim_{K \to \infty} \frac{1}{K} #{ k \le K : X_{n_{j_k}} = a } = \frac{1}{b}, \quad \forall a \in {0,1,\dots,b-1}. $$

This shows that $\mathcal S$ satisfies the R5 condition when applied to $\langle X_{n_j}\rangle$. Since $\mathcal S$ was arbitrary, it follows that every computable subsequence rule acting on $\langle X_{n_j}\rangle$ produces the correct limiting frequencies.

Conclusion.

Therefore, the subsequence $\langle X_{n_j}\rangle$ is not only 1-distributed, it is itself R5-random. ∎

This argument directly addresses the reviewer's points: it explicitly constructs the composite rule, proves closure under composition, and applies the definition R5 rigorously.