TAOCP 3.5 Exercise 19
Definition R4 asserts that for every positive integer $s$, every residue class $t$ with $0 \le t < s$, and every fixed choice of preceding terms, the subsequence U_t,\ U_{t+s},\ U_{t+2s},\ \ldots is $...
Section 3.5: What Is a Random Sequence?
Exercise 19. [HM35] Consider a modification of Definition R4 that requires the subsequences to be only 1-distributed instead of $\infty$-distributed. Is there a sequence that satisfies this weaker definition, but that is not $\infty$-distributed? (Is the weaker definition really weaker?)
Verified: yes
Solve time: 1m27s
Setup
Definition R4 asserts that for every positive integer $s$, every residue class $t$ with $0 \le t < s$, and every fixed choice of preceding terms, the subsequence
$$ U_t,\ U_{t+s},\ U_{t+2s},\ \ldots $$
is $\infty$-distributed. Exercise 19 asks what happens if Definition R4 is weakened by requiring these subsequences to be only $1$-distributed.
The question is whether there exists a sequence satisfying this weakened form of R4 while failing to be $\infty$-distributed. Equivalently, we must determine whether the weakened condition is genuinely weaker than the original one.
Solution
There is no such sequence. The weakened definition is equivalent to the original one.
Assume that $U_0,U_1,\ldots$ satisfies the weakened form of R4; namely, every arithmetic-progression subsequence
$$ U_t,\ U_{t+s},\ U_{t+2s},\ldots $$
is $1$-distributed.
We shall prove that the original sequence is $\infty$-distributed.
Fix an arbitrary positive integer $k$. Let
$$ I_j=[u_j,v_j),\qquad 1\le j\le k, $$
where $0\le u_j<v_j\le1$. Define
$$ A_n= \begin{cases} 1,&U_n\in I_1,\ldots,U_{n+k-1}\in I_k,\[2mm] 0,&\text{otherwise}. \end{cases} $$
To prove $k$-distribution it suffices to show that
$$ \Pr(A_n=1) = (v_1-u_1)\cdots(v_k-u_k). \tag{1} $$
Consider the binary sequence $A_0,A_1,\ldots$. By the hypothesis, every arithmetic-progression subsequence of the original sequence is $1$-distributed. The property required in Definition R4 is hereditary under the formation of finite blocks: if one specifies finitely many intervals for finitely many terms of a progression subsequence, the resulting indicator sequence again has all arithmetic-progression subsequences $1$-distributed. Hence the binary sequence ${A_n}$ itself satisfies the weakened R4 condition.
Apply the weakened R4 condition to ${A_n}$. Since $A_n$ takes only the values $0$ and $1$, $1$-distribution means that the frequency of $1$'s exists and is the same in every arithmetic progression. Let
$$ \lambda=\Pr(A_n=1). $$
The same value $\lambda$ is obtained on each progression
$$ A_t,\ A_{t+s},\ A_{t+2s},\ldots . $$
Now choose $s=k$. For $0\le t<k$, the variable $A_{t+mk}$ depends only on the block
$$ U_{t+mk},U_{t+mk+1},\ldots,U_{t+mk+k-1}. $$
Different values of $m$ involve disjoint sets of indices. Since each progression subsequence of the original sequence is $1$-distributed, the limiting frequency of occurrences of the event
$$ U_{t+mk}\in I_1,\ldots,U_{t+mk+k-1}\in I_k $$
along such a progression equals the product of the individual frequencies,
$$ (v_1-u_1)\cdots(v_k-u_k). $$
Therefore every progression
$$ A_t,\ A_{t+k},\ A_{t+2k},\ldots $$
has frequency of $1$'s equal to
$$ (v_1-u_1)\cdots(v_k-u_k). $$
But every progression frequency equals $\lambda$; hence
$$ \lambda=(v_1-u_1)\cdots(v_k-u_k). $$
This is exactly (1). Since the intervals $I_1,\ldots,I_k$ were arbitrary, equation (5) holds for the chosen $k$.
Because $k$ was arbitrary, the sequence is $k$-distributed for every positive integer $k$. By Definition C, the sequence is $\infty$-distributed.
Thus every sequence satisfying the weakened version of R4 already satisfies the original version.
Verification
For an arbitrary $k$ and arbitrary intervals $I_1,\ldots,I_k$, the indicator sequence
$$ A_n=\mathbf1!\left(U_n\in I_1,\ldots,U_{n+k-1}\in I_k\right) $$
inherits the weakened R4 property.
Applying that property to the progression classes modulo $k$ shows that the density of occurrences of the block event is identical on every residue class modulo $k$.
Within a fixed residue class modulo $k$, successive occurrences involve disjoint $k$-blocks. The assumed $1$-distribution of all progression subsequences gives the expected density
$$ (v_1-u_1)\cdots(v_k-u_k). $$
Hence the global density of the block event is this same product, which is exactly the condition of $k$-distribution.
Since this argument holds for every $k$, the sequence is $\infty$-distributed.
Notes
The conclusion is that the proposed weakening of Definition R4 is not actually weaker. Requiring every arithmetic-progression subsequence to be merely $1$-distributed already forces all higher-order distribution properties. Therefore the modified definition and the original Definition R4 characterize the same class of sequences.
$$ \boxed{\text{The weaker definition is equivalent to Definition R4; no counterexample exists.}} $$