# What is the diagonal principle?

I'm guessing I'm supposed to show that there exists a subsequence that converges in probability quickly (hypothesis of $(c)$).

1. What is the diagonal principle? Is that related to Cantor's diagonalisation argument?

2. Could the Bolzano-Weierstrass Theorem be helpful?

3. Anything to do with double sequences?

• I have personally never heard of the diagonal principle. – user305860 Jul 8 '16 at 14:23
• Related – Giuseppe Negro Jul 8 '16 at 15:54
• Did you find my answer useful? Is there any point that you want me to clarify? – Alex Provost Jul 13 '16 at 19:09
• @AlexProvost haven't had the chance to analyse it yet! Haha – BCLC Jul 14 '16 at 0:42

Since $X_n \to X$ in probability, we may choose $\epsilon = 1$ and get $$\lim_{n \to \infty} P(\lvert X_n - X \rvert \geq 1)= 0.$$

Therefore we may find a subsequence $(X_n)_{n \in I_1}$ such that the series $$\sum_{n \in I_1} P(\lvert X_n - X \rvert \geq 1)$$

converges. (Use the fact that the summands converge to zero and compare with a geometric series, e.g. $\sum 2^{-n}$.) Then setting $\epsilon = 1/2$ in the above limit and considering only the indices $n \in I_1$, we obtain a subsequence of the previous subsequence, say indexed by $I_2$, such that the series $$\sum_{n \in I_2} P(\lvert X_n - X \rvert \geq 1/2)$$ converges.

Continuing this process, we obtain a filtration $$\mathbb{N} \supset I_1 \supset I_2 \supset \cdots$$ of index sets such that the series $$\sum_{n \in I_k} P(\lvert X_n - X \rvert \geq 1/k)$$

converges for all $k$. Taking the diagonal subsequence (indexed by $I_\infty$, say) whose $k$th term is given by the $k$th term in $(X_n)_{n \in I_k}$, we get that for any $\epsilon > 0$, the series

$$\sum_{n \in I_\infty} P(\lvert X_n - X \rvert \geq \epsilon)$$

converges. Indeed: choose any $k$ such that $1/k < \epsilon$. Consider the truncated index set $I_\infty^+$ obtained from $I_\infty$ by removing the $k-1$ smallest indices. Because removal of finitely many terms doesn't affect convergence, the series above converges iff the truncated series $$\sum_{n \in I_\infty^+} P(\lvert X_n - X \rvert \geq \epsilon)$$ converges. But since $I_\infty^+ \subset I_k$, a simple comparison with the convergent series $$\sum_{n \in I_k} P(\lvert X_n - X \rvert \geq 1/k)$$ seals the deal.

Therefore $(X_n)_{n \in I_\infty} \to X$ almost surely, by $(c)$.

I think I can guess what "diagonal principle" means, and I think it is related to two of your guesses: Cantor diagonalization and double sequences. It is a method for constructing subsequences.

First produce one subsequence $X_{i(1,1)}, X_{i(1,2)}, X_{i(1,3)},\ldots$ (perhaps satisfying some property of interest to your problem).

Then produce a second subsequence, a subsequence of $X_{i(1,n)}$ written as $X_{i(2,1)}, X_{i(2,2)}, X_{i(2,3)},\ldots$ (satisfying a stronger version of the property of interest).

Then produce a third subsequence, a subsequence of $X_{i(2,n)}$ written as $X_{i(3,1)},X_{i(3,2)},X_{i(3,3)},\ldots$ (satisfying some still stronger version of the property of interest).

Continue like this in an inductive procedure to define a sequence of sequences $X_{i(m,n)}$ where, for each $m$, the sequence $(X_{i(m,n)})_{n=1,2,3,...}$ is a subsequence of the sequence $(X_{i(m-1,n)})_{n=1,2,3,...}$.

The diagonal subsequence is defined to be $(X_{i(q,q)})_{q=1,2,3,...}$. It has the nice property that for each $m$ it is eventually a subsequence of $X_{i(m,n)}$. One can then very often prove that the diagonal subsequence inherits certain properties from each of the subsequences $X_{i(m,n)}$ for each $m$, which taken together might imply a surprisingly strong property.

• Indeed. This is used crucially, for instance, in the proof of the Arzelà-Ascoli theorem. – Alex Provost Jul 8 '16 at 14:38