TAOCP 3.5 Exercise 11

Exercise 11. [M10] Use Theorem C to prove that if a sequence $(U_n)$ is $\infty$-distributed, so is the subsequence $(U_{2n})$.

Verified: no
Solve time: 3m43s

Exercise 3.5.11 [M10]

Let $(U_n)$ be $\infty$-distributed. By definition, $(U_n)$ is $m$-distributed for every positive integer $m$.

To prove that $(U_{2n})$ is $\infty$-distributed, it suffices to show that it is $k$-distributed for every positive integer $k$.

Fix $k \ge 1$. Since $(U_n)$ is $\infty$-distributed, it is in particular $2k$-distributed. Hence the sequence of overlapping $2k$-tuples

$$ (U_n,U_{n+1},\ldots,U_{n+2k-1}), \qquad n=0,1,2,\ldots, $$

is uniformly distributed in the unit cube $[0,1]^{2k}$.

Apply Theorem C to these $2k$-tuples, projecting onto the coordinates numbered

$$ 1,3,5,\ldots,2k-1. $$

(These coordinate numbers refer to positions within the $2k$-tuple. Thus coordinate $1$ is $U_n$, coordinate $3$ is $U_{n+2}$, and so on.)

Theorem C implies that the projected $k$-tuples

$$ (U_n,U_{n+2},U_{n+4},\ldots,U_{n+2k-2}), \qquad n=0,1,2,\ldots, $$

are $k$-distributed.

Now consider only those projected tuples for which $n$ is even. Writing $n=2m$, we obtain

$$ (U_{2m},U_{2m+2},\ldots,U_{2m+2k-2}), \qquad m=0,1,2,\ldots, $$

which are exactly the overlapping $k$-tuples associated with the subsequence $(U_{2n})$.

Equivalently, these are

$$ (U_0,U_2,\ldots,U_{2k-2}), \quad (U_2,U_4,\ldots,U_{2k}), \quad (U_4,U_6,\ldots,U_{2k+2}), \quad \ldots $$

Therefore the subsequence $(U_{2n})$ is $k$-distributed.

Since $k$ was arbitrary, $(U_{2n})$ is $k$-distributed for every $k\ge1$. Hence, by definition,

$$ (U_{2n}) $$

is $\infty$-distributed.

$$ \boxed{\text{If }(U_n)\text{ is }\infty\text{-distributed, then }(U_{2n})\text{ is }\infty\text{-distributed.}} $$

∎