Unit 3.6 · about 4 h
70 / 324Laws of large numbers, CLT, concentration and Monte Carlo
Every simulation check in this stage, and every bootstrap and permutation test later, stands or falls on whether the samples are independent with a finite variance and whether the error bar is quoted.
- derive
- measure
You can now
- Explain law-of-large-numbers behavior, central-limit approximations, and when heavy tails or dependence undermine them.
- Derive Markov, Chebyshev and Hoeffding bounds for a stated model and name the assumption each one uses.
- Build a Monte Carlo estimator with a \(1/\sqrt{n}\) standard error and confirm the scaling by measurement.
Covers
- Law of large numbers and central-limit behavior
- Concentration bounds and what breaks under dependence or heavy tails
- Monte Carlo estimation and sampling error
Study, in this order
4 steps
- Inequalities, LLN and CLTHarvard Stat 110 - Probability
Lecture 28: Cauchy-Schwarz, Jensen, Markov and Chebyshev inequalities; Lecture 29: law of large numbers and central limit theorem
- Inequality and limit-theorem drillsStat 110 Strategic Practice
Strategic Practice set 10, Inequalities Q1-4: the inequality comparison table, Jensen for \(\mathbb{E}(1/X)\), the Chebyshev sample-size question and AM-GM
- LLN, CLT and Monte Carlo drillsStat 110 Strategic Practice
Strategic Practice set 11, LLN and CLT Q1-5: convergence modes, Poisson-to-Normal, norming and the rectangle-integral Monte Carlo example
- CLT and Monte Carlo approximationProbabilistic Machine Learning: An Introduction
Chapter 2, Sections 2.8.6-2.8.7 (pp. 72-73): central limit behavior and the Monte Carlo approximation of a distribution
Focus on
- Each bound buys generality with looseness: Markov needs only non-negativity, Chebyshev adds a finite variance, Hoeffding adds bounded independent summands.
- The CLT describes the standardized mean, not the raw sum and not the underlying distribution. \(n = 30\) is folklore, not a theorem.
- Monte Carlo error scales as \(1/\sqrt{n}\): one more decimal digit costs 100 times the samples. Quote every estimate with its standard error.
- Dependence and heavy tails break the standard bars. An MCMC-style correlated stream or a Cauchy average needs its own analysis.
Reproduce closed-book
float64: numpy.random.default_rng(51), 400000 standard_normal draws give tail fraction 0.04596 with standard error 0.00033; Chebyshev allows \(P(|Z|>2) \le 1/4=0.25\), loose but valid since \(\operatorname{Var}(Z)=1\); Hoeffding gives \(P(|\hat{p}-p| \ge 0.05) \le 2\exp(-10)=9.08 \times 10^{-5}\) for 2000 independent fair-coin flips.Traps
- Reading a bound as an approximation. Chebyshev's 0.25 against the true 0.0455 is a guarantee, not a prediction.
- Applying Hoeffding to dependent or unbounded summands. Independence and boundedness enter the proof; dropping either voids it.
- Judging convergence from one sample size. Halve the observed standard error across a 4x sample-size run before claiming \(1/\sqrt{n}\) scaling.
Practice
Stat 110 Strategic Practice 11: LLN and CLT Q1-5
Strategic Practice Q1-5 with the inline solutions; Ultimate Homework Q1 (log-scale stock price, LLN versus CLT) and Q2 (chi-square and Student-t limits) in the same file
Attempt each problem before reading its solution. The solutions are printed in the same file.
Stat 110 Strategic Practice 10: Inequalities Q1 and Q3
Strategic Practice set 10, Inequalities Q1 (comparison table) and Q3 (sample size for a 99 percent chance that the sample mean lands within 2 standard deviations)
Attempt before reading the solutions printed in the same file.
Self-test
-
Prove Chebyshev from Markov and name the step that needs a finite variance.
\(P(|X-\mu| \ge k\sigma)=P((X-\mu)^2 \ge k^2\sigma^2) \le \mathbb{E}[(X-\mu)^2]/(k^2\sigma^2)=1/k^2\). Markov needs a non-negative variable, supplied by squaring; finiteness of \(\mathbb{E}[(X-\mu)^2]\) is the variance assumption. -
Why is Hoeffding's 9.08e-05 far below Chebyshev-style bounds for the coin example, and what does it cost?
Hoeffding exploits bounded independent summands to get exponential tails, while Chebyshev uses only variance for \(1/k^2\) tails. The cost is the stronger assumption: boundedness plus full independence. -
Averages of 100 Cauchy draws still jump around. Which assumption fails for the LLN and the CLT?
Finite mean for the LLN and finite variance for the CLT. Cauchy has neither, so neither theorem applies; the sample mean stays Cauchy at every n. -
Your Monte Carlo tail estimate at \(n=400000\) gives 0.04596 with SE 0.00033. How many draws for SE 0.0001?
About \((0.00033/0.0001)^2=11\) times more, roughly 4.4 million draws. Standard error scales as \(1/\sqrt{n}\), so a 3.3x reduction needs an 11x sample.
Completion criterion
Stop when
You derive Markov-to-Chebyshev without notes, your rerun of the seed-51 check matches 0.04596 to 4 decimals with its standard error, and you can state which bound applies to a new sampling scheme and why.
Mark passed, then open 3.7 Only mark this when you can do it without notes.Leads to
- 4.4 Bootstrap, permutation tests and multiple comparisons Bootstrap and permutation resampling inherit these Monte Carlo error bars.
- 5.6 Paired bootstrap, permutation tests and multiplicity Apply concentration thinking to paired resampling comparisons.
Comes after
- 3.3 Expectation, variance, covariance and conditioning lawsFeed these moments into concentration bounds and Monte Carlo standard errors.
Resources for this unit
- Harvard Stat 110 - Probability Follow lectures 4-14, 17-23 and 25-30 with matching Strategic Practice. Use lectures 1-3 only for prerequisite repair.
- Stat 110 Strategic Practice Solve the matching sets before marking a probability topic Practised; use solutions to audit reasoning, not to begin it.
- Probabilistic Machine Learning: An Introduction Consult targeted parts of Chapters 2, 3, 4 and 6 for ML notation, Monte Carlo, factorization, posterior prediction and information theory.
Also in this section
- MIT 18.05 - Bayesian bridge Use classes 10-16 for MLE, Bayesian updating, posterior prediction, conjugacy, prior choice and credible intervals.
- D2L - Information Theory Use §§22.11.1-22.11.5 for runnable entropy, cross-entropy, KL and mutual-information examples and exercises.