Skip to content

Lesson 15 · Monte Carlo Integration

Hit-or-Miss Integration

Estimate definite integrals by throwing random points under a curve, compute the error bar, and see how it compares with the rectangle rule.

A definite integral ∫ₐᵇ f(x) dx is the area between the graph of f and the x-axis. Many integrals have no neat formula. Monte Carlo can still estimate them. The simplest method, hit-or-miss integration, is the dart-throwing idea from the π lesson, aimed at the area under any curve.

The method

Assume 0 ≤ f(x) ≤ H on the interval [a, b]. The curve lives inside a rectangle of width b − a and height H, whose area is (b − a)·H.

  1. Throw N darts uniformly into the rectangle: x uniform on [a, b], y uniform on [0, H].
  2. Count the hits: darts with y ≤ f(x).
  3. Because the fraction of hits estimates the fraction of the rectangle under the curve,
Text
∫ₐᵇ f(x) dx ≈ (b − a) · H · (hits / N)
flowchart LR
  A["Bounding rectangle<br/>area = (b-a) H"] --> B["N random darts"]
  B --> C["hits: y ≤ f(x)"]
  C --> D["integral ≈ area × hits/N"]

Hit-or-miss: the integral is a fraction of a known rectangle.

Example: the integral of sin(x) from 0 to π

The exact value is 2, since ∫₀^π sin x dx = [−cos x]₀^π = 1 − (−1) = 2. Here f is at most 1, so take H = 1.

Python Hit-or-miss for sin(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.

The 95% margin 1.96 × SE shrinks about 10 times for each 100-fold increase in N, just as the 1/√N rule predicts. Each estimate should lie within its margin of 2 about 95% of the time.

Seeing it

Python Darts under the sine curve

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.

Choosing H

H must be at least the maximum of f on the interval. A larger H is still correct but wasteful: more darts land high and miss, and the estimate becomes noisier. If you cannot find the exact maximum, take a generous upper bound, or evaluate f on a fine grid and add a small margin. If f can be negative, shift the problem: integrate f(x) + c (with c large enough to make it nonnegative) and subtract c·(b − a).

Python Effect of H on accuracy

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.

The standard error grows with H. Doubling H wastes half of the darts and increases the error by about √2.

Comparison with ordinary quadrature

In one dimension, classical numerical rules like the trapezoid rule converge much faster than Monte Carlo. For a smooth function, the error with N points shrinks like 1/N², versus 1/√N for Monte Carlo. So for a plain 1D integral you should not use Monte Carlo. We study it anyway for three reasons:

  • It generalizes immediately to many dimensions, where grid methods fail (later in this chapter).
  • It works for irregular, discontinuous or noisy integrands.
  • It gives a statistical error bar for free.
Python Monte Carlo against the trapezoid rule

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.

The trapezoid error collapses far faster. Monte Carlo's advantage is not speed in 1D, but flexibility and dimension-independence.

Hit-or-miss is the easiest Monte Carlo integrator but not the best. The next lesson uses the average of f itself, which always has a smaller (or equal) variance.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In hit-or-miss integration over [a, b] with bound H, 600 of 2,000 darts land under the curve. If (b − a) = 5 and H = 4, what is the estimate?

    Rectangle area = 5 × 4 = 20; the hit fraction is 600/2000 = 0.3; the estimate is 20 × 0.3 = 6.
  2. 2. What happens if you choose H much larger than the maximum of f?

    A larger bound wastes darts. The estimate is still correct on average, but its variance increases.
  3. 3. For a smooth one-dimensional integral, which method usually converges faster?

    Deterministic rules like the trapezoid rule beat the 1/√N rate of Monte Carlo in one dimension.
  4. 4. Which is a reason to prefer Monte Carlo integration anyway?

    Dimension-independent convergence and flexibility are Monte Carlo's strengths.

Summary

  • Hit-or-miss integration: integral ≈ (b − a)·H·(hits/N) for 0 ≤ f ≤ H.
  • The standard error comes from the binomial formula: (b−a)·H·√(p(1−p)/N).
  • A larger bound H is safe but noisier.
  • In 1D, deterministic quadrature is much faster; Monte Carlo pays off in high dimensions and for rough integrands.

Next: Sample-Mean Integration