Chapter 30: Sampling, Monte Carlo & Estimation Error

Chapter 30: Sampling, Monte Carlo & Estimation Error

AI Reading

Quick summary of this article

Preparing the AI summary…

AI Mathematics Masterclass — Chapter 30 of 48

Most integrals in machine learning have no closed form. Expectations over a model’s output distribution, marginal likelihoods, and gradient estimates under a stochastic layer are all intractable analytically — so they are estimated by sampling. Monte Carlo is the only estimation method whose error rate does not degrade with dimension, and that single property is why it dominates inference in modern ML.

1. Technical Audit & Core Learning Objectives

Component Common Tutorial Deficiency Engineering Standard Applied Here
Monte Carlo Presented as “just average random samples”. Framed as the estimator whose error is dimension-independent.
Error rate The 1/√n law stated without comparison. Contrasted with grid methods’ n^(−1/d), which is the whole argument.
Importance sampling Omitted, leaving off-policy evaluation unexplained. Derived with the weight-ratio correction and its variance failure.
Method choice No guidance on which sampler fits which problem. A selection table with the exactness/speed trade-off stated.

Core learning objectives. After this chapter you should be able to:

  1. Estimate an expectation by sampling and state the estimator’s error.
  2. Explain why Monte Carlo error is independent of dimension.
  3. Compute how many samples are needed to halve the error.
  4. Apply importance sampling and state when it fails.
  5. Describe rejection sampling and its acceptance-rate problem.
  6. Choose a sampling method appropriate to a given inference problem.

2. Estimating an Expectation

Random points inside a square estimating a circle's area, with the estimator formula and 1 over root n error
Figure 30.1: Estimating π by sampling. The method knows nothing about circles — it only averages an indicator.
E[f(X)]  ≈  (1/n) sum_i f(x_i)          x_i ~ p

Unbiased: E[estimate] = E[f(X)]
Error:    std = sigma_f / sqrt(n)

To halve the error, quadruple n.
import numpy as np

rng = np.random.default_rng(0)

# estimate pi by sampling the unit square
for n in (1000, 10000, 100000, 1000000):
    pts = rng.uniform(-1, 1, size=(n, 2))
    inside = (pts ** 2).sum(axis=1) <= 1
    est = 4 * inside.mean()
    err = abs(est - np.pi)
    print(f"n={n:8d}  pi_hat={est:.5f}  error={err:.5f}")

The estimator is unbiased and converging. Note the error roughly halves each time n grows by 4 — visible in the table above as the last few rows tighten by a factor of about two for each tenfold increase in n, since √10 ≈ 3.16.

3. Why Dimension Does Not Hurt

Error versus sample count falling as one over root n on a log-like scale
Figure 30.2: The error law depends only on sample count, not on the dimension of the space.
Method Error in d Dimensions Samples for 1% Error at d = 10
Grid n^(−1/d) 10²⁰
Monte Carlo n^(−1/2) 10⁴
import numpy as np

# the 1/sqrt(n) SCALING holds in every dimension, even though the
# constant depends on Var[f(X)], which itself can grow with d
rng = np.random.default_rng(1)
for d in (2, 10, 100):
    row = []
    for n in (500, 8000):
        ests = [(rng.normal(size=(n, d)) ** 2).sum(axis=1).mean() for _ in range(200)]
        row.append(np.std(ests))
    ratio = row[0] / row[1]                 # expect sqrt(8000/500) = 4
    print(f"d={d:4d}  std(n=500)={row[0]:7.4f}  std(n=8000)={row[1]:7.4f}  ratio={ratio:5.2f}")

Read the ratio column, not the absolute errors. In every dimension, going from 500 to 8000 samples divides the error by about 4 — exactly √(8000/500). That is the invariant: the rate is n^(−1/2) regardless of dimension. The constant in front does depend on Var[f(X)], which grows with d in this example, so absolute errors are larger in higher dimensions — but they shrink at the same speed. A grid method's rate would degrade to n^(−1/d), and no number of samples fixes that.

4. Importance Sampling

