The central limit theorem and the law of large numbers are the two fundamental theorems of probability. Roughly, the central limit theorem states that the distribution of the sum (or average) of a large number of independent, identically distributed variables will be approximately normal, regardless of the underlying distribution. The importance of the central limit theorem is hard to overstate; indeed it is the reason that many statistical procedures work.

Partial Sum Processes

Definitions

Suppose that $\mathit{X}=(X_1,X_2,\dots )$ is a sequence of independent, identically distributed, real-valued random variables with common probability density function $f$, mean $\mu$, and variance ${\sigma }^2$. We assume that $0<\sigma <\mathrm{\infty }$, so that in particular, the random variables really are random and not constants. Let $$Y_n=\sum _{i=1}^n{X}_i,n\in \mathbb{N}$$ Note that by convention, $Y_0=0$, since the sum is over an empty index set. The random process $\mathit{Y}=(Y_0,Y_1,Y_2,\dots )$ is called the partial sum process associated with $\mathit{X}$. Special types of partial sum processes have been studied in many places in this text; in particular see

• the binomial distribution in the setting of Bernoulli Trials
• the negative binomial distribution in the setting of Bernoulli Trials
• the gamma distribution in the Poisson process
• the the arrival times in a general renewal process

Recall that in statistical terms, the sequence $\mathit{X}$ corresponds to sampling from the underlying distribution. In particular, $(X_1,X_2,\dots ,X_n)$ is a random sample of size $n$ from the distribution, and the corresponding sample mean is $$M_n=\frac{Y_n}{n}=\frac{1}{n}\sum _{i=1}^n{X}_i$$ By the law of large numbers, $M_n\to \mu$ as $n\to \mathrm{\infty }$ with probability 1.

Stationary, Independent Increments

The partial sum process corresponding to a sequence of independent, identically distributed variables has two important properties, and these properties essentially characterize such processes.

Note however that $Y_n-Y_m$ and $Y_{n-m}$ are very different random variables; the theorem simply states that they have the same distribution.

So partial sum processes are the only discrete-time random processes that have stationary, independent increments. An interesting, and much harder problem, is to characterize the continuous-time processes that have stationary independent increments. The Poisson counting process has stationary independent increments, as does the Brownian motion process.

Moments

Distributions

More generally, we can use the stationary and independence properties to find the joint distributions of the partial sum process:

The Central Limit Theorem

First, let's make the central limit theorem more precise. From Theorem 4 in [4], we cannot expect $Y_n$ itself to have a limiting distribution. Note that $\text{var}(Y_n)\to \mathrm{\infty }$ as $n\to \mathrm{\infty }$ since $\sigma >0$, and $\mathbb{E}(Y_n)\to \mathrm{\infty }$ as $n\to \mathrm{\infty }$ if $\mu >0$ while $\mathbb{E}(Y_n)\to -\mathrm{\infty }$ as $n\to \mathrm{\infty }$ if $\mu <0$. Similarly, we know that $M_n\to \mu$ as $n\to \mathrm{\infty }$ with probability 1, so the limiting distribution of the sample mean is degenerate. Thus, to obtain a limiting distribution of $Y_n$ or $M_n$ that is not degenerate, we need to consider, not these variables themeselves, but rather the common standard score. Thus, let $$Z_n=\frac{Y_n-n\mu }{\sqrt{n}\sigma }=\frac{M_n-\mu }{\sigma /\sqrt{n}}$$

The precise statement of the central limit theorem is that the distribution of the standard score $Z_n$ converges to the standard normal distribution as $n\to \mathrm{\infty }$. Recall that the standard normal distribution has probability density function $$\varphi (z)=\frac{1}{\sqrt{2\pi }}{e}^{-\frac{1}{2}{z}^2},z\in \mathbb{R}$$ A special case of the central limit theorem (to Bernoulli trials), dates to Abraham De Moivre. The term central limit theorem was coined by George Pólya in 1920. By definition of convergence in distribution, the central limit theorem states that $F_n(z)\to \mathrm{\Phi }(z)$ as $n\to \mathrm{\infty }$ for each $z\in \mathbb{R}$, where $F_n$ is the distribution function of $Z_n$ and $\mathrm{\Phi }$ is the standard normal distribution function: $$\mathrm{\Phi }(z)={\int }_{-\mathrm{\infty }}^z\varphi (x)dx={\int }_{-\mathrm{\infty }}^z\frac{1}{\sqrt{2\pi }}{e}^{-\frac{1}{2}{x}^2}dx,z\in \mathbb{R}$$ An equivalent statment of the central limit theorm involves convergence of the corresponding characteristic functions. This is the version that we will give and prove, but first we need a generalization of a famous limit from calculus.

