12 | November | 2012 | Eventually Almost Everywhere

Taking a course on Large Deviations has forced me to think a bit more carefully about what happens when you have large collections of IID random variables. I guess the first thing think to think about is ‘What is a Large Deviation‘? In particular, how large or deviant does it have to be?

Of primary interest is the tail of the distribution function of $S_n=X_1+\ldots+X_n$ , where the $X_i$ are independent and identically distributed as $X$ . As we can always negate everything later if necessary, we typically consider the probability of events of the type:

$\mathbb{P}(S_n\geq \theta(n))$

where $\theta(n)$ is some function which almost certainly increases fairly fast with $n$ . More pertinently, if we are looking for some limit which corresponds to an actual random variable, we perhaps want to look at lots of related $\theta(n)$ s simultaneously. More concretely, we should fix $\theta$ and consider the probabilities

$\mathbb{P}(\frac{S_n}{\theta(n)}\geq \alpha).$ (*)

Throughout, we lose no generality by assuming that $\mathbb{E}X=0$ . Of course, it is possible that this expectation does not exist, but that is certainly a question for another post!

Now let’s consider the implications of our choice of $\theta(n)$ . If this increases with $n$ too slowly, and the likely deviation of $S_n$ is greater than $\theta(n)$ , then the event might not be a large deviation at all. In fact, the difference between this event and the event ( $S_n$ is above 0, that is, its mean) becomes negligible, and so the probability at (*) might be 1/2 or whatever, regardless of the value of $\alpha$ . So object $\lim \frac{S_n}{\theta(n)}$ whatever that means, certainly cannot be a proper random variable, as if we were to have convergence in distribution, this would imply that the limit RV consisted of point mass at each of $\{+\infty, -\infty\}$ .

On the other hand, if $\theta(n)$ increases rapidly with $n$ , then the probabilities at (*) might become very small indeed when $\alpha>0$ . For example, we might expect:

$\lim_{n\rightarrow\infty}\mathbb{P}(\frac{S_n}{\theta(n)}\geq \alpha)=\begin{cases}0& \alpha>0\\1&\alpha<0.\end{cases}$

and more information to be required when $\alpha=0$ . This is what we mean by a large deviation event. Although we always have to define everything concretely in terms of some finite sum $S_n$ , we are always thinking about the behaviour in the limit. A large deviation principle exists in an enormous range of cases to show that these probabilities in fact decay exponentially. Again, that is the subject for another post, or indeed the lecture course I’m attending.

Instead, I want to return to the Central Limit Theorem. I first encountered this result in popular science books in a vague “the histogram of boys’ heights looks like a bell” kind of way, then, once a normal random variable had been to some extent defined, it returned in A-level statistics courses in a slightly more fleshed out form. As an undergraduate, you see it in several forms, including as a corollary following from Levy’s convergence theorem.

In all applications though, it is generally used as a method of calculating good approximations. It is not uncommon to see it presented as:

$\mathbb{P}(a\sigma\sqrt{n}+\mu n\leq S_n\leq b\sigma\sqrt{n}+\mu n)\approx \frac{1}{\sqrt{2\pi}}\int_a^b e^{-x^2/2}dx.$

Although in many cases that is the right way to think use it, it isn’t the most interesting aspect of the theorem itself. CLT says that the correct scaling of $\theta(n)$ so that the deviation probabilities lie between the two cases outline above is the same (that is, $\theta(n)=O(\sqrt{n})$ in some sense) for an enormous class of distributions, and in particular, most distributions that one might encounter in practice (ie finite mean, finite variance). There is even greater universality, as furthermore the limit distribution at this interface has the same form (some appropriate normal distribution) whenever $X$ is in this class of distributions. I think that goes a long way to explaining why we should care about the theorem. It also immediately prompts several questions:

What happens for less regular distributions? It is now more clear what the right question to ask in this setting might be. What is the appropriate scaling for $\theta(n)$ in this case, if such a scaling exists? Is there a similar universality property for suitable classes of distributions?
What is special about the normal distribution? The theorem itself shows us that it appears as a universal scaling limit in distribution, but we might reasonably ask what properties such a distribution should have, as perhaps this will offer a clue to a version of CLT or LLNs for less regular distributions.
We can see that the Weak Law of Large Numbers follows immediately from CLT. In fact we can say more, perhaps a Slightly Less Weak LLN, that

$\frac{S_n-\mu n}{\sigma \theta(n)}\stackrel{d}{\rightarrow}0$

whenever $\sqrt{n}<<\theta(n)$ . But of course, we also have a Strong Law of Large Numbers, which asserts that the empirical mean converges almost surely. What is the threshhold for almost sure convergence, because there is no a priori reason why it should be $\theta(n)=n$ ?

To be continued next time.

Weak Law of Large Numbers and Central Limit Theorem via the Levy’s continuity theorem. (maikolsolis.wordpress.com)

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Daily Archives: November 12, 2012

Large Deviations and the CLT

Related articles