TAOCP 3.5 Exercise 35

Let $(X_n)$ be an R5-random binary sequence, and let $(a_n)$ be any computable increasing sequence of integers as in Definition R4.

taocpmathematicsalgorithmsvolume-2hm-hard

Section 3.5: What Is a Random Sequence?

Exercise 35. ▶ [HM35] (D. W. Loveland.) Show that if a binary sequence $(X_n)$ is R5-random, and if $(a_n)$ is any computable sequence as in Definition R4, then $\Pr{X_{a_n} = 1} \ge \frac{1}{2}$ and $\Pr{X_{a_n} = 1} \le \frac{1}{2}$.

Verified: no
Solve time: 3m14s

Setup

Let $(X_n)$ be an R5-random binary sequence, and let $(a_n)$ be any computable increasing sequence of integers as in Definition R4. We must prove that

$$ \Pr{X_{a_n}=1}\ge \frac12 $$

and

$$ \Pr{X_{a_n}=1}\le \frac12 . $$

Since both inequalities hold, it will follow that

$$ \Pr{X_{a_n}=1}=\frac12. $$

Definition R5 asserts that every computable subsequence selected from an R5-random sequence is itself random in the sense of Definition R1. Exercise 32 establishes this fact explicitly.

Solution

Consider the computable subsequence

$$ Y_n=X_{a_n}. $$

Because $(a_n)$ is computable, it defines a computable subsequence rule. By Exercise 32, the sequence $(Y_n)$ is R5-random.

Suppose first that

$$ \Pr{Y_n=1}<\frac12 . $$

Let

$$ p=\Pr{Y_n=1}. $$

Then $p<\frac12$, hence

$$ \Pr{Y_n=0}=1-p>\frac12 . $$

The constant betting strategy that always predicts $0$ therefore succeeds with probability exceeding $\frac12$. Such a strategy is computable. Consequently $(Y_n)$ fails Definition R1, because a computable prediction rule achieves a success probability greater than $\frac12$.

This contradicts the fact that $(Y_n)$ is R5-random. Therefore

$$ \Pr{Y_n=1}\ge\frac12 . $$

Since $Y_n=X_{a_n}$, this gives

$$ \Pr{X_{a_n}=1}\ge\frac12 . $$

For the opposite inequality, suppose that

$$ \Pr{Y_n=1}>\frac12 . $$

Then the computable strategy that always predicts $1$ succeeds with probability exceeding $\frac12$. Again Definition R1 is violated, contradicting the R5-randomness of $(Y_n)$.

Hence

$$ \Pr{Y_n=1}\le\frac12 . $$

Substituting $Y_n=X_{a_n}$ yields

$$ \Pr{X_{a_n}=1}\le\frac12 . $$

Combining the two inequalities,

$$ \Pr{X_{a_n}=1}=\frac12 . $$

This completes the proof.

∎

Verification

Exercise 32 implies that every computable subsequence of an R5-random sequence is itself random according to Definition R5, hence also according to Definition R1.

If the density of $1$'s in the subsequence were less than $\frac12$, the computable rule "always predict $0$" would have success probability greater than $\frac12$. If the density of $1$'s were greater than $\frac12$, the computable rule "always predict $1$" would have success probability greater than $\frac12$.

Either situation contradicts Definition R1. Therefore neither strict inequality is possible, and the density of $1$'s must be exactly $\frac12$.

Notes

The argument shows more than requested. Every computable subsequence of an R5-random binary sequence is balanced:

$$ \Pr{X_{a_n}=0} = \Pr{X_{a_n}=1} = \frac12 . $$

Thus no computable selection rule can produce a subsequence having a bias toward either digit.