Now let $\chi$ denote the characteristic function of the standard score of the sample variable $X$, and let ${\chi }_n$ denote the characteristic function of the standard score $Z_n$: $$\chi (t)=\mathbb{E}[\exp \left(it\frac{X-\mu }{\sigma }\right)],{\chi }_n(t)=\mathbb{E}[\exp (it{Z}_n)];t\in \mathbb{R}$$ Recall that $t\mapsto e^{-\frac{1}{2}{t}^2}$ is the characteristic function of the standard normal distribution. We can now give a proof.

Normal Approximations

The central limit theorem implies that if the sample size $n$ is large then the distribution of the partial sum $Y_n$ is approximately normal with mean $n\mu$ and variance $n{\sigma }^2$. Equivalently the sample mean $M_n$ is approximately normal with mean $\mu$ and variance ${\sigma }^2/n$. The central limit theorem is of fundamental importance, because it means that we can approximate the distribution of certain statistics, even if we know very little about the underlying sampling distribution.

Of course, the term large is relative. Roughly, the more abnormal the basic distribution, the larger $n$ must be for normal approximations to work well. The rule of thumb is that a sample size $n$ of at least 30 will usually suffice if the basic distribution is not too weird; although for many distributions smaller $n$ will do.

Random variable $Y$ in [12] has the Irwin-Hall distribution of order 30, named for Joseph Irwin and Phillip Hall.

The Continuity Correction

A slight technical problem arises when the sampling distribution is discrete. In this case, the partial sum also has a discrete distribution, and hence we are approximating a discrete distribution with a continuous one. Suppose that $X$ takes integer values (the most common case) and hence so does the partial sum $Y_n$. For any $k\in \mathbb{Z}$ and $h\in [0,1)$, note that the event $\{k-h\le Y_n\le k+h\}$ is equivalent to the event $\{Y=k\}$. Different values of $h$ lead to different normal approximations, even though the events are equivalent. The smallest approximation would be 0 when $h=0$, and the approximations increase as $h$ increases. It is customary to split the difference by using $h=\frac{1}{2}$ for the normal approximation. This is sometimes called the half-unit continuity correction or the histogram correction. The continuity correction is extended to other events in the natural way, using the additivity of probability.

Normal Approximation to the Gamma Distribution

Recall that the gamma distribution with shape parameter $k\in (0,\mathrm{\infty })$ and scale parameter $b\in (0,\mathrm{\infty })$ is a continuous distribution on $(0,\mathrm{\infty })$ with probability density function $f$ given by $$f(x)=\frac{1}{\mathrm{\Gamma }(k)b^k}{x}^{k-1}{e}^{-x/b},x\in (0,\mathrm{\infty })$$ The mean is $kb$ and the variance is $k{b}^2$. The gamma distribution is widely used to model random times and other positive random variables. In the context of the Poisson model (where $k\in {\mathbb{N}}_{+}$), the gamma distribution is also known as the Erlang distribution, named for Agner Erlang. Suppose now that $Y_k$ has the gamma (Erlang) distribution with shape parameter $k\in {\mathbb{N}}_{+}$ and scale parameter $b>0$ then $$Y_k=\sum _{i=1}^k{X}_i$$ where $(X_1,X_2,\dots )$ is a sequence of independent variables, each having the exponential distribution with scale parameter $b$. (The exponential distribution is a special case of the gamma distribution with shape parameter 1.) It follows that if $k$ is large, the gamma distribution can be approximated by the normal distribution with mean $kb$ and variance $k{b}^2$. The same statement actually holds when $k$ is not an integer. Here is the precise statement:

Normal Approximation to the Chi-Square Distribution

Recall that the chi-square distribution with $n\in (0,\mathrm{\infty })$ degrees of freedom is a special case of the gamma distribution, with shape parameter $k=n/2$ and scale parameter $b=2$. Thus, the chi-square distribution with $n$ degrees of freedom has probability density function $$f(x)=\frac{1}{\mathrm{\Gamma }(n/2)2^{n/2}}{x}^{n/2-1}{e}^{-x/2},0<x<\mathrm{\infty }$$ When $n$ is a positive, integer, the chi-square distribution governs the sum of $n$ independent, standard normal variables. For this reason, it is one of the most important distributions in statistics. From the previous discussion on gamma distributions, it follows that if $n$ is large, the chi-square distribution can be approximated by the normal distribution with mean $n$ and variance $2n$. Here is the precise statement:

Normal Approximation to the Binomial Distribution

Recall that a Bernoulli trials sequence, named for Jacob Bernoulli, is a sequence $(X_1,X_2,\dots )$ of independent, identically distributed indicator variables with $\mathbb{P}(X_i=1)=p$ for each $i$, where $p\in (0,1)$ is the parameter. In the usual language of reliability, $X_i$ is the outcome of trial $i$, where 1 means success and 0 means failure. The common mean is $p$ and the common variance is $p(1-p)$.

Let $Y_n=\sum _{i=1}^n{X}_i$, so that $Y_n$ is the number of successes in the first $n$ trials. Recall that $Y_n$ has the binomial distribution with parameters $n$ and $p$, and has probability density function $$f(k)=(\genfrac{}{}{0ex}{}{n}{k})p^k(1-p{)}^{n-k},k\in \{0,1,\dots ,n\}$$

