1.43 Monte Carlo sampling: study notes

Learn AI by Story

1. The idea in one sentence

Monte Carlo sampling estimates a hard average, area or integral by drawing random samples and averaging them, so that the error shrinks like 1/√n no matter how many dimensions the problem has.

2. The story from the video

Sam has a square tile of side 1 and a bag of rice. He imagines a quarter circle of radius 1 drawn in the corner of the tile. The quarter circle covers π/4 ≈ 0.7854 of the square's area. So if he throws grains at random onto the square, about 78.54% of them should land inside the quarter circle, and π ≈ 4 × (grains inside) ÷ (grains thrown).

He tries it with 40 grains (a run from a computer simulation with seed 7, illustrative of one run): 32 land inside, giving 4 × 32/40 = 3.2. Not bad, but not great. With a computer he throws more. In one run (seed 42): 100 grains give 3.36; 1,000 grains give 3.156; 10,000 grains give 3.1348; and 1,000,000 grains give 3.142568. The true value is 3.14159.

Sam notices that the error shrinks slowly: to make it ten times smaller, he needs a hundred times more grains. He then generalises: any average E[f(x)] can be estimated by (1/n) Σ f(xᵢ). The surprising part is that this works just as well in 20 dimensions, where a grid with 10 points per axis would need 10²⁰ points.

The video lists uses in AI: mini-batch gradients are Monte Carlo estimates of the full-data gradient, generative models are built so that sampling is the goal, and averaging many sampled predictions gives uncertainty. Then comes the catch: you must be able to sample from the distribution you care about, and that is often the hard part. That leads to the next video, 1.44 MCMC: Metropolis-Hastings and Gibbs. (This video, 1.43, follows 1.42 Markov chains.)

3. Key definitions (glossary)

Monte Carlo method: a way of computing a quantity by using random numbers and averaging the results. Plain English: answer a hard question by running many random experiments.
Sample: one random draw x⁽ⁱ⁾ from a distribution p. Plain English: one thrown grain.
Expectation E[f(x)]: the average value of f(x) when x is drawn from p, written s = E_p[f(x)] (Goodfellow et al., 17.1.2). Plain English: the long-run average of f.
Monte Carlo estimator: ŝₙ = (1/n) Σ f(x⁽ⁱ⁾), the average of f over n samples. Plain English: add up the values and divide by how many you took.
Unbiased estimator: an estimator whose expected value equals the true value: E[ŝₙ] = s. Plain English: on average it is neither too high nor too low.
Law of large numbers: ŝₙ converges to s as n grows (Goodfellow et al., 17.1.2). Plain English: more samples, closer answer.
Variance: Var(X) = E[(X − μ)²], the average squared distance from the mean μ. Plain English: how spread out the values are.
Variance of the estimator: Var[ŝₙ] = Var[f(x)] ÷ n (Goodfellow et al., 17.1.2). Plain English: averaging n values cuts the variance by n.
Standard error: the standard deviation σ of the estimator, equal to √(Var[f(x)] ÷ n). Plain English: the typical size of the error.
Central limit theorem (CLT): for large n, ŝₙ is approximately normally distributed around s, which gives confidence intervals (Goodfellow et al., 17.1.2). Plain English: the error follows a bell curve.
Confidence interval: a range around the estimate that contains the true value with a stated probability. Plain English: an error bar.
Curse of dimensionality: the number of grid points grows exponentially with the number of dimensions. Plain English: grids explode; for 10 points per axis in 20 dimensions you need 10²⁰ points.
Rejection sampling: sample from an easy distribution and keep only the draws that satisfy a rule (Bishop, 11.1.2; MacKay, 29.3). Plain English: throw away the unwanted draws.
Importance sampling: draw from an easy distribution q and reweight each sample by p(x) ÷ q(x) to estimate averages under p (Goodfellow et al., 17.2; Bishop, 11.1.4). Plain English: sample where it is easy, then correct with weights.
Minibatch: a small random subset of the training data used to estimate the gradient. Plain English: a quick poll instead of asking everyone.
Partition function Z: the normalising constant that makes an unnormalised model p̃(x) into a probability, p(x) = p̃(x) ÷ Z. Plain English: the total that is often impossible to compute.
Typical set: the region where most of the probability mass of a high-dimensional distribution lives (MacKay, 29.1). Plain English: where samples actually land.
Pseudorandom numbers: numbers from a deterministic algorithm that behave like random draws; a "seed" fixes the sequence (background). Plain English: repeatable fake randomness.
Markov chain Monte Carlo (MCMC): a method that generates correlated samples by running a Markov chain whose stationary distribution is p (Goodfellow et al., 17.3). Plain English: sample by taking a random walk that spends time in the right places.

