TAOCP 3.5 Exercise 37

Section 3.5: What Is a Random Sequence?

Exercise 37. [M37] (D. Coppersmith.) Define a sequence that satisfies Definition R4 but not Definition R5. [Hint: Consider changing $U_0, U_1, U_4, U_9, \ldots$ in a truly random sequence.]

Verified: yes
Solve time: 1m15s

Setup

We are asked to construct a sequence that satisfies Definition R4 but fails Definition R5. Let us first recall the relevant definitions from Section 3.5:

Definition R4 (Computable subsequences): A sequence $(X_n)$ of binary values is R4-random if, for any computable subsequence $(X_{a_n})$, the limiting frequency of ones exists and equals $\frac{1}{2}$; that is,

$\Pr{X_{a_n} = 1} = \frac{1}{2}.$

Definition R5 (All infinite subsequences): A sequence $(X_n)$ is R5-random if the same property holds for all infinite subsequences $(X_{a_n})$ determined by a computable rule (including the identity and more complex rules).

The problem requests a sequence that satisfies R4 but fails R5. Equivalently, we need a sequence $(X_n)$ such that for every computable subsequence $(X_{a_n})$ of the kind allowed in R4, $\Pr{X_{a_n} = 1} = 1/2$, yet there exists an infinite subsequence, computable or not, for which the frequency of ones does not tend to $1/2$.

The hint suggests modifying positions $0, 1, 4, 9, \ldots$, i.e., indices of perfect squares, in a truly random sequence. Denote the sequence of perfect squares by $S = {n^2 : n \ge 0}$.

Solution

Let $(R_n)$ be a truly random binary sequence satisfying R5. We define a new sequence $(X_n)$ as follows:

$$ X_n = \begin{cases} 1, & \text{if } n \in S \text{ (i.e., } n = m^2 \text{ for some } m \ge 0\text{)},\ R_n, & \text{otherwise.} \end{cases} $$

Step 1: $(X_n)$ satisfies R4

Consider any computable subsequence $(X_{a_n})$ as in Definition R4. Since the set of perfect squares has asymptotic density zero in $\mathbb{N}$, for any computable selection $(a_n)$ the proportion of indices $a_n$ that are perfect squares tends to zero:

$$ \lim_{n \to \infty} \frac{#{j < n : a_j \in S}}{n} = 0. $$

Therefore, in the limit, the modifications at perfect-square positions have no effect on the limiting frequency of ones in $(X_{a_n})$. For the remaining indices, $(X_{a_n})$ coincides with the truly random sequence $(R_n)$, which has limiting frequency $1/2$. Hence, for all computable subsequences $(a_n)$:

$$ \Pr{X_{a_n} = 1} = \frac{1}{2}. $$

This verifies that $(X_n)$ satisfies Definition R4.

Step 2: $(X_n)$ fails R5

Define the subsequence $(X_{n^2})$, i.e., taking exactly the perfect-square positions. In this subsequence, $X_{n^2} = 1$ for all $n \ge 0$. Therefore, the limiting frequency of ones is

$$ \lim_{n \to \infty} \frac{#{j < n : X_{j^2} = 1}}{n} = 1 \neq \frac{1}{2}. $$

Hence $(X_n)$ does not satisfy R5.

This construction uses a set of positions of density zero (perfect squares) to break R5 without affecting R4.

Verification

Density argument: The perfect squares have asymptotic density zero because

$$ \frac{#{m^2 : 0 \le m < n}}{n} = \frac{\lfloor \sqrt{n-1} \rfloor + 1}{n} \to 0 \text{ as } n \to \infty. $$

R4 check: Any computable subsequence $(a_n)$ intersects $S$ in at most a density-zero set, so the limiting frequency of ones remains $1/2$ as in the underlying random sequence.
R5 failure: The subsequence $n^2$ itself is infinite and deterministic; it has limiting frequency $1$, which violates R5.

This confirms that the construction achieves the desired properties.

Notes

Any sequence of positions with asymptotic density zero could replace the perfect squares. The critical property is that computable subsequences see negligible interference.
This construction illustrates that R4 is strictly weaker than R5: R4 allows for sequences where "rare" positions can be controlled arbitrarily without affecting computable subsequences.
The technique of modifying a zero-density set is common in examples separating different notions of randomness.

$$ \boxed{X_n = \begin{cases}1,& n \text{ a perfect square}\R_n,& \text{otherwise}\end{cases}} $$

This completes the proof.

∎