Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 38 · Monte Carlo Integration

Sample-Mean Integration

Estimate integrals as the interval length times the average of f at random points, use any sampling density, and compare variance with hit-or-miss.

Hit-or-miss integration throws away information: it records only whether a dart is under the curve, not how far under. A better idea uses the actual value of the function. The result, sample-mean integration (also called crude Monte Carlo), is the workhorse method of the field.

Integral as an expected value

If U is uniform on [a, b], its density is 1/(b − a), so the expected value of f(U) is

Text
E[f(U)] = ∫ₐᵇ f(x) · 1/(b−a) dx = (1/(b−a)) ∫ₐᵇ f(x) dx.

Rearranging, ∫ₐᵇ f(x) dx = (b − a) · E[f(U)]. By the law of large numbers, average f at N random points:

Text
I ≈ (b − a) · (1/N) · Σ f(xᵢ),   xᵢ uniform on [a, b].

That is it: the interval length times the average height. The standard error is (b − a) · s / √N, where s is the sample standard deviation of the values f(xᵢ).

Example

Integrate f(x) = e^(−x²) over [0, 2]. This integral has no elementary closed form, but it equals (√π/2)·erf(2) ≈ 0.8821, and SciPy provides the error function erf for a reference.

Python Sample-mean estimate of the integral of exp(-x²)

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why it beats hit-or-miss

Compare the variance of the two estimators for the same problem. In hit-or-miss, each dart contributes a 0 or a 1, which is a very coarse measurement. In sample-mean integration each point contributes the smooth value f(x). Mathematically, the sample-mean estimator never has larger variance than hit-or-miss with the same N. Run both on the same integral and compare their spread over repeated runs.

Python Variance: hit-or-miss versus sample mean

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both have the same mean (they are both unbiased), but the sample-mean standard deviation is clearly smaller, so you get the same accuracy with fewer points.

Using other sampling densities

You are not forced to sample uniformly. Suppose X has density p(x) on [a, b]. Then

Text
I = ∫ f(x) dx = ∫ [f(x)/p(x)] · p(x) dx = E[ f(X)/p(X) ].

So draw xᵢ from p and average f(xᵢ)/p(xᵢ). The uniform case has p = 1/(b−a), giving back the formula above. Why bother? If p is large where f is large, the ratio f/p becomes nearly constant, and an estimator of a nearly constant quantity has almost no variance. This is importance sampling, the first variance reduction technique of the next chapter. For now, check that it works.

Python A non-uniform sampling density

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both estimates target the same integral (about 0.8821). The truncated exponential follows the shape of e^(−x²) more closely than a flat density does, so its standard error is somewhat smaller. Poor choices can instead increase the variance, so always compute the standard error.

If p(x) is much smaller than f(x) anywhere, the ratio f/p becomes huge there and occasional enormous weights ruin the estimate. A sampling density must have heavier tails than the integrand.

Infinite intervals

You can integrate over [0, ∞) by sampling from a density on that range. For ∫₀^∞ e^(−x²) dx = √π/2, draw x from an exponential(1) and average f(x)/e^(−x). The result should be about 0.8862.

Python An integral over [0, infinity)

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In sample-mean integration over [a, b] with uniform points, the estimate is

    The integral equals (b − a) times the expected value of f at a uniform point.
  2. 2. Compared with hit-or-miss using the same N, sample-mean integration has

    Both are unbiased, but averaging the function values has variance at most that of hit-or-miss.
  3. 3. If points are sampled from density p, what do you average?

    Dividing by p corrects for non-uniform sampling: E[f(X)/p(X)] = ∫ f dx.
  4. 4. The sample values f(xᵢ) over [0, 3] have standard deviation 0.5, with N = 400 points. What is the standard error of the integral estimate?

    SE = (b − a) · s / √N = 3 × 0.5 / 20 = 0.075.

Summary

  • ∫ₐᵇ f dx = (b − a)·E[f(U)], so estimate it by (b − a) times the average of f at random points.
  • The standard error is (b − a)·s/√N, with s the sample standard deviation of the values.
  • It is unbiased and never worse than hit-or-miss.
  • Sampling from a density p requires averaging f/p; a well-matched p reduces variance (importance sampling), a poor one increases it.

Next: Multidimensional Integration