4. Detailed explanation, from basics to the full picture

Step 1: Turn an area into a probability

The unit square has area 1 × 1 = 1. The quarter circle x² + y² ≤ 1 inside it has area π/4. If a point is chosen uniformly at random in the square, the probability that it lands in the quarter circle is exactly (area of quarter circle) ÷ (area of square) = π/4 ≈ 0.7854. So π = 4 × P(inside). The unknown π has become a probability, and probabilities can be estimated by counting.

Step 2: Estimate the probability by counting

Throw n points. Count how many satisfy x² + y² ≤ 1; call that k. The fraction k/n estimates π/4, so π̂ = 4k/n. With 40 grains and 32 inside, π̂ = 4 × 32/40 = 3.2.

Step 3: Write it as an average

The count is an average in disguise. Let f(x, y) = 1 if x² + y² ≤ 1, else 0. Then k/n = (1/n) Σ f(xᵢ, yᵢ), which is a Monte Carlo estimate of E[f]. This is the general recipe from Goodfellow et al. (17.1.2): to compute s = E_p[f(x)], draw x⁽¹⁾, …, x⁽ⁿ⁾ from p and compute ŝₙ = (1/n) Σ f(x⁽ⁱ⁾).

Step 4: Why the estimate is trustworthy

Two facts. First, the estimator is unbiased: E[ŝₙ] = s, so on average it hits the target. Second, by the law of large numbers, ŝₙ converges to s as n grows. Goodfellow et al. also give the variance: Var[ŝₙ] = Var[f(x)] ÷ n.

Step 5: The 1/√n error law

Taking the square root of the variance gives the standard error: √(Var[f(x)] ÷ n) = σ ÷ √n. Dividing n by 100 means dividing the error by √100 = 10. So 100 times more samples gives only 10 times less error. That is why going from 100 to 1,000,000 grains (a factor of 10,000 more) shrinks the error by a factor of 100.

Step 6: Put a number on the error for the π experiment

For the π estimator, f is 0 or 1 with success chance p = π/4, so the estimate of π has standard error 4 × √(p(1 − p) ÷ n) ≈ 1.642 ÷ √n. At n = 100 that is 0.164, at n = 1,000 it is 0.052, at n = 10,000 it is 0.0164, and at n = 1,000,000 it is 0.0016. The observed errors in Sam's run (0.22, 0.014, 0.0068, 0.00098) are all within a few standard errors of zero, as the theory predicts. The central limit theorem says that errors are approximately bell-shaped, so a rough 95% error bar is about two standard errors (background).

Step 7: The dimension does not hurt the accuracy

MacKay (29.1) states that Monte Carlo accuracy depends only on the variance of the function being averaged, not on the dimensionality of the space, and that the variance of the estimate goes as σ² ÷ R for R independent samples. A dozen independent samples may already be enough for a rough answer. Compare a grid: 10 points per axis in 20 dimensions has 10²⁰ points, far beyond any computer. Monte Carlo sidesteps the grid completely.

Step 8: The catch, you must be able to sample

The estimator needs independent samples from p. MacKay (29.1) warns that this is the hard part in high dimensions, because probability mass sits in a thin typical set. Simple fixes exist: rejection sampling and importance sampling (Goodfellow et al., 17.2; Bishop, 11.1). When those fail, we run a Markov chain whose stationary distribution is p, which is MCMC (Goodfellow et al., 17.3), the topic of video 1.44 and the reason video 1.42 introduced Markov chains.