Target and proposal densities offset from each other with the weight-ratio estimator
Figure 30.3: Sample where it matters, then correct the bias with the density ratio.
E_p[f] = integral f(x) p(x) dx
       = integral f(x) [p(x)/q(x)] q(x) dx
       ≈ (1/n) sum_i w_i f(x_i),     w_i = p(x_i)/q(x_i)

import numpy as np

rng = np.random.default_rng(2)

# target: N(2, 1); proposal: N(0, 1) -- a poor match on purpose
def p(x): return np.exp(-0.5 * (x - 2) ** 2) / np.sqrt(2 * np.pi)
def q(x): return np.exp(-0.5 * x ** 2) / np.sqrt(2 * np.pi)

n = 200_000
xs = rng.normal(0, 1, n)                 # sample from q
w = p(xs) / q(xs)

# self-normalised importance sampling
est = np.sum(w * xs) / np.sum(w)
print(f"importance estimate of E_p[X] = {est:.4f}  (true 2.0)")

print(f"effective sample size {np.sum(w)**2 / np.sum(w**2):.0f} of {n}")
print("  <- far below n: the weights are heavily skewed")

The effective sample size — (Σw)² / Σw² — is the diagnostic that matters. Even with 200,000 draws, a mismatched proposal reduces you to an effective handful. This is why importance sampling is exact in theory and fragile in practice, and why off-policy reinforcement learning clips its ratios.

5. Rejection Sampling

Target density under a flat envelope with the accept-reject procedure and acceptance-rate warning
Figure 30.4: Exact, simple, and exponentially wasteful as dimension grows.
import numpy as np

rng = np.random.default_rng(3)

# sample a truncated distribution by rejection
def target(x):
    return np.exp(-0.5 * (x - 1) ** 2)

M = 1.0                       # envelope height
accepted = []
n_proposals = 100_000
for _ in range(n_proposals):
    x = rng.uniform(-3, 4)    # proposal
    u = rng.uniform(0, M)     # height
    if u <= target(x) / target(1.0) * M:
        accepted.append(x)

accepted = np.array(accepted)
print(f"accepted {len(accepted)}/{n_proposals}  ({len(accepted)/n_proposals:.1%})")
print(f"sample mean {accepted.mean():.4f} (target mean ~1.0)")

Rejection sampling returns exact independent samples, which MCMC cannot. Its cost is the acceptance rate, and in d dimensions the envelope volume grows relative to the target's, so the rate decays exponentially. That is why it is used for one- and two-dimensional problems and abandoned above that.

6. Choosing a Method

Table of six sampling methods with when to use each and the trade-off
Figure 30.5: Exactness and speed trade off against each other across the available samplers.
Method Exact? Typical Use in ML
Reparameterisation trick Yes VAE training — low-variance gradients through sampling
MCMC Asymptotically Posterior inference, uncertainty quantification
Importance sampling Unbiased Off-policy RL, rare-event estimation
Variational inference No (biased) Large-scale posterior approximation

The reparameterisation trick deserves its reputation: writing x = μ + σ·ε with ε ~ N(0,1) moves the randomness outside the parameter, so a gradient can flow through μ and σ. Without it, a sampled layer blocks backpropagation, and VAEs would not train.

7. Worked Examples

7.1 Samples needed for a given error

std of f(X) = 2, want std of estimate = 0.02
n = (sigma / target)^2 = (2 / 0.02)^2 = 10,000

7.2 Variance reduction by averaging

Antithetic sampling: pair each draw with its mirror
For a monotone f, the pair's average has strictly lower
variance than two independent draws.

7.3 Grid versus Monte Carlo

d = 10, target error 1%
Grid needs 100^10 = 10^20 points
Monte Carlo needs about 10^4

7.4 ESS diagnostic

Equal weights w = 1 for all n:  ESS = n
One weight dominates:           ESS ≈ 1
ESS is the sample size you effectively have.

7.5 Reparameterised gradient

x = mu + sigma * eps,  eps ~ N(0,1)
dE[x]/dmu = 1          gradient flows
dE[x]/dsigma = eps     gradient flows
No score-function estimator needed.

8. Verify It in Python

import numpy as np

rng = np.random.default_rng(0)

