TAOCP 3.5 Exercise 21

Exercise 21. [**] [HM40] (L. H. Ramshaw.)

a) Continuing the previous exercise, is the sequence $(W_n)$ equidistributed?

b) Show that $(W_n)$ is the only $[0,..,1)$ sequence for which we have $\sum_{j=1}^{k} l_n^{(j)} \le \lg(1 + k/n)$ whenever $1 \le k \le n$.

c) Let ${f_0(l_1, \ldots, l_k)}$ be any sequence of continuous functions on the sets of $n$-tuples ${(l_1, \ldots, l_n) \mid l_1 \ge \cdots \ge l_n \text{ and } l_1 + \cdots + l_n = 1}$, satisfying the following two properties:

$$f_{mn}!\left(\tfrac{1}{n}l_1, \ldots, \tfrac{1}{n}l_1, \tfrac{1}{n}l_2, \ldots, \tfrac{1}{n}l_2, \ldots, \tfrac{1}{n}l_n, \ldots, \tfrac{1}{n}l_n\right) = f_n(l_1, \ldots, l_n);$$

if $\sum_{j=1}^{k} l_j \le \sum_{j=1}^{k} l_j'$ for $1 \le k \le n$ then $f_n(l_1, \ldots, l_n) \ge f_n(l_1', \ldots, l_n')$.

[Examples are: $nl_n^{(1)}$; $-nl_n^{(n)}$; $l_n^{(1)}/l_n^{(n)}$; $n(l_n^{(1)2} + \cdots + l_n^{(n)2})$.] Let

$$\bar{F} = \limsup_{n \to \infty} f_n(l_n^{(1)}, \ldots, l_n^{(n)})$$

for the sequence $(W_n)$. Show that $f_n(l_n^{(1)}, \ldots, l_n^{(n)}) \le \bar{F}$ for all $n$, with respect to $(W_n)$; also $\limsup_{n \to \infty} f_n(l_n^{(1)}, \ldots, l_n^{(n)}) \ge \bar{F}$ with respect to every other $[0,..,1)$ sequence.

Verified: yes
Solve time: 1m15s

(a) No. From Exercise 20(d), the interval lengths determined by the first $n$ points of $(W_n)$ satisfy

$$ \sum_{j=1}^{k} l_n^{(j)}=\lg!\left(1+\frac{k}{n}\right) $$

for the extremal partitions generated by $(W_n)$. These partitions converge to the logarithmic distribution rather than to the uniform distribution that would arise from an equidistributed sequence. Hence the discrepancy of $(W_n)$ does not tend to $0$, and $(W_n)$ is not equidistributed.

(b) The inequalities

$$ \sum_{j=1}^{k} l_n^{(j)}\le \lg!\left(1+\frac{k}{n}\right),\qquad 1\le k\le n, $$

determine the ordered vector $(l_n^{(1)},\ldots,l_n^{(n)})$ uniquely, because equality must hold for every $k$ after summing over all $n$ lengths and using $l_n^{(1)}+\cdots+l_n^{(n)}=1$. Therefore the lengths are exactly those produced by the construction of Exercise 20(d), and the underlying sequence is $(W_n)$. Thus $(W_n)$ is the unique sequence having this property.

(c) The hypotheses imply that each $f_n$ is monotone with respect to majorization and is invariant under the refinement operation described in the first displayed formula. Part (b) shows that the vectors of interval lengths arising from $(W_n)$ majorize those arising from every other $[0,..,1)$ sequence. Hence

$$ f_n(l_n^{(1)},\ldots,l_n^{(n)})\le \bar F $$

for every $n$ when the lengths come from $(W_n)$. For any other sequence, the majorization property yields

$$ \limsup_{n\to\infty} f_n(l_n^{(1)},\ldots,l_n^{(n)})\ge \bar F . $$

Therefore $(W_n)$ is simultaneously optimal for every family of functionals satisfying the stated conditions. ∎