Let X1,X2,… be an iid sequence of random variables with mean μ and n≥1. The partial sum of the first n terms is Sn and the sample average of the first n terms is Xn.
Sn:=i=1∑nXi,Xn:=n1i=1∑nXi
If the variance σ2 is finite then by linearity of expectation and independence
E[Xn]=μ,var[Xn]=nσ2.
The limit theorems describe how Xn behaves as n→∞. The laws of large numbers state that it converges to μ, and the central limit theorem describes the distribution of its fluctuations around μ at the scale n1.
Let X1,X2,… be an iid sequence of random variables with mean μ. The weak law of large numbers states that the sample average converges in probability to the mean.
Xnpμ,thatisn→∞limP(Xn−μ>ε)=0∀ε>0
The weak law of large numbers has the following properties:
under the assumption of finite variance it follows from Chebyshev’s inequality, P(Xn−μ>ε)≤nε2σ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,… 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.
Xna.s.μ⇔E[∣X1∣]<∞
The strong law states that for almost every outcome the sequence of averages eventually stays within any fixed distance of μ, whereas the weak law only states that the probability of a deviation at a given n is small. Applied to the indicator random variables 1{Xi∈A} the strong law gives
n1i=1∑n1{Xi∈A}a.s.P(X1∈A),
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,…,Xn be random variables. The empirical distribution function of X1,…,Xn is the cdf that places probability n1 on each observed value.
F^n(x):=n1i=1∑n1{Xi≤x}∀x∈R
Let X1,X2,… be an iid sequence of random variables with cdf FX. By the strong law F^n(x)a.s.FX(x) for each fixed x. The Glivenko–Cantelli theorem states that the convergence is uniform in x.
x∈RsupF^n(x)−FX(x)a.s.0
Let X1,X2,… be an iid sequence of random variables with mean μ and finite variance σ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.
σn(Xn−μ)=σnSn−nμdN(0,1)
Equivalently, n(Xn−μ)dN(0,σ2). The central limit theorem has the following properties:
it is proved by showing that the characteristic function of the standardised average converges to e−2t2 and applying Lévy’s continuity theorem;
for large n it justifies the approximations Xn≈N(μ,nσ2),Sn≈N(nμ,nσ2) and P(Xn≤x)≈Φ(σn(x−μ));
the finiteness of the variance is essential: the average of iid Cauchy random variables has the same Cauchy distribution for every n 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) is approximately N(np,np(1−p)).
Let X1,X2,… be an iid sequence of random variables with mean μ, finite variance σ2>0 and finite third absolute central moment ρ=E[∣X1−μ∣3]. The Berry–Esseen theorem states that there is an absolute constant C<1 such that the error of the normal approximation is bounded by a multiple of n1.
x∈RsupP(σn(Xn−μ)≤x)−Φ(x)≤σ3nCρ∀n∈N
The error of the normal approximation therefore decreases like n1 and is larger for skewed or heavy-tailed distributions.
Let X1,X2,… be independent random variables that are not necessarily identically distributed. The Lindeberg condition is the condition that for every ε>0 the contribution to the total variance from terms exceeding ε 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 X1,X2,… be iid random vectors in Rk with mean vector μ and covariance matrix Σ with finite entries. The multivariate central limit theorem states that the centred sample average converges in distribution to a multivariate normal distribution.
n(Xn−μ)dNk(0,Σ)
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,…,Xn be random variables. The order statistics of X1,…,Xn are the values X(1)≤X(2)≤…≤X(n) of X1,…,Xn arranged in increasing order. The k-th order statisticX(k) is the k-th smallest value. The smallest and largest order statistics are the minimum and maximum of X1,…,Xn.
X(1)=iminXi,X(n)=imaxXi
Let X1,…,Xn be iid continuous random variables with cdf F and pdf f, so that ties occur with probability zero and the inequalities between the order statistics are strict almost surely. The event X(k)≤x occurs if and only if at least k of the Xi are at most x, and the number of such Xi is Binomial(n,F(x)), so the k-th order statistic has cdf and pdf
The density follows from requiring k−1 values below x, one value at x and n−k values above x. Order statistics of iid continuous random variables have the following properties:
the maximum and minimum have FX(n)(x)=F(x)n and FX(1)(x)=1−(1−F(x))n;
the joint pdf of all n order statistics is n!∏i=1nf(xi) on the region x1<x2<…<xn and zero elsewhere;
if U1,…,Un are iid U(0,1) then U(k)∼Beta(k,n−k+1);
since F(Xi)∼U(0,1) by the probability integral transform, F(X(k))∼Beta(k,n−k+1) in general, so E[F(X(k))]=n+1k and the k-th order statistic sits on average at the n+1k-quantile.
Let X1,X2,… be iid continuous random variables with cdf F and pdf f,u∈(0,1),xu=F−1(u) be the u-quantile at which f is continuous and positive, and kn be a sequence with nkn→u. The central order statisticX(kn) is the order statistic whose rank grows in proportion to n. The central order statistic converges in distribution to a normal distribution after centring at the quantile.
n(X(kn)−xu)dN(0,f(xu)2u(1−u))
For u=21 the middle order statistic converges to the median m with limiting variance 4f(m)21.
Let X1,X2,… be iid random variables with cdf F. The extreme order statistics are the maximum X(n) and the minimum X(1). The maximum converges in probability to the supremum of the support.
Let X1,X2,… be iid random variables with cdf F, and an>0 and bn be normalising sequences. The Fisher–Tippett–Gnedenko theorem states that if anX(n)−bn 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. For example, if Xi∼Exponential(1) then X(n)−logen converges in distribution to the Gumbel distribution with cdf exp(−e−x), and nX(1)∼Exponential(1) exactly for every n.