TAOCP 3.5 Exercise 10

In TAOCP §3.

taocpmathematicsalgorithmsvolume-2hm-medium

Section 3.5: What Is a Random Sequence?

Exercise 10. ▶ [HM22] Where was the fact that $m$ divides $q$ used in the proof of Theorem C?

Verified: no
Solve time: 3m46s

Solution

In TAOCP §3.5, Theorem C states that if a sequence $\langle U_n\rangle$ is $(m,k)$-distributed, then for any integer $q > 0$ divisible by $m$ and for all integers $h$ with $0 \le h < m^k$, we have

$$ #{ n : 0 \le n < q,\ U_n \in I_h} = \frac{q}{m^k}, $$

where $I_h$ is the $h$-th subinterval of $[0,1)$ in the standard partition into $m^k$ equal parts.

The proof of Theorem C relies directly on the definition of $(m,k)$-distribution. A sequence $\langle U_n\rangle$ is $(m,k)$-distributed if, for every block of length $m^k$, each $k$-tuple of $m$-adic digits occurs exactly once. Equivalently, each subinterval $I_h$ of length $1/m^k$ contains exactly one term of the sequence in every block of length $m^k$.

Knuth proves Theorem C by partitioning the first $q$ terms of the sequence into consecutive blocks of length $m^k$. Specifically, he writes

$$ q = t m^k, $$

where $t = q / m^k$ is an integer. Then the interval $0 \le n < q$ is decomposed as

$$ [0, q) = [0, m^k) \cup [m^k, 2 m^k) \cup \dots \cup [(t-1) m^k, t m^k). $$

By the $(m,k)$-distribution property, each block $[j m^k, (j+1) m^k)$ contains exactly one term in each subinterval $I_h$. Summing over the $t$ blocks, the total number of points in $I_h$ is

$$ \sum_{j=0}^{t-1} 1 = t = \frac{q}{m^k}. $$

This proves equation (13).

The assumption that $m \mid q$ is used exactly at the step where $q$ is expressed as $q = t m^k$. Without this divisibility, the first $q$ terms cannot be partitioned into an integer number of complete blocks of length $m^k$. The proof relies on counting entire blocks of length $m^k$ because the $(m,k)$-distribution property guarantees exactly one point per subinterval $I_h$ in each block. If $q$ were not divisible by $m^k$, there would be a leftover segment shorter than $m^k$, and the argument would fail because the property does not specify the distribution of points in incomplete blocks.

Thus, the hypothesis $m \mid q$ enters precisely when Knuth decomposes the first $q$ terms into $t$ blocks of length $m^k$ in order to apply the $(m,k)$-distribution property to each block and sum the counts. No other part of the proof requires this divisibility. ∎

This version:

  1. Correctly identifies the block length $m^k$ relevant to the $(m,k)$-distribution.
  2. Locates the exact step where the divisibility condition $m \mid q$ is needed.
  3. Avoids reconstructing unrelated arguments about blocks of length $m$.
  4. Provides full justification for the counting step.