The weak law of large numbers

Statement

Let \( (X_n)_{n \in \mathbb{N}} \) be a sequence of random variables on a probability space \( (\Omega, \mathcal{F}, \mathbb{P}) \) that are pairwise uncorrelated, share a common expectation \( \mathbb{E}[X_n] = \mu \in \mathbb{R} \), and have a common finite variance \( \operatorname{Var}(X_n) = \sigma^2 \lt \infty \). Write \( \overline{X}_n = \frac{1}{n}\sum_{i=1}^{n} X_i \) for the sample mean. Then \( \overline{X}_n \to \mu \) in probability: for every \( \varepsilon \gt 0 \), \( \lim_{n \to \infty} \mathbb{P}\!\left( \left| \overline{X}_n - \mu \right| \geq \varepsilon \right) = 0 \). In particular the conclusion holds for any i.i.d. sequence with finite variance; Khinchin's theorem (stated in the Discussion) extends it to i.i.d. sequences assuming only \( \mathbb{E}|X_1| \lt \infty \).

Why it matters

The weak law is the first rigorous bridge between probability theory and the empirical world: it says that the arithmetic average of many repeated, unrelated measurements stabilises near the theoretical expectation, with quantifiable error. Every consistent estimator in statistics, every Monte Carlo computation, and the frequentist reading of the number \( \mathbb{P}(A) \) as a long-run relative frequency rests, at bottom, on this theorem.

Pedagogically it is also the canonical first use of Chebyshev's inequality, and the first place a student meets a mode of stochastic convergence. Understanding exactly what "in probability" does and does not assert — and how it differs from almost-sure convergence — is a rite of passage for the whole of Probability I and II.

Hypotheses

Proof

We prove the pairwise-uncorrelated, finite-variance version. The strategy is pure \( L^2 \): compute the variance of \( \overline{X}_n \), watch it die like \( 1/n \), and convert second-moment decay into probability decay via Chebyshev. To keep the proof self-contained we first prove Markov's and Chebyshev's inequalities.

Result

Corollaries & converses

• Bernoulli's law (1713). For i.i.d. indicator variables \( X_i = \mathbf{1}_{A_i} \) of independent trials with success probability \( p \), the relative frequency satisfies \( \overline{X}_n \xrightarrow{\mathbb{P}} p \). This is the mathematical content of the frequency interpretation of probability.
• Consistency of estimators. The sample mean is a (weakly) consistent estimator of the population mean; more generally, sample moments \( \frac{1}{n}\sum_i X_i^k \) are consistent for \( \mathbb{E}[X^k] \) whenever \( X^k \) satisfies the hypotheses, which underwrites the method of moments.
• Weierstrass approximation. Bernstein's probabilistic proof that polynomials are uniformly dense in \( C[0,1] \) is exactly the WLLN argument run uniformly in the parameter (Problem 4).
• Relation to the Strong Law. Almost-sure convergence implies convergence in probability, so SLLN \( \Rightarrow \) WLLN. The converse fails: an i.i.d. sequence with \( \mathbb{P}(|X_1| \gt x) \sim \frac{1}{x \log x} \) has \( \mathbb{E}|X_1| = \infty \), yet satisfies the Kolmogorov–Feller condition \( n\,\mathbb{P}(|X_1| \gt n) \to 0 \), so the WLLN holds (with suitable centring) while \( \limsup_n |\overline{X}_n| = \infty \) almost surely, killing the SLLN.
• Converse direction. \( \overline{X}_n \xrightarrow{\mathbb{P}} c \) does not imply \( \mathbb{E}|X_1| \lt \infty \) (same example as above); the exact i.i.d. characterisation is Kolmogorov–Feller: a WLLN with centring constants \( a_n = \mathbb{E}\big[ X_1 \mathbf{1}_{\{|X_1| \leq n\}} \big] \) holds if and only if \( n\,\mathbb{P}(|X_1| \gt n) \to 0 \).