5. Everything the video skipped

Variants

Rejection sampling: draw from an easy proposal and accept or reject so the accepted draws follow p (Bishop, 11.1.2; MacKay, 29.3). Works well in low dimensions and badly in high dimensions.
Importance sampling: draw from q and weight by p(x) ÷ q(x), giving E_p[f] ≈ (1/n) Σ f(xᵢ) p(xᵢ) ÷ q(xᵢ) (Goodfellow et al., 17.2). A well-chosen q can reduce the variance a lot, and a poor choice can make it enormous (background).
MCMC: Metropolis-Hastings and Gibbs sampling produce correlated samples from a chain (Bishop, 11.2 and 11.3; MacKay, 29.4 and 29.5).
Hamiltonian Monte Carlo: a more advanced MCMC method that exists; named in MacKay, 30.1.
Parallel and block versions (background): run many independent chains, or update groups of variables together.

Formulas in simple words

Estimator: ŝₙ = (1/n) Σ f(x⁽ⁱ⁾). In words: average f over the samples.
Unbiased: E[ŝₙ] = s. In words: no systematic error.
Variance: Var[ŝₙ] = Var[f(x)] ÷ n. In words: n times more samples, n times less variance.
Standard error: σ ÷ √n. In words: 100 times more samples, 10 times less error.
π estimate: π̂ = 4 × (inside) ÷ (total). In words: the inside fraction times 4.
Importance weights: w(x) = p(x) ÷ q(x). In words: how much to trust a draw from the wrong distribution.

Limitations

You need to be able to sample from p (or from a good proposal).
Rare events need huge n. If an event has probability 10⁻⁶, a run of 1,000 samples will almost never see it.
Slow convergence: halving the error costs four times the samples.
Pseudorandom numbers are only as good as the generator (background).
Samples from MCMC are correlated, so the formula Var ÷ n is too optimistic for them (Goodfellow et al., 17.3).

Background

The name comes from the Monte Carlo Casino in Monaco. According to Wikipedia (second source only), Stanisław Ulam was inspired by his uncle's gambling, and the method grew out of nuclear weapons work at Los Alamos in the 1940s, with John von Neumann involved. Bishop (11.2) cites Metropolis and Ulam (1949) for the early physics origins of MCMC.

Links on the roadmap

Before: 1.42 Markov chains (the engine behind MCMC). After: 1.44 MCMC, then 1.45 Mutual information and Jensen's inequality.

6. Worked examples with real numbers

Example A: Sam's 40 grains

Setup: 40 grains thrown at the unit square, 32 land inside the quarter circle (a simulation run with seed 7, illustrative).

Fraction inside = 32 ÷ 40 = 0.8.
Scale by 4: π̂ = 4 × 0.8 = 3.2.
Error against π ≈ 3.1416: 3.2 − 3.1416 = 0.058.
Standard error at n = 40: 1.642 ÷ √40 = 1.642 ÷ 6.325 ≈ 0.26.

Result: π̂ = 3.2, off by 0.058, well inside one standard error of 0.26, so a single small run is a plausible but noisy answer.

Example B: More grains, smaller error

Setup: one run with seed 42 (illustrative of one run).

n = 100 with 84 inside: π̂ = 4 × 84/100 = 3.36.
n = 1,000 with 789 inside: π̂ = 4 × 789/1,000 = 3.156.
n = 10,000 with 7,837 inside: π̂ = 4 × 7,837/10,000 = 3.1348.
n = 1,000,000 with 785,642 inside: π̂ = 4 × 785,642/1,000,000 = 3.142568.
Predicted standard errors, 1.642 ÷ √n: 0.164, 0.052, 0.0164, 0.0016.

Result: each estimate is within about one or two standard errors of π, and 100 times more samples gave about 10 times smaller error.

Example C: The 1/√n law on a different function

Setup: estimate E[x²] where x is uniform on (0, 1). The true value is ∫₀¹ x² dx = 1/3. The variance arithmetic below was checked in Python for these notes.

