17
$\begingroup$

I'm studying statistics, and would like to better understand the Central Limit Theorem. The proof I found on Wikipedia requires some previous knowledge I do not currently possess.

Is there a quick intuitive explanation you can give as to why this theorem is correct?

$\endgroup$
4
  • 1
    $\begingroup$ Have you seen this already? $\endgroup$ Dec 4 '10 at 11:50
  • $\begingroup$ @J. M., thanks for the link. Although, I didn't find a quick explanation that I understood, sadly. Specifically, I'm interested in why sampling any distribution (even a non-symmetric one) will lead to a normal, symmetric distribution, for large enough samples. $\endgroup$ Dec 4 '10 at 12:01
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Illustration_of_the_central_limit_theorem might help provide a little intuition. Great question, by the way! $\endgroup$ Dec 4 '10 at 12:39
  • 2
    $\begingroup$ Not to confuse you, but the CLT only applies in the finite second moment case (finite variance). Levy-Stable distributions are also a convergent distribution of sums of random variables. $\endgroup$
    – user4143
    Dec 4 '10 at 16:46
20
$\begingroup$

I don't think you should expect any short, snappy answers because I think this is a very deep question. Here is a guess at a conceptual explanation, which I can't quite flesh out.

Our starting point is something called the principle of maximum entropy, which says that in any situation where you're trying to assign a probability distribution to some events, you should choose the distribution with maximum entropy which is consistent with your knowledge. For example, if you don't know anything and there are $n$ events, then the maximum entropy distribution is the uniform one where each event occurs with probability $\frac{1}{n}$. There are lots more examples in this expository paper by Keith Conrad.

Now take a bunch of independent identically distributed random variables $X_i$ with mean $\mu$ and variance $\sigma^2$. You know exactly what the mean of $\frac{X_1 + ... + X_n}{n}$ is; it's $\mu$ by linearity of expectation. Variance is also linear, at least on independent variables (this is a probabilistic form of the Pythagorean theorem), hence

$$\text{Var}(X_1 + ... + X_n) = \text{Var}(X_1) + ... + \text{Var}(X_n) = n \sigma^2$$

but since variance scales quadratically, the variance of $\frac{X_1 + ... + X_n}{n}$ is actually $\frac{\sigma^2}{n}$; in other words, it goes to zero! This is a simple way to convince yourself of the (weak) law of large numbers.

So we can convince ourselves that (under the assumptions of finite mean and variance) the average of a bunch of iid random variables tends to its mean. If we want to study how it tends to its mean, we need to instead consider $\frac{(X_1 - \mu) + ... + (X_n - \mu)}{\sqrt{n}}$, which has mean $0$ and variance $\sigma^2$.

Suppose we suspected, for one reason or another, that this tended to some fixed limiting distribution in terms of $\sigma^2$ alone. We might be led to this conclusion by seeing this behavior for several particular distributions, for example. Given that, it follows that we don't know anything about this limiting distribution except its mean and variance. So we should choose the distribution of maximum entropy with a fixed mean and variance. And this is precisely the corresponding normal distribution! Intuitively, each iid random variable is like a particle moving randomly, and adding up the contributions of all of the random particles adds "heat," or "entropy," to your system. (I think this is why the normal distribution shows up in the description of the heat kernel, but don't quote me on this.) In information-theoretic terms, the more iid random variables you sum, the less information you have about the result.

$\endgroup$
1
  • $\begingroup$ (+1) Given that we want a given mean and variance, maximum entropy and the calculus of variations lead directly to the normal distribution. Using the machinery of Fourier Transforms (see this answer for a start), we can derive the Gaussian distribution as a weak limit of a contraction of convolutions of any distribution with mean $0$ and variance $1$. $\endgroup$
    – robjohn
    Mar 26 '20 at 16:31
7
$\begingroup$

