Let X1,X2,…X_1,X_2,\ldots be an iid sequence of random variables with mean μ\mu and, where needed, finite variance σ2>0.\sigma^2>0. The partial sum and the average of the first nn terms are

Sn:=∑i=1nXi,X‾n:=1n∑i=1nXi,S_n:=\sum_{i=1}^n X_i,\qquad\overline{X}_n:=\frac{1}{n}\sum_{i=1}^n X_i,

which by linearity of expectation and independence have

E[X‾n]=μ,var[X‾n]=σ2n.\mathbb{E}\left[\overline{X}_n\right]=\mu,\qquad\mathrm{var}\left[\overline{X}_n\right]=\frac{\sigma^2}{n}.

The limit theorems describe how X‾n\overline{X}_n behaves as n→∞:n\rightarrow\infty: the laws of large numbers state that it converges to μ\mu and the central limit theorem describes the distribution of its fluctuations around μ\mu at the scale 1n.\frac{1}{\sqrt{n}}.

The weak law of large numbers states that the average converges in probability to the mean.

X‾n→pμ\overline{X}_n\xrightarrow{p}\mu that  is  lim⁡n→∞P(∣X‾n−μ∣>ε)=0  ∀ ε>0\mathrm{that}\,\,\mathrm{is}\,\,\lim_{n\rightarrow\infty}\mathbb{P}\left(\left\lvert\overline{X}_n-\mu\right\rvert>\varepsilon\right)=0\,\,\forall\,\varepsilon>0

Under the assumption of finite variance it follows from Chebyshev’s inequality, P(∣X‾n−μ∣>ε)≤σ2nε2,\mathbb{P}\left(\left\lvert\overline{X}_n-\mu\right\rvert>\varepsilon\right)\leq\frac{\sigma^2}{n\varepsilon^2}, but it holds whenever the mean exists. The law also holds for independent random variables with a common mean that are not identically distributed provided their variances are bounded, and for uncorrelated rather than independent random variables with bounded variances.

The strong law of large numbers states that the average converges almost surely to the mean, and that the existence of the mean is both necessary and sufficient.

X‾n→a.s.μ⇔E[∣X1∣]<∞\overline{X}_n\xrightarrow{a.s.}\mu\Leftrightarrow\mathbb{E}\left[\lvert X_1\rvert\right]<\infty

The strong law states that for almost every outcome the sequence of averages eventually stays within any fixed distance of μ,\mu, whereas the weak law only states that the probability of a deviation at a given nn is small. Applied to the indicator random variables 1{Xi∈A}\mathbf{1}_{\{X_i\in A\}} the strong law gives

1n∑i=1n1{Xi∈A}→a.s.P(X1∈A),\frac{1}{n}\sum_{i=1}^n\mathbf{1}_{\{X_i\in A\}}\xrightarrow{a.s.}\mathbb{P}\left(X_1\in A\right),

so the long-run relative frequency of an event converges to its probability, which is the justification for the frequentist interpretation of probability and for Monte Carlo estimation of probabilities and expectations by averaging simulated values.

The empirical distribution function of X1,…,XnX_1,\ldots,X_n is the cdf that places probability 1n\frac{1}{n} on each observed value.

F^n(x):=1n∑i=1n1{Xi≤x}  ∀ x∈R\hat{F}_n\left(x\right):=\frac{1}{n}\sum_{i=1}^n\mathbf{1}_{\{X_i\leq x\}}\,\,\forall\,x\in\mathbb{R}

By the strong law F^n(x)→a.s.FX(x)\hat{F}_n\left(x\right)\xrightarrow{a.s.}F_X\left(x\right) for each fixed x,x, and the Glivenko–Cantelli theorem strengthens this to uniform convergence.

sup⁡x∈R∣F^n(x)−FX(x)∣→a.s.0\sup_{x\in\mathbb{R}}\left\lvert\hat{F}_n\left(x\right)-F_X\left(x\right)\right\rvert\xrightarrow{a.s.}0

The central limit theorem states that if σ2\sigma^2 is finite then the standardised average converges in distribution to the standard normal distribution, whatever the distribution of the Xi.X_i.