# --- 1. Monte Carlo estimate of a known expectation --------------
x = rng.uniform(0, 1, 400_000)
assert abs(x.mean() - 0.5) < 0.005
print("E[U(0,1)] estimated:", round(x.mean(), 5))

# --- 2. error scales as 1/sqrt(n) --------------------------------
stds = {}
for n in (1000, 16000):
    stds[n] = np.std([rng.uniform(0, 1, n).mean() for _ in range(400)])
ratio = stds[1000] / stds[16000]
assert abs(ratio - 4.0) < 0.6                 # sqrt(16) = 4
print("error ratio for 16x samples:", round(ratio, 2), "(expect 4)")

# --- 3. dimension does not change the error law -----------------
for d in (2, 50):
    lo = np.std([(rng.normal(size=(400, d)) ** 2).sum(axis=1).mean() for _ in range(200)])
    hi = np.std([(rng.normal(size=(6400, d)) ** 2).sum(axis=1).mean() for _ in range(200)])
    ratio = lo / hi                       # expect sqrt(6400/400) = 4
    assert abs(ratio - 4.0) < 1.0, (d, ratio)
    print(f"d={d:3d} error ratio for 16x samples: {ratio:.2f} (expect 4)")

# --- 4. unbiasedness of the estimator ---------------------------
ests = [rng.uniform(0, 1, 500).mean() for _ in range(3000)]
assert abs(np.mean(ests) - 0.5) < 0.01
print("estimator is unbiased: mean of estimates", round(np.mean(ests), 4))

# --- 5. importance sampling recovers a shifted mean -------------
def p(x): return np.exp(-0.5 * (x - 2) ** 2)
def q(x): return np.exp(-0.5 * x ** 2)
xs = rng.normal(0, 1, 400_000)
w = p(xs) / q(xs)
est = np.sum(w * xs) / np.sum(w)
assert abs(est - 2.0) < 0.05
print("importance sampling estimate of mean:", round(est, 4))

# --- 6. ESS degrades when proposal mismatches -------------------
def ess(weights):
    return weights.sum() ** 2 / (weights ** 2).sum()

def normal_pdf(x, mu):
    return np.exp(-0.5 * (x - mu) ** 2)

n_ess = 100_000
# good proposal: matches the target N(2,1) exactly -> all weights equal -> ESS = n
xs_good = rng.normal(2, 1, n_ess)
w_good = normal_pdf(xs_good, 2) / normal_pdf(xs_good, 2)
# poor proposal: N(0,1) against the same target
w_bad = normal_pdf(xs, 2) / normal_pdf(xs, 0)

assert ess(w_good) > ess(w_bad)
print("ESS matched proposal:", f"{ess(w_good):.0f}",
      " mismatched:", f"{ess(w_bad):.0f}")

# --- 7. rejection sampling acceptance rate ----------------------
accepted = 0
total = 50_000
for _ in range(total):
    xv = rng.uniform(-3, 4)
    if rng.uniform(0, 1) <= np.exp(-0.5 * (xv - 1) ** 2):
        accepted += 1
rate = accepted / total
assert 0.2 < rate < 0.8
print(f"rejection acceptance rate: {rate:.2%}")

# --- 8. reparameterisation gives a usable gradient -------------
eps = rng.normal(size=200_000)
mu, sigma = 0.0, 1.0
x_rep = mu + sigma * eps
grad_mu = np.mean(2 * x_rep)          # for f(x) = x^2, d/dmu = 2*E[x]
assert abs(grad_mu) < 0.05
print("reparameterised gradient of E[x^2] w.r.t. mu:", round(grad_mu, 4))
print("all assertions passed")

9. Practice Questions

  1. Write the Monte Carlo estimator for E[f(X)].
  2. How many samples are needed to halve an estimate's error?
  3. Explain why grid methods fail in ten dimensions.
  4. Derive the importance sampling estimator.
  5. What is effective sample size and what does a low value indicate?
  6. Why does rejection sampling become impractical in high dimensions?
  7. When is the reparameterisation trick applicable?
  8. Give an example of Monte Carlo used in a training loop.
  9. Why is the estimator unbiased even when n is small?
  10. Contrast MCMC and variational inference on bias and speed.

Leave a Reply

Your email address will not be published. Required fields are marked *