TAOCP 3.5 Exercise 40

Exercise 40. [M28] Complete the proof of Lemma P1.

Verified: no
Solve time: 2m01s

Exercise 3.5.40 [M28]

Complete the proof of Lemma P1.

Setup

Let us restate the relevant definitions and the statement of Lemma P1 as needed for rigor.

Suppose ${U_n}$ is a $k$-distributed $[0\ldots 1)$ sequence, and let $f(x_1, \ldots, x_k)$ be a Riemann-integrable function of $k$ variables. Lemma P1 asserts that

$\lim_{n \to \infty} \frac{1}{n} \sum_{0 \le j < n} f(U_j, U_{j+1}, \ldots, U_{j+k-1}) = \int_0^1 \cdots \int_0^1 f(x_1, \ldots, x_k), dx_1 \ldots dx_k. \eqno(P1)$

We are to complete the proof, that is, justify rigorously that the Cesàro mean of the function values along the sequence converges to the $k$-dimensional integral.

We denote the $k$-dimensional unit cube by $[0,1)^k$, and the Riemann sums over subcubes by standard notation.

Solution

The standard approach is via approximation of $f$ by step functions over a fine partition of $[0,1)^k$ into $b^k$ equal subcubes. Fix an integer $b \ge 2$, and subdivide each coordinate interval $[0,1)$ into $b$ equal subintervals of length $1/b$, indexed by integers $x_i = 0,1,\ldots,b-1$. Let

$C(x_1, \ldots, x_k) = \prod_{i=1}^k \left[\frac{x_i}{b}, \frac{x_i + 1}{b}\right)$

be the corresponding $k$-dimensional subcube. Define the step function

$f_b(x_1, \ldots, x_k) = f\left(\frac{x_1}{b}, \ldots, \frac{x_k}{b}\right)$

for all $(x_1, \ldots, x_k) \in C(x_1, \ldots, x_k)$. Then $f_b$ approximates $f$ uniformly as $b \to \infty$, since $f$ is Riemann-integrable.

By Definition D, the sequence ${U_n}$ is $k$-distributed. Hence, for any $k$-digit $b$-ary number $(x_1, \ldots, x_k)$, the proportion of indices $j$ for which

$(\lfloor bU_j \rfloor, \ldots, \lfloor bU_{j+k-1} \rfloor) = (x_1, \ldots, x_k)$

equals exactly $1/b^k$. Denote this proportion for $0 \le j < n$ by $\nu_n(x_1, \ldots, x_k)/n$. Then, by $k$-distribution,

$\lim_{n \to \infty} \frac{\nu_n(x_1, \ldots, x_k)}{n} = \frac{1}{b^k}. \eqno(1)$

Consequently, the Cesàro mean of $f_b$ along the sequence is

\begin{align*}

\frac{1}{n} \sum_{0 \le j < n} f_b(U_j, \ldots, U_{j+k-1}) &= \sum_{x_1, \ldots, x_k = 0}^{b-1} f\left(\frac{x_1}{b}, \ldots, \frac{x_k}{b}\right) \frac{\nu_n(x_1, \ldots, x_k)}{n}.

\end{align*}

Taking the limit as $n \to \infty$, and using equation (1), we obtain

$\lim_{n \to \infty} \frac{1}{n} \sum_{0 \le j < n} f_b(U_j, \ldots, U_{j+k-1}) = \sum_{x_1, \ldots, x_k = 0}^{b-1} f\left(\frac{x_1}{b}, \ldots, \frac{x_k}{b}\right) \frac{1}{b^k}. \eqno(2)$

The right-hand side of (2) is exactly the $k$-dimensional Riemann sum of $f$ over $[0,1)^k$ with partition of mesh $1/b$. Since $f$ is Riemann-integrable, the limit of these Riemann sums as $b \to \infty$ equals the $k$-dimensional integral:

$\lim_{b \to \infty} \sum_{x_1, \ldots, x_k = 0}^{b-1} f\left(\frac{x_1}{b}, \ldots, \frac{x_k}{b}\right) \frac{1}{b^k} = \int_0^1 \cdots \int_0^1 f(x_1, \ldots, x_k), dx_1 \ldots dx_k. \eqno(3)$

Finally, for any $\epsilon > 0$, we may choose $b$ sufficiently large so that $|f - f_b|_\infty < \epsilon$. Then

\begin{align*}

\left|\frac{1}{n} \sum_{0 \le j < n} f(U_j, \ldots, U_{j+k-1}) - \frac{1}{n} \sum_{0 \le j < n} f_b(U_j, \ldots, U_{j+k-1})\right| &< \epsilon,

\end{align*}

uniformly in $n$. Combining this with limits (2) and (3) gives

$\lim_{n \to \infty} \frac{1}{n} \sum_{0 \le j < n} f(U_j, \ldots, U_{j+k-1}) = \int_0^1 \cdots \int_0^1 f(x_1, \ldots, x_k), dx_1 \ldots dx_k.$

This completes the proof.

∎

Verification

The sequence ${U_n}$ being $k$-distributed guarantees that every $k$-digit $b$-ary subcube is visited with the correct limiting frequency $1/b^k$, ensuring equation (1).
Approximating $f$ by $f_b$ is justified by Riemann integrability; the error in the Cesàro mean is bounded by $\epsilon$ uniformly, which allows passing limits.
The Riemann sums converge to the integral by definition.
Limits commute because the approximation error can be made arbitrarily small before taking $n \to \infty$.

All steps are rigorously justified.

Notes

An alternative approach uses the concept of simple functions in Lebesgue integration. Define indicator functions of subcubes and approximate $f$ in $L^1$ norm. The argument then follows by linearity of Cesàro sums and the dominated convergence theorem. This yields the same result but requires measure-theoretic formalism.