n(X‾n−μ)σ=Sn−nμσn→dN(0,1)\frac{\sqrt{n}\left(\overline{X}_n-\mu\right)}{\sigma}=\frac{S_n-n\mu}{\sigma\sqrt{n}}\xrightarrow{d}\mathrm{N}\left(0,1\right)

Equivalently, n(X‾n−μ)→dN(0,σ2).\sqrt{n}\left(\overline{X}_n-\mu\right)\xrightarrow{d}\mathrm{N}\left(0,\sigma^2\right). The theorem is proved by showing that the characteristic function of the standardised average converges to e−t22e^{-\frac{t^2}{2}} and applying Lévy’s continuity theorem. For large nn it justifies the approximations

X‾n≈N(μ,σ2n),\qquadSn≈N(nμ,nσ2)\overline{X}_n\approx\mathrm{N}\left(\mu,\frac{\sigma^2}{n}\right),\qquadS_n\approx\mathrm{N}\left(n\mu,n\sigma^2\right) P(X‾n≤x)≈Φ(n(x−μ)σ).\mathbb{P}\left(\overline{X}_n\leq x\right)\approx\Phi\left(\frac{\sqrt{n}\left(x-\mu\right)}{\sigma}\right).

The case of Bernoulli random variables, in which Sn∼Binomial(n,p)S_n\sim\mathrm{Binomial}\left(n,p\right) is approximately N(np,np(1−p)),\mathrm{N}\left(np,np\left(1-p\right)\right), is the de Moivre–Laplace theorem. The finiteness of the variance is essential: the average of iid Cauchy random variables has the same Cauchy distribution for every nn and does not concentrate at all.

The Berry–Esseen theorem quantifies the rate of convergence in the central limit theorem. If ρ=E[∣X1−μ∣3]<∞\rho=\mathbb{E}\left[\lvert X_1-\mu\rvert^3\right]<\infty then there is an absolute constant C<1C<1 with

sup⁡x∈R∣P(n(X‾n−μ)σ≤x)−Φ(x)∣≤Cρσ3n  ∀ n∈N,\sup_{x\in\mathbb{R}}\left\lvert\mathbb{P}\left(\frac{\sqrt{n}\left(\overline{X}_n-\mu\right)}{\sigma}\leq x\right)-\Phi\left(x\right)\right\rvert\leq\frac{C\rho}{\sigma^3\sqrt{n}}\,\,\forall\,n\in\mathbb{N},

so the error of the normal approximation decreases like 1n\frac{1}{\sqrt{n}} and is larger for skewed or heavy-tailed distributions. The central limit theorem also holds for independent random variables that are not identically distributed when no single term dominates the sum, which is made precise by the Lindeberg condition that for every ε>0\varepsilon>0 the contribution to the total variance from terms exceeding ε\varepsilon standard deviations of the sum tends to zero.

Let X‾1,X‾2,…\underline{X}_1,\underline{X}_2,\ldots be iid random vectors in Rk\mathbb{R}^k with mean vector μ‾\underline{\mu} and covariance matrix Σ\Sigma with finite entries. The multivariate central limit theorem states that

n(X‾‾n−μ‾)→dNk(0‾,Σ).\sqrt{n}\left(\overline{\underline{X}}_n-\underline{\mu}\right)\xrightarrow{d}\mathrm{N}_k\left(\underline{0},\Sigma\right).

Combined with the multivariate delta method it gives the limiting normal distribution of any smooth function of averages, such as the average of the squares together with the average itself, from which the limiting distribution of a variance estimate follows.

Let X1,…,XnX_1,\ldots,X_n be random variables. The order statistics X(1)≤X(2)≤…≤X(n)X_{(1)}\leq X_{(2)}\leq\ldots\leq X_{(n)} are the values of X1,…,XnX_1,\ldots,X_n arranged in increasing order, so that X(k)X_{(k)} is the kk-th order statistic, the kk-th smallest value. The smallest and largest are the minimum and maximum of X1,…,Xn,X_1,\ldots,X_n,

X(1)=min⁡iXi,X(n)=max⁡iXi.X_{(1)}=\min_{i}X_i,\qquad X_{(n)}=\max_{i}X_i.

