Chapter 7 companion · Averages and assumptions
Which law of large numbers?
“The average settles down” hides several questions. What kind of convergence? How much integrability? How independent? Does the population change? The answers determine which theorem you can use.
Start with the question you want to answer
Let Sₙ=X₁+⋯+Xₙ and X̄ₙ=Sₙ/n. For iid observations with a finite absolute first moment, write μ=EX₁. “Weak” and “strong” describe conclusions, not two different sample sizes. Under these iid assumptions both laws hold, and L¹ convergence holds too.
The first route needs expectation, variance, independence, and Markov’s and Chebyshev’s inequalities. The extensions introduce Borel–Cantelli, conditional expectation, and stationary processes as needed. An almost-sure assertion means probability one, not every imaginable outcome.
1. Four meanings of “settles down”
| Mode | Definition for Yₙ → μ | Question it answers |
|---|---|---|
| In probability | For every ε>0, P(|Yₙ−μ|>ε)→0. | At a specified late time, how likely is a noticeable error? |
| Almost surely | P({ω : Yₙ(ω)→μ})=1. | For almost every trajectory, does it eventually stay inside every tolerance? |
| In L¹ | E|Yₙ−μ|→0. | Does expected absolute error vanish? |
| In L² | E[(Yₙ−μ)²]→0. | Does mean squared error vanish? |
almost surely ⇒ in probability
L²⇒L¹ follows from Cauchy–Schwarz; L¹⇒probability follows from Markov. Almost-sure convergence implies convergence in probability by applying bounded convergence to the error indicators. Almost sure and L¹ do not imply one another for arbitrary sequences. Convergence in distribution to a constant is equivalent to convergence in probability to that constant.
Two examples separating the modes
Small probabilities, infinitely many failures. Let Yₙ be independent indicators with P(Yₙ=1)=1/n, n≥2. Then E(Yₙ²)=1/n→0, so Yₙ→0 in L² and probability. But Σ1/n diverges, so the second Borel–Cantelli lemma gives Yₙ=1 infinitely often almost surely. There is no almost-sure convergence to zero.
Almost sure, but not L¹. Take one U uniform on (0,1), and put Zₙ=n·1{U≤1/n}. For every U>0, Zₙ eventually equals zero, but E|Zₙ|=1 for every n. Rare events carry a nonvanishing expected cost.
These are examples of random sequences. A genuine sample-average weak law without a strong law appears in Example 5 below.
2. A map of the versions
Rows 1–4 are the core course route. The remaining rows show which hypotheses can change. “Centered” means subtracting each variable’s own mean; that distinction matters when the distributions vary.
| Version | Sufficient assumptions | Conclusion | What changes? |
|---|---|---|---|
| Chebyshev / L² weak law | Pairwise uncorrelated, finite variances; Σᵢ≤ₙ Var(Xᵢ)/n² → 0. | (Sₙ−ESₙ)/n → 0 in L², hence L¹ and probability. | No identical-distribution assumption. The center is the average of the means. |
| Integrable iid weak law | Independent and identically distributed; E|X₁| < ∞. | X̄ₙ → μ in probability. | Finite variance is unnecessary; truncation replaces the variance proof. |
| Integrable iid strong law | The same iid and absolute-integrability assumptions. | X̄ₙ → μ almost surely. | A statement about eventual behavior of almost every whole trajectory. |
| L¹ law for iid averages | Again iid and E|X₁| < ∞. | E|X̄ₙ−μ| → 0. | Expected absolute error vanishes, including rare large errors. |
| Kolmogorov: independent, nonidentical | Independent, finite variances; Σᵢ≥₁ Var(Xᵢ)/i² < ∞. | (Sₙ−ESₙ)/n → 0 almost surely. | Uniformly bounded variances suffice. A fixed limit needs convergence of the average means. |
| Etemadi: pairwise independence | Pairwise independent, identically distributed; E|X₁| < ∞. | X̄ₙ → μ almost surely. | Joint independence can be weakened; pairwise uncorrelated alone is not this theorem. |
| Bounded martingale differences | E[Dᵢ | past] = 0 and |Dᵢ| ≤ C for a fixed C. | (D₁+⋯+Dₙ)/n → 0 almost surely. | Dependence is allowed when each next increment is conditionally centered. Azuma gives summable tails. |
| Stationary ergodic law | Stationary, ergodic sequence; E|X₁| < ∞. | X̄ₙ → EX₁ almost surely and in L¹. | Ergodicity replaces independence: invariant information is trivial. |
| Stationary law without ergodicity | Stationary sequence; E|X₁| < ∞. | X̄ₙ → E[X₁ | invariant information] almost surely and in L¹. | The limit can be random. See the shared hidden coin. |
| Triangular-array weak law | Row n: variables Xₙ,ᵢ, 1≤i≤n, uncorrelated with finite variances; n⁻²Σᵢ Var(Xₙ,ᵢ) → 0. | The centered row average tends to 0 in L². | Each row can describe a different experiment; no independence between rows is needed. |
| Polynomially weighted iid law | iid integrable; deterministic weights wᵢ=iᵃ with fixed a≥0. | Σᵢ≤ₙ wᵢXᵢ / Σᵢ≤ₙ wᵢ → μ almost surely. | Summation by parts transfers the ordinary strong law. Arbitrary weights need additional conditions. |
| Glivenko–Cantelli uniform law | iid real observations, with any distribution function F. | supₜ |Fₙ(t)−F(t)| → 0 almost surely. | Uniform over all thresholds at once; no moment condition is required for these bounded indicators. |
These are useful sufficient conditions, not a catalogue of necessary-and-sufficient criteria. In particular, absolute integrability is not necessary for every possible iid weak law with a finite limiting constant. The Cauchy example demonstrates a failure; it does not classify all infinite-mean distributions.
Stationary means the joint law is unchanged by shifting time. Ergodic means events unchanged by that shift have probability zero or one. “Invariant information” describes features of the experiment that do not change as time advances, such as a bias chosen once for a hidden coin.
3. Why the core laws work
The easy weak law: variance plus Chebyshev
For independent copies with variance σ²<∞, E(X̄ₙ)=μ and Var(X̄ₙ)=σ²/n. Thus
Only zero pairwise covariances were used in the variance calculation. More generally, Var(X̄ₙ)=n⁻²(ΣVar(Xᵢ)+2Σᵢ<ⱼCov(Xᵢ,Xⱼ)). Controlling this whole expression gives a weak law even under dependence.
Remove finite variance by clipping
For iid integrable Xᵢ, clip each observation at height M: Xᵢ⁽ᴹ⁾=max(−M,min(Xᵢ,M)). These bounded observations have finite variance. Add and subtract the clipped average and its mean, use the triangle inequality, and then Cauchy–Schwarz:
First fix M and let n grow. Then let M grow: the first term tends to zero by integrability. This proves L¹ convergence, hence the full integrable iid weak law.
A strong-law proof when variance is finite
Put Tₖ=Sₖ−kμ. Kolmogorov’s maximal inequality for independent centered finite-variance sums gives
The bounds are summable over m. The first Borel–Cantelli lemma says that almost surely only finitely many of these maximum events occur. If 2ᵐ⁻¹<n≤2ᵐ, eventually |Tₙ|/n≤2ε. Use ε=1,1/2,1/3,… on a common probability-one event to obtain Tₙ/n→0.
Why the plain weak-law bound is insufficient: Σ1/n diverges, so applying Borel–Cantelli directly to the Chebyshev bound does not prove the strong law. Divergence of an upper-bound series also does not prove infinitely many failures.
How the integrable strong law removes the variance assumption
For iid integrable Xᵢ, put Yᵢ=Xᵢ·1{|Xᵢ|≤i}. Integrability implies ΣP(|Xᵢ|>i)<∞, so Xᵢ=Yᵢ eventually almost surely. Also
For |X₁|≥1 the inner sum is bounded by a constant divided by |X₁|; for |X₁|<1 use X₁²≤|X₁|. Kolmogorov’s independent-series convergence criterion then makes Σ(Yᵢ−EYᵢ)/i converge almost surely. Kronecker’s lemma turns convergence of that series into n⁻¹Σᵢ≤ₙ(Yᵢ−EYᵢ)→0. Finally EYᵢ→μ, so their Cesàro averages tend to μ; the finitely many changed observations do not affect the average.
The independent-series criterion and Kronecker’s lemma are the additional ingredients in this proof route; the finite-variance argument above alone does not cover this case. Durrett’s Chapter 2 develops both ingredients.
4. Examples that change the answer
Example 1. A coin: a guarantee, a limit, and a fluctuation scale
For iid Bernoulli(p), Var(X̄ₙ)=p(1−p)/n≤1/(4n). To guarantee P(|X̄ₙ−p|>0.05)≤0.05 using Chebyshev, it suffices to take n≥2000. This bound is conservative. The strong law describes eventual settling of a trajectory and supplies no deterministic time after which every trajectory is accurate.
Hoeffding’s inequality improves the bounded iid guarantee to P(|X̄ₙ−p|≥ε)≤2exp(−2nε²). These exponential bounds are summable in n and give a bounded-variable strong law through Borel–Cantelli. The CLT instead describes √n(X̄ₙ−p)/√(p(1−p)) for 0<p<1; it gives an asymptotic normal approximation, not a universal exact guarantee.
Example 2. A mean exists even when variance does not
Let X have density f(x)=(3/2)x⁻⁵ᐟ² for x≥1, zero otherwise. Integrating gives EX=3 and EX²=∞. Iid averages converge to 3 almost surely and in L¹. They do not converge in L²: since the observations are positive, each finite sample average still has infinite second moment. The ordinary finite-variance CLT and its standard error do not apply.
Example 3. Cauchy averages do not concentrate
A standard Cauchy has density 1/[π(1+x²)] and no expectation. Its characteristic function is exp(−|t|); independence gives φX̄ₙ(t)=[exp(−|t|/n)]ⁿ=exp(−|t|). Every average is again standard Cauchy. In particular, P(|X̄ₙ|>1)=1/2 for every n. Symmetry around zero does not create a mean or a law of large numbers at zero.
Example 4. Independent observations from a changing population
Take independent Xᵢ∼Bernoulli(pᵢ). Since Var(Xᵢ)≤1/4, ΣVar(Xᵢ)/i²<∞, so X̄ₙ−n⁻¹Σpᵢ→0 almost surely. For alternating pᵢ=0.2,0.8, the average tends to 0.5. But choose alternating 0.2 and 0.8 blocks, each so long that all earlier blocks form a vanishing fraction of its length: the averages of the means then have subsequential limits 0.2 and 0.8. No constant limit follows, even though the centered strong law still holds.
Example 5. A genuine weak law without a strong law for sample averages
This example is independent but deliberately not identically distributed. For k≥1, let X2k equal +2ᵏ or −2ᵏ with probability 1/(2k) each, and zero otherwise. All other Xᵢ are zero. The choices at the powers of two are independent and every EXᵢ=0.
For 2ᵐ≤n<2ᵐ⁺¹, E[(Sₙ/n)²]≤4⁻ᵐΣₖ≤ₘ4ᵏ/k→0. Split the sum at m/2: the early part is O(2⁻ᵐ), and the later part is at most 8/(3m). Thus Sₙ/n→0 in L² and probability.
However, the independent jump events have probabilities 1/k and occur infinitely often almost surely by Borel–Cantelli. Thus Xₙ/n does not tend to zero. If Sₙ/n had any finite limit, the identity Xₙ/n=Sₙ/n−((n−1)/n)(Sₙ₋₁/(n−1)) would force Xₙ/n→0. Therefore no finite almost-sure limit exists.
Example 6. A random limit under dependence
Choose Θ=0.2 or 0.8 with equal probability once, and then draw conditionally iid Bernoulli(Θ) observations. Every Xᵢ has unconditional mean 0.5, but the conditional strong law gives X̄ₙ→Θ almost surely. The sequence is stationary and exchangeable, but not ergodic.
Var(X̄ₙ)=0.09+0.16/n.
The common hidden bias does not average away. This is the accessible meaning of a conditional ergodic limit. See the exchangeability and Pólya lab. Perfect dependence is even simpler: if Xᵢ=Z for every i, every average is Z.
Example 7. Pairwise independence without joint independence
In each independent block choose two independent fair bits Aₖ,Bₖ and output Aₖ, Bₖ, Aₖ XOR Bₖ. Every pair in a block is independent; pairs in different blocks are independent too. But the third bit is determined by the first two, so the sequence is not jointly independent. All observations are Bernoulli(1/2). Etemadi’s theorem gives a strong law to 1/2. For this particular block construction, grouping into iid three-bit blocks also supplies a direct proof.
Example 8. Rare successes: average versus count
Row n has n independent Bernoulli(1/n) observations. The row average has mean 1/n and variance (1−1/n)/n², hence tends to zero in L². The row count Cₙ has mean 1 and variance 1−1/n, and converges in distribution to Poisson(1). Indeed P(Cₙ=0)=(1−1/n)ⁿ→e⁻¹, so P(|Cₙ−1|>1/2) does not tend to zero. More trials do not give a small relative error when the expected number of successes stays bounded.
Example 9. One threshold versus all thresholds
For each fixed t, apply the Bernoulli strong law to 1{Xᵢ≤t}: Fₙ(t)→F(t) almost surely. Glivenko–Cantelli says more: the largest discrepancy over all t tends to zero. Taking an uncountable intersection of pointwise probability-one events is not a proof. One can instead use finitely many probability brackets at each accuracy and monotonicity; this handles atoms as well as continuous distributions.
5. Change the model, not just the sample size
One trajectory versus many experiments
The average tends to 0.5 almost surely and in L¹ and L². Chebyshev and Hoeffding give finite-sample bounds.
Teal, brown, and purple show three experiments. Dashed line: reference mean 0.5; shading: ±0.1. The vertical scale adjusts to include every displayed point. Points are sampled for display; every observation contributes to each mean.
The percentage estimates a fixed-time probability; following a path asks a different question. These are reproducible pseudorandom finite experiments, not proofs of convergence or evidence that rare events cannot occur. For Cauchy, “error” here means distance from the symmetry center.
6. Choose a theorem before averaging
- Specify the target. A common mean, a Cesàro average of changing means, a conditional mean, or a distribution function?
- Check moments. Absolute first moment for the basic iid strong law; second moment for L² and the usual standard error.
- Check the dependence structure. Independence, pairwise independence, controlled covariances, conditional centering, or stationarity plus ergodicity?
- Choose the conclusion. A fixed-time probability, eventual path behavior, expected error, or uniform accuracy over a family?
- Separate consistency from precision. A limit theorem alone need not give a practical sample size. Use a valid finite-sample bound or a justified approximation.
7. Exercises with worked answers
1. How large n makes the worst-case Bernoulli Chebyshev bound at ε=0.02 at most 0.01?
Solve 1/(4n·0.02²)≤0.01, giving n≥62,500. This is a sufficient worst-case bound, not a claim that smaller samples fail.
2. Why does an iid Pareto sample with tail P(X>x)=x⁻³ᐟ² obey a strong law?
EX=1+∫₁∞x⁻³ᐟ²dx=3<∞. The integrable iid strong law applies even though EX²=∞. The L² conclusion and ordinary finite-variance CLT are unavailable.
3. Does almost-sure convergence imply vanishing expected absolute error?
No. Zₙ=n·1{U≤1/n} tends to zero almost surely but E|Zₙ|=1. Additional control, such as uniform integrability, is needed. Iid integrable sample averages do have L¹ convergence by the clipping proof.
4. Derive the hidden-coin variance formula.
Conditional variance gives E[Var(X̄ₙ|Θ)]=E[Θ(1−Θ)]/n=0.16/n. The variance of E[X̄ₙ|Θ]=Θ is 0.09. Add them. For distinct observations, conditional covariance is zero, leaving Cov(Xᵢ,Xⱼ)=Var(Θ)=0.09.
5. Do independent observations with variances bounded by 100 satisfy a centered strong law?
Yes: ΣVar(Xᵢ)/i²≤100Σ1/i²<∞. Kolmogorov gives (Sₙ−ESₙ)/n→0 almost surely. A numerical limit for Sₙ/n still requires the average expectations to converge.
6. Why is the standard CLT different from a law of large numbers?
The LLN sends the unscaled error to zero. The standard iid finite-variance CLT rescales it by √n and gives a nondegenerate normal limiting distribution when σ²>0. Neither theorem says every realized average moves monotonically toward its target.
7. Check the XOR block’s pairwise independence and its joint dependence.
Each pair of coordinates takes the four possible bit pairs with probability 1/4. But the only three-bit strings are 000,011,101,110, each of probability 1/4; independent fair bits would permit all eight strings.
8. Show that bounded martingale differences obey a strong law.
For |Dᵢ|≤C and E[Dᵢ|past]=0, Azuma–Hoeffding gives P(|ΣDᵢ|≥nε)≤2exp(−nε²/(2C²)). Sum over n, apply Borel–Cantelli, and intersect over positive rational ε. The result is ΣDᵢ/n→0 almost surely.
9. Can an LLN correct selection bias?
No. If the observations are iid from the wrong population, the sample average consistently estimates that population’s mean. Increasing n can make an incorrect target estimate very precise.