TAOCP 4.2.4 Exercise 9
Let the averaging operator of Eq.
Section 4.2.4: Distribution of Floating Point Numbers
Exercise 9. [HM25] (P. Diaconis.) Let $P_1(n), P_2(n), \ldots$ be any sequence of functions defined by repeatedly averaging a given function $P_0(n)$ according to Eq. (9). Prove that $\lim_{n \to \infty} P_m(n) = P_0(1)$ for all fixed $n$.
Verified: yes
Solve time: 2m05s
Solution
Let the averaging operator of Eq. (9) be
$$ P_{m+1}(n)=\frac1n\sum_{k=1}^{n}P_m(k). $$
We must prove that for every fixed positive integer $n$,
$$ \lim_{m\to\infty}P_m(n)=P_0(1). $$
Write
$$ a_m(n)=P_m(n)-P_0(1). $$
Since averaging preserves constants,
$$ a_{m+1}(n)=\frac1n\sum_{k=1}^{n}a_m(k), \qquad a_m(1)=0 $$
for all $m\ge0$. It suffices to show that
$$ \lim_{m\to\infty}a_m(n)=0 $$
for each fixed $n$.
We proceed by induction on $n$.
For $n=1$,
$$ a_m(1)=0 $$
for every $m$, so the assertion is true.
Assume that
$$ \lim_{m\to\infty}a_m(k)=0 $$
for all $k<n$. Since $n$ is fixed,
$$ a_{m+1}(n) =\frac1n\sum_{k=1}^{n}a_m(k) =\frac1n a_m(n) +\frac1n\sum_{k=1}^{n-1}a_m(k). $$
Define
$$ b_m=\frac1n\sum_{k=1}^{n-1}a_m(k). $$
By the induction hypothesis, each sequence $a_m(k)$ with $k<n$ tends to $0$; therefore
$$ b_m\to0. $$
Hence
$$ a_{m+1}(n)=\frac1n a_m(n)+b_m. $$
Let
$$ c_m=a_m(n). $$
Then
$$ c_{m+1}=\frac1n c_m+b_m, \qquad b_m\to0. $$
Fix $\varepsilon>0$. Choose $M$ so that
$$ |b_m|\le\varepsilon $$
for all $m\ge M$. For $m\ge M$,
$$ |c_{m+1}| \le \frac1n |c_m|+\varepsilon . $$
Iterating this inequality $t$ times gives
$$ |c_{M+t}| \le \frac{|c_M|}{n^t} +\varepsilon\sum_{j=0}^{t-1}\frac1{n^j}. $$
Since $n\ge2$,
$$ \sum_{j=0}^{t-1}\frac1{n^j} \le \frac1{1-1/n} =\frac{n}{n-1}. $$
Therefore
$$ \limsup_{m\to\infty}|c_m| \le \varepsilon\frac{n}{n-1}. $$
Because $\varepsilon$ is arbitrary,
$$ \limsup_{m\to\infty}|c_m|=0. $$
Thus $c_m\to0$, that is,
$$ a_m(n)\to0. $$
The induction is complete. Consequently,
$$ \lim_{m\to\infty}P_m(n) =P_0(1) $$
for every fixed $n$.
$$ \boxed{\lim_{m\to\infty}P_m(n)=P_0(1)} $$
This completes the proof.
∎