Let X1,…,XnX_1,\ldots,X_n be iid continuous random variables with cdf FF and pdf f,f, so that ties occur with probability zero and the inequalities between the order statistics are strict almost surely. The event X(k)≤xX_{(k)}\leq x occurs if and only if at least kk of the XiX_i are at most x,x, and the number of such XiX_i is Binomial(n,F(x)),\mathrm{Binomial}\left(n,F\left(x\right)\right), so

FX(k)(x)=∑j=kn(nj)F(x)j(1−F(x))n−jF_{X_{(k)}}\left(x\right)=\sum_{j=k}^n\binom{n}{j}F\left(x\right)^j\left(1-F\left(x\right)\right)^{n-j} fX(k)(x)=n!(k−1)!(n−k)!F(x)k−1(1−F(x))n−kf(x).f_{X_{(k)}}\left(x\right)=\frac{n!}{\left(k-1\right)!\left(n-k\right)!}F\left(x\right)^{k-1}\left(1-F\left(x\right)\right)^{n-k}f\left(x\right).

The density follows from requiring k−1k-1 values below x,x, one value at xx and n−kn-k values above x.x. In particular the maximum and minimum have

FX(n)(x)=F(x)n,FX(1)(x)=1−(1−F(x))n,F_{X_{(n)}}\left(x\right)=F\left(x\right)^n,\qquad F_{X_{(1)}}\left(x\right)=1-\left(1-F\left(x\right)\right)^n,

and the joint pdf of all nn order statistics is n!∏i=1nf(xi)n!\prod_{i=1}^n f\left(x_i\right) on the region x1<x2<…<xnx_1<x_2<\ldots<x_n and zero elsewhere. If U1,…,UnU_1,\ldots,U_n are iid U(0,1)\mathrm{U}\left(0,1\right) then U(k)∼Beta(k,n−k+1),U_{(k)}\sim\mathrm{Beta}\left(k,n-k+1\right), and since F(Xi)∼U(0,1)F\left(X_i\right)\sim\mathrm{U}\left(0,1\right) by the probability integral transform, F(X(k))∼Beta(k,n−k+1)F\left(X_{(k)}\right)\sim\mathrm{Beta}\left(k,n-k+1\right) in general. Hence E[F(X(k))]=kn+1,\mathbb{E}\left[F\left(X_{(k)}\right)\right]=\frac{k}{n+1}, so the kk-th order statistic sits on average at the kn+1\frac{k}{n+1}-quantile.

The order statistics have their own limit theorems. Let u∈(0,1)u\in\left(0,1\right) and knk_n be a sequence with knn→u,\frac{k_n}{n}\rightarrow u, and suppose ff is continuous and positive at the uu-quantile xu=F−1(u).x_u=F^{-1}\left(u\right). The central order statistic X(kn)X_{(k_n)} converges in distribution to a normal distribution after centring at the quantile,

n(X(kn)−xu)→dN(0,u(1−u)f(xu)2),\sqrt{n}\left(X_{(k_n)}-x_u\right)\xrightarrow{d}\mathrm{N}\left(0,\frac{u\left(1-u\right)}{f\left(x_u\right)^2}\right),

so for u=12u=\frac{1}{2} the middle order statistic converges to the median mm with limiting variance 14f(m)2.\frac{1}{4f\left(m\right)^2}. The extreme order statistics behave differently: the maximum X(n)X_{(n)} converges in probability to the supremum of the support, and the Fisher–Tippett–Gnedenko theorem states that if some normalisation X(n)−bnan\frac{X_{(n)}-b_n}{a_n} has a non-degenerate limit in distribution then the limit is one of three extreme value distributions, the Gumbel, Fréchet or Weibull distribution, determined by the tail of F.F. For example, if Xi∼Exponential(1)X_i\sim\mathrm{Exponential}\left(1\right) then X(n)−log⁡enX_{(n)}-\log_e n converges in distribution to the Gumbel distribution with cdf exp⁡(−e−x),\exp\left(-e^{-x}\right), and n X(1)∼Exponential(1)n\,X_{(1)}\sim\mathrm{Exponential}\left(1\right) exactly for every n.n.