Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 38 · Monte Carlo Integration

Multidimensional Integration

Integrate over boxes and odd regions in many dimensions, see why grid methods fail, and why Monte Carlo's 1/sqrt(N) error ignores dimension.

Monte Carlo integration earns its reputation in many dimensions. A physics model with 20 variables, a financial portfolio with 50 assets, an expected value over 100 random inputs: each is an integral over a high-dimensional space. Traditional numerical methods struggle badly there, while Monte Carlo barely notices. This lesson shows why and how.

The curse of dimensionality for grids

A grid method places points on a regular lattice. With m points per axis in d dimensions you need m^d points. Take m = 10, a very coarse grid:

Dimension d Grid points 10^d
1 10
3 1,000
6 1,000,000
10 10,000,000,000
20 100,000,000,000,000,000,000

The work explodes exponentially. Worse, a rule whose 1D error shrinks like 1/m² has error roughly N^(−2/d) when N total points are used in d dimensions, which becomes painfully slow when d is large.

Monte Carlo's error is σ/√N, independent of d. The dimension affects the variance σ² only through how variable the function is, not through the number of coordinates.

flowchart LR
  A["Grid: N^(-2/d) accuracy"] --> B["bad for large d"]
  C["Monte Carlo: N^(-1/2) accuracy"] --> D["same for every d"]

Error rates with N total points (smooth function, trapezoid-type rule).

The multidimensional estimator

Let V be the volume of a region Ω in d dimensions, and draw x₁, …, x_N uniformly in Ω. Then

Text
∫_Ω f(x) dx ≈ V · (1/N) Σ f(xᵢ)

with standard error V·s/√N. It is the same formula as in 1D, with the length replaced by the volume.

Example: an integral over the unit cube

Integrate f(x₁, …, x_d) = (x₁ + x₂ + … + x_d)² over the cube [0, 1]^d. By linearity of expectation, if the xᵢ are independent uniform, E[(Σxᵢ)²] = Var(Σxᵢ) + (E Σxᵢ)² = d/12 + (d/2)² = d/12 + d²/4. So the exact integral is d/12 + d²/4. Let us check for several d.

Python Integrating over the unit cube in many dimensions

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 same code, with the same sample count, works from d = 1 to d = 200. A grid with even 3 points per axis in 200 dimensions would need 3²⁰⁰ points, more than the number of atoms in the observable universe.

Odd-shaped regions

When the region is not a box, enclose it in a box B of volume V_B and use an indicator function 1_Ω(x), which is 1 inside Ω and 0 outside. Then

Text
∫_Ω f dx = ∫_B f(x)·1_Ω(x) dx ≈ V_B · mean( f(xᵢ)·1_Ω(xᵢ) ).

Points outside Ω simply contribute zero. As a check, using f = 1 gives the volume of Ω itself. This is the dart method again, now with weights.

Python Volume and moment of a 3D ball

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.

For the second integral: in spherical coordinates ∫ r² dV = ∫₀¹ r² · 4πr² dr = 4π/5 ≈ 2.513.

Rare regions and variance

The weakness shows when Ω fills only a tiny fraction of the bounding box, as with the ball in 12 dimensions (previous chapter). Almost all points contribute zero, and the variance relative to the value becomes enormous. When you can, sample inside Ω directly, or use importance sampling and the other tools from Chapter 5.

Convergence check by repetition

A good habit is to test the √N law empirically even in many dimensions.

Python Error versus N in 10 dimensions

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.

On a log-log plot the points follow a straight line with slope −1/2, regardless of the 10 dimensions.

"Independent of dimension" refers to the rate. The variance σ² itself can grow with dimension for particular integrands, and in some problems the effective sample size shrinks. Always look at the reported standard error rather than assuming the theory applies unchanged.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A grid with 10 points per axis in 8 dimensions needs how many points?

    10⁸ = 100,000,000 points: m^d grows exponentially with the dimension d.
  2. 2. How does the Monte Carlo error rate depend on the dimension d?

    The standard error is σ/√N; the dimension enters only through σ.
  3. 3. To integrate over an odd-shaped region Ω, you can

    Points outside Ω contribute 0; the box volume restores the scale: V_box · mean(f · 1_Ω).
  4. 4. Why might the box-and-indicator method be inefficient?

    When Ω has small volume relative to the box, the estimator has huge relative variance.

Summary

  • Grid methods need m^d points and suffer from the curse of dimensionality; Monte Carlo's error σ/√N does not depend on d.
  • Estimate ∫_Ω f dx as V · mean(f(xᵢ)) for uniform points in Ω; use an enclosing box with an indicator for irregular regions.
  • Use f = 1 to test your code on a known volume.
  • Regions that fill little of their bounding box call for smarter sampling.

Next: Quasi-Monte Carlo and Low-Discrepancy Sequences