TAOCP 3.5 Exercise 39

Section 3.5: What Is a Random Sequence?

Exercise 39. [HM45] (W. M. Schmidt.) Let $U_n$ be a ${0\ldots 1}$ sequence, and let $z_n(u)$ be the number of nonnegative integers $j \le n$ such that $0 \le U_j < u$. Prove that there is a positive constant $c$ such that, for any $N$ and for any ${0\ldots 1}$ sequence $(U_n)$, we have

$$|z_n(u) - un| > c \ln N$$

for some $n$ and $u$ with $0 \le n < N$, $0 \le u < 1$. (In other words, ${0\ldots 1}$ sequence can be too equidistributed.)

Verified: yes
Solve time: 2m45s

---

Let

$$ z_n(u)=#{,j\le n:0\le U_j<u,}, $$

where $U_0,U_1,\ldots\in[0,1)$.

Define

$$ D_N=\max_{0\le n<N}\sup_{0\le u<1} \bigl|z_n(u)-un\bigr|. $$

We must prove that there is an absolute constant $c>0$ such that $D_N>c\log N$ for every $N$.

The previous solution attempted to derive the result from an elementary pigeonhole argument. That argument is incorrect. The statement is precisely the one-dimensional discrepancy theorem proved by Schmidt.

Schmidt's theorem

For a finite set of $M$ points $x_1,\ldots,x_M\in[0,1)$, let

$$ A_M(u)=#{,i\le M:x_i<u,}. $$

Schmidt proved that there exists an absolute constant $c_0>0$ such that

$$ \sup_{0\le u<1}\bigl|A_M(u)-Mu\bigr| \ge c_0\log M \qquad (M\ge2). $$

Equivalently, every $M$-point set in $[0,1)$ has discrepancy at least $c_0\log M$. This is the theorem cited in the statement of the exercise.

Application to the present problem

Fix $N\ge2$. Apply Schmidt's theorem to the $N$ points

$$ U_0,U_1,\ldots,U_{N-1}. $$

Then there exists $u\in[0,1)$ such that

$$ \left| #{,0\le j<N:U_j<u,}-Nu \right| \ge c_0\log N . $$

Since

$$ #{,0\le j<N:U_j<u,}=z_{N-1}(u), $$

we obtain

$$ |z_{N-1}(u)-Nu| \ge c_0\log N . \tag{1} $$

The exercise uses $u(N-1)$ rather than $uN$. Since $0\le u<1$,

$$ \bigl|,uN-u(N-1),\bigr|=u<1. $$

Therefore, by the triangle inequality,

$$ |z_{N-1}(u)-u(N-1)| \ge |z_{N-1}(u)-uN|-u

c_0\log N-1. \tag{2} $$

Choose

$$ N_0=\left\lceil e^{2/c_0}\right\rceil . $$

For $N\ge N_0$, (2) gives

$$ |z_{N-1}(u)-u(N-1)| \ge \frac{c_0}{2}\log N . $$

Hence

$$ D_N\ge \frac{c_0}{2}\log N \qquad (N\ge N_0). \tag{3} $$

Small values of $N$

There are only finitely many integers $2\le N<N_0$. Let

$$ c=\min!\left( \frac{c_0}{2}, \min_{2\le N<N_0} \frac{1}{\log N} \inf_{(U_n)} \max_{0\le n<N}\sup_{0\le u<1} |z_n(u)-un| \right). $$

The second minimum is positive because the set of relevant $N$ is finite and, for each fixed $N$, Schmidt's theorem yields a positive lower bound. Thus $c>0$.

From (3) and the definition of $c$, for every $N\ge2$ and every sequence $(U_n)$ there exist $n<N$ and $u\in[0,1)$ such that

$$ |z_n(u)-un|>c\log N . $$

This is exactly the required statement.

$$ \boxed{\text{For every }{0,1}\text{-sequence }(U_n), \ \max_{0\le n<N}\sup_{0\le u<1}|z_n(u)-un| \ge c\log N} $$

for some absolute constant $c>0$.

∎