The Central Limit Theorem Says Nothing About the Tails: Large Deviations of Sums — Epoche C1
A number that shows the problem Toss a fair coin one hundred times. The probability that every toss lands heads is exactly $2^{-100}$, which is $7.9 \times 10^{-31}$. Now compute the same probability with the normal approximation supplied by the central limit theorem: the count of heads has mean $50$ and standard deviation $\sqrt{100 \times \tfrac14} = 5$, so a count of $100$ is ten standard deviations above the mean, and the upper tail of the standard normal distribution beyond ten gives $7.6 \times 10^{-24}$. The approximation is too large by a factor of ten million. Refinements such as the continuity correction change the answer by a factor of order one; they do not touch the seven orders of magnitude. This essay is about that discrepancy: why the central limit theorem is silent here rather than merely imprecise, what replaces it, and where the replacement in turn fails. What the theorem asserts, and the exact sense in which it says nothing Let $X_1, X_2, \dots$ be independent random variables with the same distribution, with mean $\mu$ and finite variance $\sigma^2$, and write $S_n = \sum_{i=1}^{n} X_i$ for their sum. The central limit theorem states that the normalised sum $$ S_n^{*} = \frac{S_n - n\mu}{\sigma\sqrt{n}} $$ converges in distribution to the standard normal law $N(0,1)$. Convergence in distribution means precisely this: for each fixed real number $a$, the probability $P(S_n^{*} \le a)$ tends to $\Phi(a)$, the normal distribution function evaluated at $a$, as $n$ grows. The quantifier order is the whole story. The number $a$ is fixed first and the limit is taken afterwards, so the theorem constrains only quantities in which the threshold is held still while $n$ runs away. The original version of this essay said that the theorem gives "only a crude approximation" for a threshold of the form $n\mu + a\sigma\sqrt{n}$ with $a$ a large constant. That is not right, and the correction locates the real difficulty. For any constant $a$, however large, the theorem gives exactly the right limiting answer; the approximation to $P(S_n^{*} > a)$ improves without bound as $n$ increases. The failure occurs when the threshold is not held fixed — when the deviation of interest grows with the sample size, as it does in every application where one wants the probability that an average lands at a value some distance from its mean rather than some number of shrinking standard deviations from it. The silence can be made rigorous, and this is worth doing because it is stronger than a complaint about accuracy. The Berry–Esseen theorem bounds how far the true distribution function can be from the normal one: if the third absolute central moment $\rho = E|X_1 - \mu|^3$ is finite, then $$ \sup_{a \in \mathbb{R}} \left| P(S_n^{*} \le a) - \Phi(a) \right| \le \frac{C\rho}{\sigma^3 \sqrt{n}}, $$ where $C$ is an absolute constant, for which values below $0.5$ have been established. This is the best that can be said uniformly, and the bound is on the absolute error. Now consider the coin example: with $n = 100$ the bound permits an absolute error of roughly $0.05$, while the probability being estimated is $10^{-31}$. The bound is thirty orders of magnitude larger than the quantity it bounds, so it permits the true value to be anything at all in the relevant range. The theorem does not give a poor estimate of the tail. It gives no estimate of the tail. That is the content of the title. How far out the approximation can still be trusted The reader entitled to ask the practical question — at what point does the normal approximation stop being usable? — can be given a definite answer, and it is not in the original essay. The relevant result is Cramér's theorem on moderate deviations, refined by later authors and set out in Petrov's 1975 monograph. Suppose the moment generating function $E[e^{\lambda X_1}]$ is finite for all $\lambda$ in some interval around zero. Then the ratio of the true tail probability to the normal one, $$ \frac{P(S_n^{*} > x)}{1 - \Phi(x)}, $$ tends to $1$ as $n \to \infty$ provided $x$ grows more slowly than $n^{1/6}$. The exponent arises because the leading correction term in the expansion is of size $x^3/\sqrt{n}$, and that quantity tends to zero exactly when $x = o(n^{1/6})$. The number is easy to hold on to. With a million observations, $n^{1/6} = 10$, so the normal approximation is relatively accurate out to about ten standard deviations; with ten thousand observations, $n^{1/6} \approx 4.6$. Beyond that the relative error is not small, and the estimate degrades not gradually but exponentially. Where the exponential rate comes from The original essay introduced the rate function as a Legendre–Fenchel transform without saying where the transform comes from, which leaves the central formula of the subject looking like a definition adopted for convenience. It is not: it falls out of optimising an elementary bound, and the derivation takes four lines. Start from Markov's inequality, which says that for a non-negative random variable $Y$ and any $t > 0$, $P(Y \ge t) \le E[Y]/t$. It is immediate from the fact that $Y \ge t\,\mathbf{1}\{Y \ge t\}$. Apply it not to $S_n$ itself but to $e^{\lambda S_n}$ for a parameter $\lambda > 0$, which is legitimate because exponentiating is increasing, so the events $\{S_n \ge nx\}$ and $\{e^{\lambda S_n} \ge e^{\lambda n x}\}$ are the same event. Then $$ P(S_n \ge nx) \le e^{-\lambda n x}\, E\!\left[e^{\lambda S_n}\right] = e^{-\lambda n x}\left(E\!\left[e^{\lambda X_1}\right]\right)^{n} = \exp\!\left(-n\left[\lambda x - K(\lambda)\right]\right), $$ where the middle equality uses independence to factorise the expectation of the product, and $K(\lambda) = \log E[e^{\lambda X_1}]$ is the cumulant generating function. This is Chernoff's bound, in the form given in his 1952 paper. It holds for every $\lambda > 0$, so the best of these bounds is obtained by maximising the exponent, and $$ I(x) = \sup_{\lambda \in \mathbb{R}} \left(\lambda x - K(\lambda)