There's an almost-formal argument using cumulants. Given a random variable $X$, define its moment generating function $$M(X) = E[e^{tX}].$$ It's called the moment generating function since opening the Taylor series of the exponential, we get $$M(X) = 1 + E[X]t + \frac{1}{2}E[X]^2t^2 + \cdots.$$ The moment generating function is useful because of its relation to convolution of two independent random variables: $$M(X+Y) = E[e^{t(X+Y)}] = E[e^{tX}e^{tY}] = E[e^{tX}]E[e^{tY}] = M(X)M(Y).$$ One proof of the CLT takes the route of the mgf, but we would like to replace the multiplication by a addition since we only really know how to handle sums. So we define the cumulant generating function $$K(X) = \log M(X).$$ We can calculate the first few coefficients (which are called cumulant) by substituting into the (formal) power series of $\log(1+x) = x - x^2/2 + \cdots$: $$K(X) = \log (1+E[X]t+E[X^2]t^2/2 + \cdots) = E[X]t + E[X^2]t^2/2 - (E[X]^2t^2 + E[X]E[X^2]t^3 + E[X^2]t^4/4)/2 + \cdots = E[X]t + V[X]t^2/2 + \cdots.$$ Also, if $X$ and $Y$ are independent then $$K[X+Y] = K[X]+K[Y].$$ Now suppose $X_1,\ldots,X_n$ are iid variables distributed like $X$ with zero expectation. Then $$K[X_1+\cdots+X_n] = nK[X] = \frac{1}{2}nV[X]t^2 + \frac{1}{6}nK_3(X)t^3 + \cdots,$$ where $K_m(X)$ are just the (normalized) coefficients of the cgf, i.e. the cumulants (they are normalized by $1/m!$). If we scale this sum down by $\sqrt{n}$, then the second cumulant becomes $V[X]$ (i.e. the variance is the same), but the rest of the cumulants $K_m$ for $m \geq 3$ get multiplied by $n^{1-m/2} \rightarrow 0$, so in the limit they disappear, and the cumulant of the limit is just $$K\left[\frac{X_1+\cdots+X_n}{\sqrt{n}}\right] = \frac{1}{2}V[X]t^2.$$ Therefore there is one 'domain of attraction' for distributions, which must be the normal distribution with zero mean and variance $V[X]$; it can be calculated directly from this representation. The same idea can be used to analyze the case where the variables are independent but not identically distributed. The main step missing to make this proof formal is reasoning about the limit distribution from the limit cgf; this is the Levy continuity lemma, which shows that the 'inverse Fourier transform' is continuous.

Had we taken the route of mgf's, we would have had to use the identity $(1+1/n)^n \rightarrow e^n$ somewhere, but otherwise the argument would be much the same.

$\endgroup$
2
$\begingroup$

Working out a few simple examples might help. This would indeed show you that the theorem works in special cases. Thus it would go a long way towards convincing oneself of the validity of the central limit theorem. The central limit theorem first appeared in the work of Abraham de Moivre, in which he proved that the normal distribution to approximate the distribution of the number of heads resulting from many tosses of a fair coin. Later Laplace showed that the same for the binomial distribution, approximating it with the normal distribution. I suggest that you work out these two simpler cases to get a feeling of how the approximation happens. All the necessary background for doing this yourself is available in the book of Hoel, Port and Stone.

If you find the theorem hard to understand, it might make you feel better to hear that probabilists needed a long time to properly formulate and understand the theorem. It was only done in the twentieth century by Lyapunov.

If you are oriented towards practical applications, then getting used to some topics of your choice, for instance noise analysis in communication theory, might help you in convincing yourself of the truth of the central limit theorem.

The best way to understand the central limit theorem would of course be to take a course in probability theory. An introductory course usually ends with a proof of this theorem. And if you take a course, you would see other interesting theorems such as the weak and strong laws of large numbers, and this would put the central limit theorem in better perspective. Even after all this, you might still need to contemplate a bit to really absorb the theorem. The proof I have seen is using some "characteristic functions" and a sort of "Fourier transform". I have to regretfully confess that I didn't fully understand it when I took the course. I never had to take up probability theory later; but if the occasion arises, I intend to go all properly through the proof and understand the machinery.