Var[f(x)] = E[x⁴] − (E[x²])² = 1/5 − 1/9 = 4/45 ≈ 0.0889.
Standard error at n = 100: √(0.0889 ÷ 100) = √0.000889 ≈ 0.0298.
Standard error at n = 10,000: √(0.0889 ÷ 10,000) ≈ 0.00298.
Ratio: 0.0298 ÷ 0.00298 = 10.

Result: with 100 samples the estimate of 1/3 is typically off by about 0.03; with 10,000 samples, about 0.003, so 100 times more samples gives 10 times less error.

Example D: Why a grid fails and Monte Carlo does not

Setup: you want an average of a function over a 20-dimensional space, using a grid with 10 points per axis.

Points per axis: 10.
Dimensions: 20.
Total grid points: 10²⁰ = 100,000,000,000,000,000,000.
Monte Carlo with n = 10,000 samples has standard error σ ÷ √10,000 = σ ÷ 100, where σ² = Var[f(x)] (MacKay, 29.1: independent of dimension).

Result: the grid needs 10²⁰ evaluations, while 10,000 random samples already give an error of about σ ÷ 100.

Example E: Mini-batch gradients as Monte Carlo

Setup: a training set has N examples and the full gradient is the average of the per-example gradients. A mini-batch of m randomly chosen examples gives a Monte Carlo estimate of that average (Goodfellow et al., 17.1.1). Batch sizes here are illustrative.

The mini-batch gradient ĝ = (1/m) Σ gᵢ is an unbiased estimate of the full gradient when examples are sampled at random.
Its variance is Var[g] ÷ m.
Compare m = 32 and m = 128: the standard error ratio is √(128 ÷ 32) = √4 = 2.

Result: quadrupling the batch size from 32 to 128 halves the noise in the gradient estimate.

7. Comparison tables

Sam's run, one seed

Grains n	Inside	π̂	Standard error
100	84	3.36	0.164
1,000	789	3.156	0.052
10,000	7,837	3.1348	0.0164
1,000,000	785,642	3.142568	0.0016

Grid versus Monte Carlo

Question	Grid	Monte Carlo
Cost in 20 dimensions	10²⁰ points	n samples, any n
Error depends on dimension	Yes, badly	No, only on variance
Error rate	Depends on the rule	σ ÷ √n

Ways to get samples

Method	Idea	Weakness
Direct sampling	Draw from p	Often impossible
Rejection sampling	Keep draws that pass a test	Wasteful in high dimensions
Importance sampling	Reweight draws from q	Bad q gives huge variance
MCMC	Run a Markov chain	Correlated samples, slow mixing

8. Common mistakes and myths

Myth: "Random means inaccurate." Randomness gives an error that is predictable in size: about σ ÷ √n.
Mistake: expecting a fixed run to improve every time. A single run can wobble; the estimate with 1,000 grains was 3.156 while the one with 10,000 was 3.1348, and both are within what the standard error allows.
Mistake: forgetting that 10 times less error needs 100 times more samples.
Myth: "Monte Carlo is a last resort." In high dimensions it is often the best tool, because its accuracy does not depend on the dimension (MacKay, 29.1).
Mistake: ignoring that you must be able to sample from p. That is the catch and the reason for MCMC.
Mistake: treating correlated MCMC samples as independent. The variance Var ÷ n applies to independent samples.
Mistake: treating one seeded run as the truth. The numbers in these notes come from specific seeds and are illustrative of one run.
Myth: "Rare events are easy." Rare events need huge n, or a smarter method such as importance sampling.

9. Real-life and AI uses

Mini-batch gradient descent: Goodfellow et al. (17.1.1) explain that minibatches subsample the training cost, which is a Monte Carlo estimate of the full-data gradient.
Intractable gradients: for some models the gradient of the log partition function is intractable, and sampling gives an approximation (Goodfellow et al., 17.1.1).
Generative models: when the goal is to produce new examples, sampling is the goal itself (Goodfellow et al., 17.1.1).
Uncertainty from many samples (background): averaging many sampled predictions, as in Bayesian predictive averages, gives an uncertainty estimate.
Approximating sums and integrals: when a sum or integral is too expensive to compute exactly, a sample average approximates it cheaply (Goodfellow et al., 17.1.1).
Physics and simulation: the original home of the method at Los Alamos (Wikipedia, second source only; Bishop, 11.2).

