Using Probability to Make Difficult Limits Obvious

05 Jan 2022 - Tags: quick-analysis-tricks

Hands down one of my worst subjects is probability, which is a shame because it’s the source of a lot of powerful arguments, both formal and heuristic. I remember struggling with the analysis of randomized algorithms, and the closely related probabilistic method in combinatorics was no easier. Of course, the more you work with these things the easier they become, and I’m starting to feel a bit better about the basics at least¹. One pattern that I’ve seen a few times recently was so slick that I wanted to write something up about it in my first “quick analysis tricks” post in a little while!

For the uninitiated, “quick analysis tricks” is a series I do where I state analysis facts that are probably super obvious to anyone who knows them, despite these facts not being obvious to me. It’s easy to forget what is and isn’t obvious to newcomers in an area, and oftentimes these little “obvious” facts aren’t actually written down anywhere. You’re supposed to just pick them up over time. I know seeing some of these written out would have helped me, so I’m writing them up for the students of the future (and also in a desparate bid to try and remember them myself :P).

Now, let’s take a look at the mse question that inspired this post²:

All I have to say is

If you’re anything like me, your first question upon seeing this is something of the form “How do people come up with this stuff³?”.

Your next question is probably “How can we tackle this?” For me, at least, it’s entirely opaque how we might proceed.

As you might have guessed from the title of this post, the answer to both of these questions lies in probability theory. So let’s take a brief detour into the world of Poisson Distributions.

We know that there’s no uniform distribution on $\mathbb{N}$ (which is a cute exercise if you’re not familiar with this theorem), but obviously we want to be able to randomly choose some $n \in \mathbb{N}$. The solution is to weight higher numbers as less likely, with the probabilities decaying quickly enough for the sum to converge. One of the most obvious ways to do this is with the Poisson Distribution, where we say

\[\mathbb{P}(X = k) = e^{-1} \frac{1}{k!}\]

The $e^{-1}$ out front is chosen so that $\sum_k \mathbb{P}(X = k) = 1$. It turns out that a useful generalization⁴ of this obvious distribution is to add a parameter $\lambda > 0$:

\[\mathbb{P}(X = k) = e^{-\lambda} \frac{\lambda^k}{k!}\]

Now we need a quick fact about poisson distributions. Namely:

So now here’s the idea. It’s intuitively clear that if we keep picking random $X_k$s from the same distribution, we would expect the average $\frac{1}{n} \sum_{k \leq n} X_k$ to approach $\mathbb{E}[X_k]$. This is basically the law of large numbers, and now we’re ready to see how someone might have come up with the theorem we’re proving:

The clever trick is to choose our point of interest $x$ to be the parameter in a poisson variable! Then by the law of large numbers⁵, we’ll know that, if the $X_k$ are iid poisson with parameter $x$:

\[\frac{1}{n} \sum_{k \leq n} X_k \to \mathbb{E}[X_k] = x\]

So, intuitively then, we would expect

\[f \left ( \frac{1}{n} \sum_{k \leq n} X_k \right ) \to f(x).\]

In fact, if we take expectations of both sides⁶, we can make this dream a reality!

Since the $X_k$ are all poisson with parameter $x$, the sum $S_n = \sum_{k \leq n} X_k$ is poisson with parameter $nx$. That is

\[\begin{align} \underset{X_k \sim \text{Poisson}(x)}{\mathbb{E}} \left [ f \left ( \frac{1}{n} \sum_{k \leq n} X_k \right ) \right ] &= \underset{S_n \sim \text{Poisson}(nx)}{\mathbb{E}} \left [ f \left ( \frac{S_n}{n} \right ) \right ] \\ &= \sum_{j = 1}^\infty f \left ( \frac{j}{n} \right ) \mathbb{P}(S_n = j) \\ &= \sum_{j = 1}^\infty f \left ( \frac{j}{n} \right ) e^{-nx} \frac{(nx)^j}{j!} \end{align}\]

and now some measure theoretic jiggery-pokery⁷ shows that this indeed converges to $f(x)$ as $n \to \infty$.

Which is exactly what we set out to show!

---

Let’s see another example in the same vein which I learned years ago⁸:

Recall the Stone-Weierstrass Theorem says that any continuous function on $[0,1]$ can be (uniformly) approximated by polynomials⁹.

Wouldn’t it be nice to know how to find these polynomials explicitly? Well probability comes to the rescue again!

Notice the similarities between this limit and the previous one. Both are limits of the form

\[\displaystyle \lim_{n \to \infty} \sum_k \text{gross stuff}(x) \ f \left ( \frac{k}{n} \right ) \to f(x)\]

where the “gross stuff” looks like some kind of probability distribution. In the previous example it was poisson, and now it’s binomial¹⁰.

We ask why $p_n \to f$, and in the context of this post the idea should be clear!

If $X_n$ is binomially distributed (over $n$ trials) with parameter $x$, then

\[\mathbb{E}[X_n] \to nx\]

This is saying that, given a coin which lands heads with probability $x$, if we flip it $n$ times (for large values of $n$) we expect $nx$ many heads (which is entirely obvious).

Again, we now look at $f \left ( \frac{X_n}{n} \right )$, which we expect to converge to $f \left ( \frac{nx}{n} \right ) = f(x)$. Indeed, we find

\[\begin{align} \underset{X_n \sim \text{Binomial}(x,n)}{\mathbb{E}} \left [ f \left ( \frac{X_n}{n} \right ) \right ] &= \sum_{j=0}^n f \left ( \frac{j}{n} \right ) \mathbb{P}(X_n = j) \\ &= \sum_{j=0}^n f \left ( \frac{j}{n} \right ) \binom{n}{j} x^j (1-x)^{n-j} \end{align}\]

And again, I’ll leave out the finer points of the derivation, where we actually show this converges to $f(x)$. This is a quick application of Chebyshev’s Inequality (which, you’ll notice, can be made uniform in $x$ since the standard deviation of $X_n$ is bounded)¹¹.

---

Next time you’re faced with a tricky limit that looks like some kind of “weighted average” of points of $f$ in order to approximate $f(x)$, try viewing it as an expectation with respect to some probability distribution! Then the law of large numbers will basically hand you the desired claim ^_^.

Of course, this is only one way that probability can show up in unexpected places. There’s a whole mathoverflow thread dedicated to this, which might be worth browsing through if you’re looking for other ones!

Now, though, I’m off to bed. See you soon!

---