It follows from the central limit theorem that if $n$ is large, the binomial distribution with parameters $n$ and $p$ can be approximated by the normal distribution with mean $np$ and variance $np(1-p)$. The rule of thumb is that $n$ should be large enough for $np\ge 5$ and $n(1-p)\ge 5$. (The first condition is the important one when $p<\frac{1}{2}$ and the second condition is the important one when $p>\frac{1}{2}$.) Here is the precise statement:

Normal Approximation to the Poisson Distribution

Recall that the Poisson distribution, named for Simeon Poisson, is a discrete distribution on $\mathbb{N}$ with probability density function $f$ given by $$f(x)=e^{-\theta }\frac{{\theta }^x}{x!},x\in \mathbb{N}$$ where $\theta >0$ is a parameter. The parameter is both the mean and the variance of the distribution. The Poisson distribution is widely used to model the number of random points in a region of time or space, particularly in the context of the Poisson process. In this context, the parameter is proportional to the size of the region.

Suppose now that $Y_n$ has the Poisson distribution with parameter $n\in {\mathbb{N}}_{+}$. Then $$Y_n=\sum _{i=1}^n{X}_i$$ where $(X_1,X_2,\dots ,X_n)$ is a sequence of independent variables, each with the Poisson distribution with parameter 1. It follows from the central limit theorem that if $n$ is large, the Poisson distribution with parameter $n$ can be approximated by the normal distribution with mean $n$ and variance $n$. The same statement holds when the parameter $n$ is not an integer. Here is the precise statement:

Normal Approximation to the Negative Binomial Distribution

The general version of the negative binomial distribution is a discrete distribution on $\mathbb{N}$, with shape parameter $k\in (0,\mathrm{\infty })$ and success parameter $p\in (0,1)$. The probability density function $f$ is given by $$f(n)=(\genfrac{}{}{0ex}{}{n+k-1}{n})p^k(1-p{)}^n,n\in {\mathbb{N}}_{+}$$ The mean is $k(1-p)/p$ and the variance is $k(1-p)/p^2$. If $k\in {\mathbb{N}}_{+}$, the distribution governs the number of failures $Y_k$ before success number $k$ in a sequence of Bernoulli trials with success parameter $p$. So in this case, $$Y_k=\sum _{i=1}^k{X}_i$$ where $(X_1,X_2,\dots ,X_k)$ is a sequence of independent variables, each having the geometric distribution on $\mathbb{N}$ with parameter $p$. (The geometric distribution is a special case of the negative binomial, with parameters 1 and $p$.) In the context of the Bernoulli trials, $X_1$ is the number of failures before the first success, and for $i\in \{2,3,\dots \}$, $X_i$ is the number of failures between success number $i-1$ success number $i$. It follows that if $k$ is large, the negative binomial distribution can be approximated by the normal distribution. The same statement holds if $k$ is not an integer. Here is the precise statement:

Another version of the negative binomial distribution is the distribution of the trial number $V_k$ of success number $k\in {\mathbb{N}}_{+}$. So $V_k=k+Y_k$ and $V_k$ has mean $k/p$ and variance $k(1-p)/p^2$. The normal approximation applies to the distribution of $V_k$ as well, if $k$ is large, and since the distributions are related by a location transformation, the standard scores are the same. That is $$\frac{p{V}_k-k}{\sqrt{k(1-p)}}=\frac{p{Y}_k-k(1-p)}{\sqrt{k(1-p)}}$$

Partial Sums with a Random Number of Terms

Our last topic is a bit more esoteric, but still fits with the general setting of this section. Recall that $\mathit{X}=(X_1,X_2,\dots )$ is a sequence of independent, identically distributed real-valued random variables with common mean $\mu$ and variance ${\sigma }^2$. Suppose now that $N$ is a random variable (on the same probability space) taking values in $\mathbb{N}$, also with finite mean and variance. Then $$Y_N=\sum _{i=1}^N{X}_i$$ is a random sum of the independent, identically distributed variables. That is, the terms are random of course, but so also is the number of terms $N$. We are primarily interested in the moments of $Y_N$.

Independent Number of Terms

Suppose first that $N$, the number of terms, is independent of $\mathit{X}$, the sequence of terms. Computing the moments of $Y_N$ is a good exercise in conditional expectation.

Wald's Equation

The result in part (b) of [33] generalizes to the case where the random number of terms $N$ is a stopping time for the sequence $\mathit{X}$. This means that the event $\{N=n\}$ depends only on (technically, is measurable with respect to) $(X_1,X_2,\dots ,X_n)$ for each $n\in \mathbb{N}$. The generalization is knowns as Wald's equation, and is named for Abraham Wald.

An elgant proof of Wald's equation is given in the chapter on Martingales.