Quantitative Cesaro Sums
18 Nov 2020 - Tags: quick-analysis-tricks
To the surprise of no one, I was on math stackexchange earlier and saw an interesting analysis question. I have a weird fascination with tricky limit questions because I feel like I’ve always been bad at them. I like working on them for the same reason I like practicing the difficult parts of pieces of music – it makes me feel like I’m improving (in a “no pain no gain” kind of way).
Anyways, the question was as follows (paraphrased):
Compute the following limit
The beginning of the solution makes sense: We want to approximate the
Then (rewriting as a summation as well) we get
Now here’s the clever idea: We use Cesàro Averages backwards! This is mentioned in a comment on the original mse question, and it’s a trick I’ll absolutely have to remember!
To explain what I mean, let’s take a quick detour into the world of Cesàro Averages:
If
People care about the Cesàro averages because it’s possible for the Cesàro averages to converge even if the original series doesn’t. Moreover, the notion of “averaging” in this way comes up very naturally in Fourier Analysis (see here) and Ergodic Theory (see here).
The fundamental theorem in this area is this:
Whenever
So the notion of Cesàro convergence is a true generalization of the original notion of convergence. It allows us to evaluate certain limits that used to be divergent, but it doesn’t mess up any limits that already converged.
And now we get to the application here:
We recognize
So we did properly figure out what the limit should be… But I did a little bit of sleight of hand in the above manipulation. Did you catch it?
As people interested in computer science, we have to be slightly pickier than a lot of mathematicians when it comes to computing limits. It’s often important exactly how quickly we get convergence2, and so we kept track of the big-Oh for the whole problem.
But above we just substituted
Say
So the error in the Cesàro averages is the average of the errors. Let’s see how this comes up in our analysis of this particular problem.
First, we need to know the error bounds on
Now we can find the error of the Cesàro averages:
While this is technically true, I would argue it isn’t useful yet. We can clean it up.
The important observation is that, for
Notice we can safely assume
Importantly, this error bound is different from the error bound of our original series! As expected, this converges slightly slower (by a log factor) because it’s being weighed down by earlier terms in the series.
Why go through this pain, though? Because now we can finally put a nice bow on things: How quickly does the limit converge?
-
A notational quirk I picked up from Ryan O’Donnell that my brain likes: I will only ever write
when is a positive function. So I meaningfully distinguish between and .This is a pretty minor thing, but it’s led to notably more comfort on my part, since my brain tends to implicitly make positivity assumptions when I’m not looking. Explicitly writing down when things can be negative forces my brain to pay extra attention to it. ↩
-
In fact, since I have Ryan O’Donnell on the brain, I audited his Theorist’s Toolkit class during my year off. In one of the lectures, he asserted the Central Limit Theorem was the most useless theorem in mathematics. Of course, he was being intentionally inflammatory. He prefaced that statement with some history – the Central Limit Theorem got its name not (as I originally thought) because summing random variables “tends to lie at the center” of a gaussian. It’s because Pólya thought it was the most important result in probability. It was central to the field.
Ryan went on to tell us about the Berry-Esseen Theorem, which gives good error bounds on the convergence guaranteed by the Central Limit Theorem. ↩
-
As a quick exercise, why do we get an upper bound here? We prove the harmonic series diverges by lower bounding it… ↩