Monte Carlo integration

When extending integration techniques to higher dimensions, traditional methods face significant challenges:

• Exponential Increase in Sample Points: Sampling each dimension with $N$ points requires $N_{total} = N^D$ points.
• Error Scaling: The approximation error, a function of $\Delta t = L/N$, scales as $\Delta t^k$. In higher dimensions, this results in $N^{-k} = N_{total}^{-k/D}$, indicating less efficient error reduction with increasing dimensions.

Example: In a 10-dimensional space, even a modest $N = 10$ per dimension results in $10^{10}$ total sample points, demonstrating the impracticality of traditional grid-based sampling in high dimensions.

This sets the stage for exploring Monte Carlo methods, which offer a viable solution to these multidimensional challenges.

We can see that for large dimensions the scaling is quite poor with traditional integration methods

We can abandon the requirement of sampling along a fixed size grid and sample points randomly.

Monte Carlo integration offers a powerful solution for high-dimensional integrals:

The integral of a function $f(x)$ over a domain $\Omega$ is approximated as:

$$ \int_\Omega f(x) \;dx \approx \frac{V}{N} \sum\limits_{i=1}^N f(r_i) $$

where,

• $V = \int_\Omega \;dx$ is the volume of the integration domain.
• $r_i$ are random points within the domain $\Omega$.
• $N$ is the number of random points used in the approximation.

Example: Estimating the area under a curve in a unit square by averaging the function values at random points within the square.

This approach bypasses the curse of dimensionality faced by grid-based sampling methods.

Understanding Convergence in Monte Carlo Integration

Exploring convergence through a specific function:

Consider the function $f(x) = \prod_i x_i$, which is the product of variables over dimensions.

Integrating over a unit cube in $D$ dimensions:

$$ I_D = \int_0^1 dx_1 \dots \int_0^1 dx_D\; x_1 \dots x_D = 2^{-D} $$

This integration helps illustrate how Monte Carlo methods perform in multidimensional spaces.

Now, let's plot the error as a function of dimensionality:

$$ E(D) = \left| 2^D I_D -1 \right|$$

The error scales as $1/\sqrt{N_{total}}$ regardless of the dimension!

For high dimensions this is going to be better than regular sampling!