10. Self-check questions (with answers)

Why does throwing grains onto a square estimate π? The quarter circle has area π/4 and the square has area 1, so the fraction of grains inside estimates π/4, and π ≈ 4 × inside ÷ total.
With 32 of 40 grains inside, what is π̂? 4 × 32/40 = 3.2.
What is the Monte Carlo estimator of E[f(x)]? ŝₙ = (1/n) Σ f(x⁽ⁱ⁾) with the x⁽ⁱ⁾ drawn from p.
What does "unbiased" mean? The expected value of the estimator equals the true value: E[ŝₙ] = s.
How does the variance of the estimator depend on n? Var[ŝₙ] = Var[f(x)] ÷ n, so it shrinks in proportion to 1/n.
How much more data do you need for 10 times less error? 100 times more samples, because the error falls like 1/√n.
What is the standard error of π̂ with n = 10,000? About 1.642 ÷ √10,000 = 0.0164.
Why does Monte Carlo beat a grid in 20 dimensions? A grid with 10 points per axis needs 10²⁰ points, while the Monte Carlo error depends only on the variance and n, not on the dimension.
Name two uses of Monte Carlo in machine learning. Mini-batch gradients estimating the full-data gradient, and generative models where sampling is the goal.
What is the catch, and what comes next? You must be able to sample from p, which is hard in high dimensions; MCMC (video 1.44) solves it with a Markov chain.

11. Key takeaways, go deeper, next

Key takeaways

Turn the quantity into an expectation E[f(x)] and estimate it by averaging f over random samples.
The estimator is unbiased, and its variance is Var[f(x)] ÷ n, so the error falls like 1/√n.
The accuracy does not depend on the dimension, while grid methods explode (10²⁰ points for 10 points per axis in 20 dimensions).
In AI it appears in mini-batch gradients, generative models and uncertainty estimates.
The catch is sampling from p, handled by rejection sampling, importance sampling and MCMC.

Go deeper

Read Goodfellow et al., chapter 17, sections 17.1 and 17.2, for the basics and importance sampling.
Read MacKay, chapter 29, section 29.1, for why accuracy is independent of dimension and why sampling is hard.
Try it yourself: write five lines of Python that throw 10,000 random points and compute 4 × inside ÷ total; change the seed and watch the answer wobble by about ±0.016.

Next on the roadmap: 1.44 MCMC: Metropolis-Hastings and Gibbs.

12. Sources and further reading

Goodfellow, Bengio and Courville, Deep Learning (2016), Chapter 17 Monte Carlo Methods: 17.1 sampling and Monte Carlo methods, 17.2 importance sampling, 17.3 MCMC
MacKay, Information Theory, Inference, and Learning Algorithms (2003), Chapter 29 Monte Carlo Methods: 29.1 the problems to be solved, 29.3 rejection sampling
Bishop, Pattern Recognition and Machine Learning (2006), Chapter 11 Sampling Methods: 11.1 basic sampling algorithms, 11.2 Markov Chain Monte Carlo
Grinstead and Snell, Introduction to Probability (AMS), Chapter 11 Markov Chains: 11.1 transition matrix and n-step probabilities (background for MCMC)
Wikipedia, Monte Carlo method (second source only), Monte Carlo method: history and name

Accuracy note: Sam, his tile and his rice are an illustrative story. The grain counts (32 of 40 with seed 7; 84, 789, 7,837 and 785,642 with seed 42) come from one computer run each and would differ with another seed. The standard-error values, the variance in Example C and the other arithmetic were checked in Python. The 95% rule of thumb and items marked "(background)" are standard facts that were not taken from the listed sources.

Monte Carlo sampling: study notes