A probabilistic proof of divergence of the harmonic series

Nicole Oresme (c. 1325 - 1382), an influential polymath who discovered the first known proof of divergence of the harmonic series.

When researching for my last blog post on large numbers, I had a lot of fun reading some very creative proofs of the divergence of the harmonic series [1,2]. In this post, I’m going to present (a slightly modified version of) my favourite one so far: a probabilistic proof based on the invariance of random i.i.d. sequences under reindexing, originally due to Omer Adelman [3]. I was originally planning to include this proof in the previous post, but as that got already longer than I had anticipated, I thought I’d better dedicate a post to it (which will also give me more space to flesh out the argument a bit). Before getting started with the proof, I have to mention that another very slick probabilistic proof of the divergence of the harmonic series has been given by Arnab Kumar Laha [4], it is most definitely worth a read!

The Proof

Now, onto the proof. Recall that our goal is to show the following

Theorem. The sum

\[H_n:= \sum_{k=1}^n\frac1k = 1 + \frac12 + \frac 13 + \cdots + \frac1n,\]

diverges as $n\to\infty$.

Proof. Let $X_1,X_2,\ldots$ be a sequence of i.i.d. random variables uniformly distributed on the unit interval, and denote by $R$ the (random) set of record times, namely:

\[R := \{n\in\mathbb N: X_n > X_j \text{ for all } j< n\}.\]

We claim that $R$ has almost surely infinitely many elements. To see this, we will need the following

Lemma. let $\sigma : \mathbb N \to \mathbb N$ be an injective mapping. Then, the sequences $X_1,X_2,\ldots$ and $X_{\sigma(1)},X_{\sigma(2)},\ldots$ have the same distribution.

Although this Lemma seems very obvious, proving it rigorously is still a nice little exercise in measure-theoretic probability, and I’ll thus include a full proof of it in the appendix. Assuming that the Lemma is true, let’s now show that $R$ has infinite cardinality: define for all $n\in\mathbb N$ the “no more records after time $n$” events:

\[A_n := \{X_j \le X_n \text{ for all } j> n\}.\]

By the Lemma applied to the injection $\sigma:k\mapsto k+ (n-m)$, we see that for any $n>m$, $A_n$ and $A_m$ have the same probability (and of course the same is true if $m<n$). We have thus shown that $\mathbb P(A_n) = \mathbb P(A_1)$ for all $n$, but it is not hard to see that $A_1$ has zero probability: indeed, denote by $A_1^{(N)}$ the event

\[A_1^{(N)} := \{X_j \le X_1 \text{ for all } 2\le j\le N\}.\]

It is easily seen (by another application of the Lemma, if you want to do it formally) that $A_1^{(N)}$ has probability $1/N$, since $X_1$ has same probabliity as $X_2, X_3,\ldots,X_N$ to be the maximum of these $N$ variables. It is also clear that

\[A_1^{(N+1)}\subseteq A_1^{(N)}, \text{ and } A_1 = \bigcap_{N=2}^\infty A_1^{(N)}.\]

Therefore, by monotonicity and continuity of probability measures, it follows that $\mathbb P(A_1) = \lim_{N\to\infty} 1/N = 0$. Going back to our random set $R$, we can thus conclude the following:

\[\mathbb P(R \text{ is finite}) = \mathbb P\left(\bigcup_{n=1}^\infty A_n\right) \le \sum_{n=1}^\infty \mathbb P(A_n) = \sum_{n=1}^\infty \mathbb P(A_1) = \sum_{n=1}^\infty 0 = 0.\]

So we have shown that the cardinal of $R$ is almost surely infinite. In particular, its expectation is also infinite. Now, recall by the same symmetry argument from above that the event

\[\{n\in R\} = \{ X_n > X_j \text{ for all } j< n\}\]

has probability $1/n$ by invariance under permutation. By Tonelli’s theorem for non-negative measurable functions, we can therefore exchange $\mathbb E$ and $\sum$ to conclude that

