Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 38 ยท 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