Let X1,X2,…X_1,X_2,\ldots be an iid sequence of random variables with mean μ\mu and n≥1.n\geq 1. The partial sum of the first nn terms is SnS_n and the sample average of the first nn terms is X‾n.\overline{X}_n.

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

If the variance σ2\sigma^2 is finite then by linearity of expectation and independence

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}}.

Let X1,X2,…X_1,X_2,\ldots be an iid sequence of random variables with mean μ.\mu. The weak law of large numbers states that the sample average converges in probability to the mean.

X‾n→pμ,that  is  lim⁡n→∞P(∣X‾n−μ∣>ε)=0  ∀ ε>0\overline{X}_n\xrightarrow{p}\mu,\qquad\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

The weak law of large numbers has the following properties:

  • 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;
  • it also holds for independent random variables with a common mean that are not identically distributed provided their variances are bounded;
  • it also holds for uncorrelated rather than independent random variables with bounded variances.

Let X1,X2,…X_1,X_2,\ldots be an iid sequence of random variables. The strong law of large numbers states that the sample 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. This is the justification for the frequentist interpretation of probability and for Monte Carlo estimation of probabilities and expectations by averaging simulated values.

Let X1,…,XnX_1,\ldots,X_n be random variables. 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}

Let X1,X2,…X_1,X_2,\ldots be an iid sequence of random variables with cdf FX.F_X. 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. The Glivenko–Cantelli theorem states that the convergence is uniform in x.x.

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

Let X1,X2,…X_1,X_2,\ldots be an iid sequence of random variables with mean μ\mu and finite variance σ2>0.\sigma^2>0. The central limit theorem states that the standardised sample 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 central limit theorem has the following properties:

  • it 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),\overline{X}_n\approx\mathrm{N}\left(\mu,\frac{\sigma^2}{n}\right), Sn≈N(nμ,nσ2)S_n\approx\mathrm{N}\left(n\mu,n\sigma^2\right) and 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 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 de Moivre–Laplace theorem is the central limit theorem for 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).

Let X1,X2,…X_1,X_2,\ldots be an iid sequence of random variables with mean μ,\mu, finite variance σ2>0\sigma^2>0 and finite third absolute central moment ρ=E[∣X1−μ∣3].\rho=\mathbb{E}\left[\lvert X_1-\mu\rvert^3\right]. The Berry–Esseen theorem states that there is an absolute constant C<1C<1 such that the error of the normal approximation is bounded by a multiple of 1n.\frac{1}{\sqrt{n}}.

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}

The error of the normal approximation therefore decreases like 1n\frac{1}{\sqrt{n}} and is larger for skewed or heavy-tailed distributions.

Let X1,X2,…X_1,X_2,\ldots be independent random variables that are not necessarily identically distributed. The Lindeberg condition is the 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, which makes precise the requirement that no single term dominates the sum. The central limit theorem holds for independent random variables that satisfy the Lindeberg condition.

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 the centred sample average converges in distribution to a multivariate normal distribution.

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, the multivariate central limit theorem 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 of X1,…,XnX_1,\ldots,X_n are the values X(1)≤X(2)≤…≤X(n)X_{(1)}\leq X_{(2)}\leq\ldots\leq X_{(n)} of X1,…,XnX_1,\ldots,X_n arranged in increasing order. The kk-th order statistic X(k)X_{(k)} is the kk-th smallest value. The smallest and largest order statistics are the minimum and maximum of X1,…,Xn.X_1,\ldots,X_n.

X(1)=min⁡iXi,X(n)=max⁡iXiX_{(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 the kk-th order statistic has cdf and pdf

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. Order statistics of iid continuous random variables have the following properties:

  • the maximum and minimum have FX(n)(x)=F(x)nF_{X_{(n)}}\left(x\right)=F\left(x\right)^n and FX(1)(x)=1−(1−F(x))n;F_{X_{(1)}}\left(x\right)=1-\left(1-F\left(x\right)\right)^n;
  • 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);
  • 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, so E[F(X(k))]=kn+1\mathbb{E}\left[F\left(X_{(k)}\right)\right]=\frac{k}{n+1} and the kk-th order statistic sits on average at the kn+1\frac{k}{n+1}-quantile.

Let X1,X2,…X_1,X_2,\ldots be iid continuous random variables with cdf FF and pdf f,f, u∈(0,1),u\in\left(0,1\right), xu=F−1(u)x_u=F^{-1}\left(u\right) be the uu-quantile at which ff is continuous and positive, and knk_n be a sequence with knn→u.\frac{k_n}{n}\rightarrow u. The central order statistic X(kn)X_{(k_n)} is the order statistic whose rank grows in proportion to n.n. The central order statistic 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)

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}.

Let X1,X2,…X_1,X_2,\ldots be iid random variables with cdf F.F. The extreme order statistics are the maximum X(n)X_{(n)} and the minimum X(1).X_{(1)}. The maximum converges in probability to the supremum of the support.

Let X1,X2,…X_1,X_2,\ldots be iid random variables with cdf F,F, and an>0a_n>0 and bnb_n be normalising sequences. The Fisher–Tippett–Gnedenko theorem states that if 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.