\[\infty = \mathbb E[|R|] = \mathbb E\left[\sum_{n=1}^\infty \mathbf{1}_{n\in R}\right] = \sum_{n=1}^\infty \mathbb P(n\in R) = \sum_{n=1}^\infty \frac 1n,\]

and so we are done. Neat, wasn’t it?

References

[1] Kifowit, Steven J., and Terra A. Stamps. “The Harmonic Series Diverges Again and Again.” AMATYC Review 27.2 (2006): 31–43.

[2] Kifowit, Steven J. “More proofs of divergence of the harmonic series.” Unpublished article available at http://skifowit.prairiestate.edu (2006).

[3] Adelman, Omer. “Σ∞: A Micro-Lesson on Probability and Symmetry.” The American Mathematical Monthly 114.9 (2007): 809–810.

[4] Laha, Arnab Kumar. “A proof of divergence of the harmonic series using probability theory.” International Journal of Mathematical Education in Science and Technology 37.4 (2006): 502-503.

Appendix

Proof of Lemma. We actually prove the lemma for any sequence of i.i.d. real-valued random variables. Let $\sigma:\mathbb N \to \mathbb N$ be injective, $d\in\mathbb N$ be any natural number, and $n_1,\ldots,n_d$ be a finite collection of distinct numbers. We will begin by showing that the random vectors $\vec X_d := (X_{n_1},\ldots, X_{n_d})$ and $\vec Y_d := (X_{\sigma(n_1)},\ldots, X_{\sigma(n_d)})$ have the same distribution. To that end, let $R_d := [a_1,b_1]\times \cdots\times [a_d, b_d]$ be a “rectangle”, and observe by the i.i.d. assumption on the $X_i$’s that

\[\mathbb P(\vec X_d \in R_d) = \prod_{i=1}^d \mathbb P(X_{n_i} \in [a_i, b_i]) = \prod_{i=1}^d \mathbb P(X_{i} \in [a_i, b_i]) = \prod_{i=1}^d \mathbb P(X_{\sigma(n_i)} \in [a_i, b_i]) = \mathbb P(\vec Y_d \in R_d).\]

Now it is clear that the collection $\mathcal R_d$ of all $d$-dimensional closed hyper-rectangles forms a $\pi$-system (i.e., is closed under finite intersections). Furthermore, (the algebra generated by) this collection is a subset of the collection $\mathcal A$ of measurable sets $A$ such that $\mathbb P(\vec X_d \in A) =\mathbb P(\vec Y_d \in A)$. By the continuity from above and below of probability measures, $\mathcal A$ is easily seen to be a monotone class, and therefore the monotone class theorem yields:

\[\sigma(\mathcal R_d) \subseteq \mathcal A,\]

where $\sigma(\mathcal R_d)$ denotes the $\sigma$-algebra generated by $\mathcal R_d$. It is immediate that the closed rectangles generate the whole Borel $\sigma$-algebra and so we have established that $\vec X_d := (X_{n_1},\ldots, X_{n_d})$ and $\vec Y_d := (X_{\sigma(n_1)},\ldots, X_{\sigma(n_d)})$ have the same distribution. Clearly, this holds for all choices of $d\in\mathbb N$ and disjoint $n_1,\ldots,n_d\in\mathbb N$.

Now that we’ve shown that the desired claim holds for finite-dimensional projections, all that’s left is to remember that the cylindrical $\sigma$-algebra generates the Borel $\sigma$-algebra on $\mathbb{R}^{\mathbb{N}}$. Indeed, with that fact in hand, we can essentially repeat the argument we gave previously: the cylinders form a $\pi$-system and the algebra they generate is a subset of the sets where the two distributions agree. A last application of the monotone class theorem thus yields that the sigma-algebra they generate is still a subset of the set where the two measures agree, so we are done. $\square$