$\endgroup$
2
$\begingroup$

This answer gives an outline of how to use the Fourier Transform to prove that the $n$-fold convolution of any probability distribution with a finite variance contracted by a factor of $\sqrt{n}$ converges weakly to the normal distribution.

However, in his answer, Qiaochu Yuan mentions that one can use the Principle of Maximum Entropy to get a normal distribution. Below, I have endeavored to do just that using the Calculus of Variations.


Applying the Principle of Maximum Entropy

Suppose we want to maximize the entropy $$ -\int_{\mathbb{R}}\log(f(x))f(x)\,\mathrm{d}x\tag1 $$ over all $f$ whose mean is $0$ and variance is $\sigma^2$, that is $$ \int_{\mathbb{R}}\left(1,x,x^2\right)f(x)\,\mathrm{d}x=\left(1,0,\sigma^2\right)\tag2 $$ That is, we want the variation of $(1)$ to vanish $$ \int_{\mathbb{R}}(1+\log(f(x)))\,\delta f(x)\,\mathrm{d}x=0\tag3 $$ for all variations of $f$, $\delta f(x)$, so that the variation of $(2)$ vanishes $$ \int_{\mathbb{R}}\left(1,x,x^2\right)\delta f(x)\,\mathrm{d}x=(0,0,0)\tag4 $$ $(3)$, $(4)$, and orthogonality requires $$ \log(f(x))=c_0+c_1x+c_2x^2\tag5 $$ To satisfy $(2)$, we need $c_0=-\frac12\log\left(2\pi\sigma^2\right)$, $c_1=0$, and $c_2=-\frac1{2\sigma^2}$. That is, $$ \bbox[5px,border:2px solid #C0A000]{f(x)=\frac1{\sigma\sqrt{2\pi}}\,e^{-\frac{x^2}{2\sigma^2}}}\tag6 $$

$\endgroup$
2
  • $\begingroup$ This says that the maximum entropy for a probability distribution on $\mathbb{R}$ with variance $\sigma^2$ is $\frac12\log\left(2\pi e\sigma^2\right)$. $\endgroup$
    – robjohn
    Mar 26 '20 at 18:16
  • 1
    $\begingroup$ @EricAuld: I have added a bit more to help clarify that I am using the Calculus of Variations. $\endgroup$
    – robjohn
    Mar 27 '20 at 23:15
2
$\begingroup$

(Cross post from Stats Stack, where a similar question was asked.)

Why the $\sqrt{n}$ instead of $n$? What's this weird version of an average?

If you have a bunch of perpendicular vectors $x_1, \dotsc, x_n$ of length $\ell$, then $ \frac{x_1 + \dotsb + x_n}{\sqrt{n}}$ is again of length $\ell.$ You have to normalize by $\sqrt{n}$ to keep the sum at the same scale.

There is a deep connection between independent random variables and orthogonal vectors. When random variables are independent, that basically means that they are orthogonal vectors in a vector space of functions.

(The function space I refer to are the $L^2$ functions with mean zero, and the variance of a random variable $X$ is just $\|X - \mu\|_{L^2}^2$. So no wonder the variance is additive over independent random variables. Just like $\|x + y\|^2 = \|x\|^2 + \|y\|^2$ when $x \perp y$.)**

Why the normal distribution?

One thing that really confused me for a while, and which I think lies at the heart of the matter, is the following question:

Why is it that the sum $\frac{X_1 + \dotsb + X_n} {\sqrt{n}}$ ($n$ large) doesn’t care anything about the $X_i$ except their mean and their variance? (Moments 1 and 2.)

This is similar to the law of large numbers phenomenon:

$\frac{X_1 + \dotsb + X_n} {n}$ ($n$ large) only cares about moment 1 (the mean).

(Both of these have their hypotheses that I'm suppressing (see the footnote), but the most important thing, of course, is that the $X_i$ be independent.)

A more elucidating way to express this phenomenon is: in the sum $\frac{X_1 + \dotsb + X_n}{\sqrt{n}}$, I can replace any or all of the $X_i$ with some other RV’s, mixing and matching between all kinds of various distributions, as long as they have the same first and second moments. And it won’t matter as long as $n$ is large, relative to the moments.

If we understand why that’s true, then we understand the central limit theorem. Because then we may as well take $X_i$ to be normal with the same first and second moment, and in that case we know $\frac{X_1 + \dotsb + X_n}{\sqrt{n}}$ is just normal again for any $n$, including super-large $n$. Because the normal distribution has the special property ("stability") that you can add two independent normals together and get another normal. Voila.

The explanation of the first-and-second-moment phenomemonon is ultimately just some arithmetic. There are several lenses through which once can choose to view this arithmetic. The most common one people use is the fourier transform (AKA characteristic function), which has the feel of "I follow the steps, but how and why would anyone ever think of that?" Another approach is to look at the cumulants of $X_i$. There we find that the normal distribution is the unique distribution whose higher cumulants vanish, and dividing by $\sqrt{n}$ tends to kill all but the first two cumulants as $n$ gets large.

I'll show here a more elementary approach. As the sum $Z_n \overset{\text{(def)}}{=} \frac{X_1 + \dotsb + X_n}{\sqrt{n}}$ gets longer and longer, I'll show that all of the moments of $Z_n$ are functions only of the variances $\operatorname{Var}(X_i)$ and the means $\mathbb{E}X_i$, and nothing else. Now the moments of $Z_n$ determine the distribution of $Z_n$ (that's true not just for long independent sums, but for any nice distribution, by the Carleman continuity theorem). To restate, we're claiming that as $n$ gets large, $Z_n$ depends only on the $\mathbb{E}X_i$ and the $\operatorname{Var}X_i$. And to show that, we're going to show that $\mathbb{E}((Z_n - \mathbb{E}Z_n)^k)$ depends only on the $\mathbb{E}X_i$ and the $\operatorname{Var}X_i$. That suffices, by the Carleman continuity theorem.

For convenience, let's require that the $X_i$ have mean zero and variance $\sigma^2$. Assume all their moments exist and are uniformly bounded. (But nevertheless, the $X_i$ can be all different independent distributions.)

Claim: Under the stated assumptions, the $k$th moment $$\mathbb{E} \left[ \left(\frac{X_1 + \dotsb + X_n}{\sqrt{n}}\right)^k \right]$$ has a limit as $n \to \infty$, and that limit is a function only of $\sigma^2$. (It disregards all other information.)

(Specifically, the values of those limits of moments are just the moments of the normal distribution $\mathcal{N}(0, \sigma^2)$: zero for $k$ odd, and $|\sigma|^k \frac{k!}{(k/2)!2^{k/2}}$ when $k$ is even. This is equation (1) below.)

Proof: Consider $\mathbb{E} \left[ \left(\frac{X_1 + \dotsb + X_n}{\sqrt{n}}\right)^k \right]$. When you expand it, you get a factor of $n^{-k/2}$ times a big fat multinomial sum.

$$n^{-k/2} \sum_{|\boldsymbol{\alpha}| = k} \binom{k}{\alpha_1, \dotsc, \alpha_n}\prod_{i=1}^n \mathbb{E}(X_i^{\alpha_i})$$ $$\alpha_1 + \dotsb + \alpha_n = k$$ $$(\alpha_i \geq 0)$$

(Remember you can distribute the expectation over independent random variables. $\mathbb{E}(X^a Y^b) = \mathbb{E}(X^a)\mathbb{E}(Y^b)$.)

Now if ever I have as one of my factors a plain old $\mathbb{E}(X_i)$, with exponent $\alpha_i =1$, then that whole term is zero, because $\mathbb{E}(X_i) = 0$ by assumption. So I need all the exponents $\alpha_i \neq 1$ in order for that term to survive. That pushes me toward using fewer of the $X_i$ in each term, because each term has $\sum \alpha_i = k$, and I have to have each $\alpha_i >1$ if it is $>0$. In fact, some simple arithmetic shows that at most $k/2$ of the $\alpha_i$ can be nonzero, and that's only when $k$ is even, and when I use only twos and zeros as my $\alpha_i$.

This pattern where I use only twos and zeros turns out to be very important...in fact, any term where I don't do that will vanish as the sum grows larger.

Lemma: The sum $$n^{-k/2} \sum_{|\boldsymbol{\alpha}| = k}\binom{k}{\alpha_1, \dotsc, \alpha_n}\prod_{i=1}^n \mathbb{E}(X_i^{\alpha_i})$$ breaks up like $$n^{-k/2} \left( \underbrace{\left( \text{terms where some } \alpha_i = 1 \right)}_{\text{These are zero because $\mathbb{E}X_i = 0$}} + \underbrace{\left( \text{terms where }\alpha_i\text{'s are twos and zeros}\right)}_{\text{This part is } O(n^{k/2}) \text{ if $k$ is even, otherwise no such terms}} + \underbrace{\left( \text{rest of terms}\right)}_{o(n^{k/2})} \right)$$

In other words, in the limit, all terms become irrelevant except

$$ n^{-k/2}\sum\limits_{\binom{n}{k/2}} \underbrace{\binom{k}{2,\dotsc, 2}}_{k/2 \text{ twos}} \prod\limits_{j=1}^{k/2}\mathbb{E}(X_{i_j}^2) \tag{1}$$

Proof: The main points are to split up the sum by which (strong) composition of $k$ is represented by the multinomial $\boldsymbol{\alpha}$. There are only $2^{k-1}$ possibilities for strong compositions of $k$, so the number of those can't explode as $n \to \infty$. Then there is the choice of which of the $X_1, \dotsc, X_n$ will receive the positive exponents, and the number of such choices is $\binom{n}{\text{# positive terms in }\boldsymbol{\alpha}} = O(n^{\text{# positive terms in }\boldsymbol{\alpha}})$. (Remember the number of positive terms in $\boldsymbol{\alpha}$ can't be bigger than $k/2$ without killing the term.) That's basically it. You can find a more thorough description here on my website, or in section 2.2.3 of Tao's Topics in Random Matrix Theory, where I first read this argument.

And that concludes the whole proof. We’ve shown that all moments of $\frac{X_1 + … + X_n}{\sqrt{n}}$ forget everything but $\mathbb{E}X_i$ and $\mathbb{E}(X_i^2)$ as $n \to \infty$. And therefore swapping out the $X_i$ with any variables with the same first and second moments wouldn't have made any difference in the limit. And so we may as well have taken them to be $\sim \mathcal{N}(\mu, \sigma^2)$ to begin with; it wouldn't have made any difference.


**(If one wants to pursue more deeply the question of why $n^{1/2}$ is the magic number here for vectors and for functions, and why the variance (square $L^2$ norm) is the important statistic, one might read about why $L^2$ is the only $L^p$ space that can be an inner product space. Because $2$ is the only number that is its own Holder conjugate.)

Another valid view is that $n^{1/2}$ is not the only denominator can appear. There are different "basins of attraction" for random variables, and so there are infinitely many central limit theorems. There are random variables for which $\frac{X_1 + \dotsb + X_n}{n} \Rightarrow X$, and for which $\frac{X_1 + \dotsb + X_n}{1} \Rightarrow X$! But these random variables necessarily have infinite variance. These are called "stable laws".

It's also enlightening to look at the normal distribution from a calculus of variations standpoint: the normal distribution $\mathcal{N}(\mu, \sigma^2)$ maximizes the Shannon entropy among distributions with a given mean and variance, and which are absolutely continuous with respect to the Lebesgue measure on $\mathbb{R}$ (or $\mathbb{R}^d$, for the multivariate case). This is proven here, for example.

$\endgroup$
1
  • 1
    $\begingroup$ Please make substantive edits. There have been many small edits to this answer. This puts this question on the front page unnecessarily frequently. $\endgroup$
    – robjohn
    Mar 26 '20 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.