Fails without

Common errors

• Mode confusion. Concluding "\( \overline{X}_n(\omega) \to \mu \) for almost every \( \omega \)" from the weak law. Convergence in probability permits each fixed sample path to keep making excursions, provided they become rare in probability at each fixed \( n \); the pathwise statement is the Strong Law and requires more work (and, in the non-i.i.d. setting, more hypotheses).
• Sum vs. average. Reading the theorem as "\( S_n \approx n\mu \) with bounded error". The WLLN controls \( S_n/n - \mu \), not \( S_n - n\mu \): the latter typically has fluctuations of order \( \sigma\sqrt{n} \to \infty \) (that is the CLT's regime). "The average settles" and "the sum stays near \( n\mu \)" are very different claims.
• The gambler's fallacy. Inferring that after a run of heads, tails is "due" so the frequency can rebalance. The law needs no compensation mechanism: past excess is not cancelled, merely swamped — a surplus of \( k \) heads changes \( \overline{X}_n \) by \( k/n \to 0 \).
• Quantifier inversion. Writing the conclusion as \( \mathbb{P}\big( \forall \varepsilon \gt 0: |\overline{X}_n - \mu| \lt \varepsilon \big) \to 1 \) or letting \( \varepsilon \) shrink with \( n \). The correct statement fixes \( \varepsilon \gt 0 \) first; for \( \varepsilon_n \downarrow 0 \) fast (e.g. \( \varepsilon_n = n^{-1} \)) the corresponding probabilities need not vanish.
• Applying it to Cauchy-type data. Averaging i.i.d. Cauchy observations to "reduce noise". No hypothesis of any LLN holds, and the average is exactly as noisy as one observation.
• Treating Chebyshev's bound as the truth. The bound \( \sigma^2/(n\varepsilon^2) \) is honest but very loose for bounded variables: Hoeffding's inequality gives \( 2e^{-2n\varepsilon^2} \) for variables in \( [0,1] \). Chebyshev proves the law; it does not give sharp sample sizes.

Discussion

Historically this is where probability theory became a mathematical subject. Jacob Bernoulli proved the Bernoulli-trials case in Ars Conjectandi (published posthumously, 1713) by delicate binomial estimates, calling it his "golden theorem"; he needed some twenty years and regarded it as the justification for learning probabilities from frequencies. Chebyshev (1867) found the inequality now bearing his name and with it the modern three-line proof, simultaneously generalising the law far beyond coin tossing. Markov, his student, pushed it to dependent sequences via the \( L^2 \) condition \( n^{-2}\sum_i \operatorname{Var}(X_i) \to 0 \), and Khinchin (1929) removed the variance assumption for i.i.d. sequences altogether, assuming only \( \mathbb{E}|X_1| \lt \infty \), by the truncation technique that has been a standard tool ever since.

The theorem sits at the bottom of a tower of refinements. The Central Limit Theorem sharpens "\( \overline{X}_n - \mu \) is small" to "\( \overline{X}_n - \mu \) is approximately \( \mathcal{N}(0, \sigma^2/n) \)", identifying the exact scale \( \sigma/\sqrt{n} \) of the fluctuations the WLLN says vanish. Large deviations theory (Cramér, 1938) measures how fast the probability in the weak law decays: for i.i.d. variables with exponential moments, \( \mathbb{P}(|\overline{X}_n - \mu| \geq \varepsilon) = e^{-n I(\varepsilon) + o(n)} \) for an explicit rate function \( I \), exponentially faster than Chebyshev's \( 1/n \). And the Strong Law (Kolmogorov, 1933) upgrades the mode of convergence to almost-sure under the bare hypothesis \( \mathbb{E}|X_1| \lt \infty \).

Conceptually, the proof above teaches a lesson that recurs throughout analysis and statistics: to control a probability, control a moment. The entire theorem is the observation that variance — a purely \( L^2 \), geometric quantity — is additive over uncorrelated summands (Pythagoras in \( L^2 \), since uncorrelated centred variables are orthogonal), while the averaging factor \( 1/n \) enters squared. The tension between the \( n \) from additivity and the \( n^2 \) from scaling is the whole engine, and it is why mere pairwise orthogonality suffices where students expect full independence to be needed.

At full rigour the i.i.d. story is closed by the Kolmogorov–Feller weak law: for i.i.d. \( (X_n) \) there exist constants \( a_n \) with \( \overline{X}_n - a_n \to 0 \) in probability if and only if \( n\,\mathbb{P}(|X_1| \gt n) \to 0 \), in which case one may take \( a_n = \mathbb{E}\big[ X_1 \mathbf{1}_{\{|X_1| \leq n\}} \big] \). This condition is strictly weaker than integrability — the tail \( \mathbb{P}(|X_1| \gt x) = \frac{c}{x \log x} \) (for \( x \geq e \), symmetric) satisfies it while \( \mathbb{E}|X_1| = \int_0^\infty \mathbb{P}(|X_1| \gt x)\,dx = \infty \) — so the weak law genuinely outruns the strong law, which by the Kolmogorov three-series/Borel–Cantelli argument requires \( \mathbb{E}|X_1| \lt \infty \) for i.i.d. sequences (indeed \( \mathbb{E}|X_1| = \infty \) forces \( \limsup_n |X_n|/n \geq 1 \) a.s., hence \( \limsup_n |\overline{X}_n| = \infty \) a.s.). The proof of Kolmogorov–Feller is a paradigm truncation argument: cut at level \( n \), Chebyshev the truncated part, and union-bound the event that any summand exceeds the cut.

Common misconceptions. The weak law does not say large deviations become impossible — for every \( n \) there is positive probability of a bad average; it says that probability tends to \( 0 \). It says nothing about the un-normalised sum \( S_n \), whose deviations from \( n\mu \) typically grow. It promises no compensation of past imbalances. And it is silent about any single finite \( n \) unless you use the quantitative bound of Step 7 rather than the limit statement.

Worked examples

Example 1 (polling / coin tossing: a guaranteed sample size). A referendum has unknown support fraction \( p \in [0,1] \). We sample voters independently and uniformly; voter \( i \) yields \( X_i \sim \mathrm{Bernoulli}(p) \), i.i.d. How large must \( n \) be so that the poll estimate \( \widehat{p}_n = \overline{X}_n \) satisfies \( \mathbb{P}\left( |\widehat{p}_n - p| \geq 0.01 \right) \leq 0.05 \), whatever \( p \) is?

Example 2 (Monte Carlo integration is consistent, with an explicit error bound). Let \( g: [0,1] \to [0,1] \) be Borel measurable and \( I = \int_0^1 g(x)\,dx \), an integral we cannot do in closed form. Estimate \( I \) by \( \widehat{I}_n = \frac{1}{n}\sum_{i=1}^n g(U_i) \) where \( U_1, U_2, \ldots \) are i.i.d. \( \mathrm{Uniform}(0,1) \).

Problems

1. Let \( X_1, X_2, \ldots \) be i.i.d. \( \mathrm{Exponential}(\lambda) \), \( \lambda \gt 0 \). Show \( \overline{X}_n \xrightarrow{\mathbb{P}} \frac{1}{\lambda} \), and find an explicit \( n_0 \) (in terms of \( \lambda, \varepsilon, \delta \)) such that \( \mathbb{P}\left( |\overline{X}_n - \frac{1}{\lambda}| \geq \varepsilon \right) \leq \delta \) for all \( n \geq n_0 \).
   Solution

   For \( X \sim \mathrm{Exponential}(\lambda) \) we compute \( \mathbb{E}[X] = \int_0^\infty x \lambda e^{-\lambda x}\,dx = \frac{1}{\lambda} \) and \( \mathbb{E}[X^2] = \int_0^\infty x^2 \lambda e^{-\lambda x}\,dx = \frac{2}{\lambda^2} \) (integrate by parts twice, or use \( \Gamma(3) = 2 \)), so \( \operatorname{Var}(X) = \frac{2}{\lambda^2} - \frac{1}{\lambda^2} = \frac{1}{\lambda^2} \lt \infty \). The sequence is i.i.d., hence pairwise uncorrelated with common mean \( \frac{1}{\lambda} \) and common finite variance, so all hypotheses of the WLLN hold and \( \overline{X}_n \xrightarrow{\mathbb{P}} \frac{1}{\lambda} \). Quantitatively, Step 7 of the proof gives \[ \mathbb{P}\!\left( \left| \overline{X}_n - \tfrac{1}{\lambda} \right| \geq \varepsilon \right) \leq \frac{1}{n \lambda^2 \varepsilon^2}, \] which is at most \( \delta \) as soon as \( n \geq n_0 = \left\lceil \frac{1}{\lambda^2 \varepsilon^2 \delta} \right\rceil \). For instance \( \lambda = 1, \varepsilon = 0.1, \delta = 0.01 \) gives \( n_0 = 10^4 \).
2. (Markov's version.) Let \( X_1, X_2, \ldots \) be pairwise uncorrelated with means \( \mu_i = \mathbb{E}[X_i] \) (not necessarily equal) and variances satisfying \( \operatorname{Var}(X_i) \leq C \) for a single constant \( C \). Prove \[ \frac{1}{n}\sum_{i=1}^{n} \left( X_i - \mu_i \right) \xrightarrow{\ \mathbb{P}\ } 0, \] and show more generally that the conclusion holds whenever \( \frac{1}{n^2} \sum_{i=1}^{n} \operatorname{Var}(X_i) \to 0 \).
   Solution

   Set \( Y_i = X_i - \mu_i \) and \( T_n = \frac{1}{n}\sum_{i=1}^n Y_i \). The \( Y_i \) are centred, and they remain pairwise uncorrelated because covariance is unaffected by subtracting constants: \( \operatorname{Cov}(Y_i, Y_j) = \operatorname{Cov}(X_i, X_j) = 0 \) for \( i \neq j \). By linearity \( \mathbb{E}[T_n] = 0 \), and by Bienaymé (exactly as in Step 5 of the main proof, which used only pairwise uncorrelatedness) \[ \operatorname{Var}(T_n) = \frac{1}{n^2}\sum_{i=1}^{n} \operatorname{Var}(Y_i) = \frac{1}{n^2}\sum_{i=1}^{n} \operatorname{Var}(X_i). \] Under the bounded-variance hypothesis this is \( \leq \frac{nC}{n^2} = \frac{C}{n} \to 0 \); under the general hypothesis it tends to \( 0 \) by assumption. In either case Chebyshev gives, for fixed \( \varepsilon \gt 0 \), \[ \mathbb{P}\left( |T_n| \geq \varepsilon \right) \leq \frac{\operatorname{Var}(T_n)}{\varepsilon^2} \to 0, \] which is the claimed convergence in probability. Note that no identical-distribution assumption was used anywhere: the WLLN is fundamentally an \( L^2 \) phenomenon about variances, not about laws.
3. Let \( X_1, X_2, \ldots \) be i.i.d. with mean \( \mu \) and variance \( \sigma^2 \lt \infty \). Define the linearly weighted average \[ T_n = \frac{2}{n(n+1)} \sum_{i=1}^{n} i\, X_i . \] Prove \( T_n \xrightarrow{\mathbb{P}} \mu \).
   Solution

   The weights \( a_{n,i} = \frac{2i}{n(n+1)} \) satisfy \( \sum_{i=1}^n a_{n,i} = \frac{2}{n(n+1)} \cdot \frac{n(n+1)}{2} = 1 \), so \( \mathbb{E}[T_n] = \mu \sum_i a_{n,i} = \mu \) by linearity. By independence (hence pairwise uncorrelatedness) and Bienaymé, \[ \operatorname{Var}(T_n) = \sigma^2 \sum_{i=1}^{n} a_{n,i}^2 = \sigma^2 \cdot \frac{4}{n^2(n+1)^2} \sum_{i=1}^{n} i^2 = \sigma^2 \cdot \frac{4}{n^2(n+1)^2} \cdot \frac{n(n+1)(2n+1)}{6} = \frac{2\sigma^2 (2n+1)}{3\,n(n+1)}. \] Since \( \frac{2n+1}{n(n+1)} \leq \frac{3n}{n \cdot n} = \frac{3}{n} \) for \( n \geq 1 \), we get \( \operatorname{Var}(T_n) \leq \frac{2\sigma^2}{n} \to 0 \). Chebyshev's inequality applied to \( T_n \) (mean \( \mu \)) then yields, for each fixed \( \varepsilon \gt 0 \), \[ \mathbb{P}\left( |T_n - \mu| \geq \varepsilon \right) \leq \frac{2\sigma^2}{n\varepsilon^2} \to 0, \] so \( T_n \xrightarrow{\mathbb{P}} \mu \). Moral: any weight scheme with \( \sum_i a_{n,i} = 1 \) and \( \sum_i a_{n,i}^2 \to 0 \) obeys a weak law; the uniform weights \( a_{n,i} = \frac{1}{n} \) minimise \( \sum_i a_{n,i}^2 \), making the plain sample mean the variance-optimal choice.
4. (Bernstein's proof of the Weierstrass approximation theorem.) Let \( f \in C[0,1] \) and define its Bernstein polynomial \[ B_n f(x) = \sum_{k=0}^{n} f\!\left( \frac{k}{n} \right) \binom{n}{k} x^k (1-x)^{n-k} . \] Prove \( \sup_{x \in [0,1]} |B_n f(x) - f(x)| \to 0 \) as \( n \to \infty \), using the weak-law mechanism (Chebyshev at the uniform scale).
   Solution

   Fix \( x \in [0,1] \) and let \( S_n \sim \mathrm{Binomial}(n, x) \), i.e. \( S_n = \sum_{i=1}^n \xi_i \) with \( \xi_i \) i.i.d. \( \mathrm{Bernoulli}(x) \). Since \( \mathbb{P}(S_n = k) = \binom{n}{k} x^k (1-x)^{n-k} \), we have the probabilistic representation \( B_n f(x) = \mathbb{E}\left[ f\!\left( \frac{S_n}{n} \right) \right] \). Because \( f(x) \) is a constant, Jensen/triangle inequality for expectations gives \[ |B_n f(x) - f(x)| \leq \mathbb{E}\left[ \left| f\!\left( \tfrac{S_n}{n} \right) - f(x) \right| \right]. \] Let \( \varepsilon \gt 0 \). As \( f \) is continuous on the compact \( [0,1] \) it is bounded, \( M = \sup |f| \lt \infty \), and uniformly continuous: there is \( \delta \gt 0 \) with \( |f(s) - f(t)| \lt \varepsilon \) whenever \( |s - t| \lt \delta \). Split the expectation over the event \( A = \left\{ \left| \frac{S_n}{n} - x \right| \lt \delta \right\} \) and its complement: \[ \mathbb{E}\left[ \left| f\!\left( \tfrac{S_n}{n} \right) - f(x) \right| \right] \leq \varepsilon \, \mathbb{P}(A) + 2M \, \mathbb{P}(A^c) \leq \varepsilon + 2M\, \mathbb{P}\!\left( \left| \tfrac{S_n}{n} - x \right| \geq \delta \right). \] Now \( \frac{S_n}{n} \) is the sample mean of i.i.d. Bernoulli variables with mean \( x \) and variance \( x(1-x) \leq \frac{1}{4} \), so the quantitative WLLN bound (Chebyshev) gives \( \mathbb{P}\left( \left| \frac{S_n}{n} - x \right| \geq \delta \right) \leq \frac{x(1-x)}{n\delta^2} \leq \frac{1}{4n\delta^2} \), uniformly in \( x \). Hence \[ \sup_{x \in [0,1]} |B_n f(x) - f(x)| \leq \varepsilon + \frac{M}{2n\delta^2} . \] Letting \( n \to \infty \), the right side tends to \( \varepsilon \); since \( \varepsilon \gt 0 \) was arbitrary, \( \sup_x |B_n f - f| \to 0 \). Thus every continuous function on \( [0,1] \) is a uniform limit of polynomials — Weierstrass's theorem, proved by coin tossing. The crucial point is that Chebyshev's bound was uniform in the parameter \( x \), which is exactly what the worst-case variance bound \( x(1-x) \leq \frac{1}{4} \) delivers.
5. Let \( X_1, X_2, \ldots \) be i.i.d. standard Cauchy, with characteristic function \( \varphi_{X_1}(t) = \mathbb{E}\left[ e^{itX_1} \right] = e^{-|t|} \) (you may take this formula as given). Prove that \( \overline{X}_n \) is standard Cauchy for every \( n \), and deduce that there is no constant \( c \) with \( \overline{X}_n \xrightarrow{\mathbb{P}} c \). Which hypothesis of the weak law fails?
   Solution

   Step 1: the law of \( \overline{X}_n \). For independent variables the characteristic function of a sum is the product of characteristic functions, and \( \varphi_{aX}(t) = \varphi_X(at) \). Hence \[ \varphi_{\overline{X}_n}(t) = \prod_{i=1}^{n} \varphi_{X_i}\!\left( \frac{t}{n} \right) = \left( e^{-|t|/n} \right)^{n} = e^{-|t|} = \varphi_{X_1}(t). \] By the uniqueness theorem for characteristic functions (two laws with equal characteristic functions coincide), \( \overline{X}_n \) is standard Cauchy for every \( n \). Step 2: no convergence in probability to any constant. Suppose \( \overline{X}_n \xrightarrow{\mathbb{P}} c \) for some \( c \in \mathbb{R} \). Convergence in probability implies convergence in distribution, so the laws of \( \overline{X}_n \) would converge weakly to the point mass \( \delta_c \). But the law of \( \overline{X}_n \) is the fixed standard Cauchy law for all \( n \), whose weak limit is itself — and the Cauchy law is not a point mass (its distribution function \( F(x) = \frac{1}{2} + \frac{1}{\pi}\arctan x \) is continuous and strictly increasing, whereas \( \delta_c \) has a jump). Contradiction. Concretely: \( \mathbb{P}\left( |\overline{X}_n - c| \geq 1 \right) \geq \mathbb{P}\left( \overline{X}_n \geq c + 1 \right) = 1 - F(c+1) \gt 0 \), a constant independent of \( n \), so the defining limit of convergence in probability fails at \( \varepsilon = 1 \). Step 3: which hypothesis fails. Integrability: \( \mathbb{E}|X_1| = \frac{2}{\pi}\int_0^\infty \frac{x}{1+x^2}\,dx = \infty \) (the integrand decays like \( \frac{1}{x} \)), so \( X_1 \) has no mean, a fortiori no variance, and neither the Chebyshev version nor Khinchin's version applies. This also violates the Kolmogorov–Feller tail condition: \( n\,\mathbb{P}(|X_1| \gt n) = n \cdot \frac{2}{\pi}\left( \frac{\pi}{2} - \arctan n \right) \to \frac{2}{\pi} \neq 0 \), confirming that no centring constants can rescue a weak law here.