Why use Monte Carlo method instead of a simple grid?

Question

when integrating a function or in complex simulations, I have seen the Monte Carlo method is widely used. I'm asking myself why one doesn't generate a grid of points to integrate a function instead of drawing random points. Wouldn't that bring more exact results?

Answer 1

I found chapter 1 and 2 of these lecture notes helpful when I asked the same question myself a few years ago. A short summary: A grid with $N$ points in 20 dimensional space will demand $N^{20}$ function evaluations. That is a lot. By using Monte Carlo simulation, we dodge the curse of dimensionality to some extent. The convergence of a Monte Carlo simulation is $O(N^{-1/2})$ which is, albeit pretty slow, dimensionally independent.

Answer 2

While one typically things of rejection sampling when considering Monte Carlo, Markov Chain Monte Carlo allows one to explore a multi-dimensional parameter space more efficiently than with a grid (or rejection sampling for that matter). How MCMC can be used for integration is clearly stated in this tutorial- http://bioinformatics.med.utah.edu/~alun/teach/stats/week09.pdf

Answer 3

Two things -

1. Faster convergence by avoiding curse of dimensionality. Because most points in a grid lie on the same hyper plane without contributing significantly extra information. Random points fill the N-dimensional space evenly. LDS is even better.

2. Sometimes for Monte carlo methods we need statistically random points in no particular order. An ordered sequence of grid points will result in poor statistical properties.

Answer 4

Previous comments are right in that simulation is easier to use in multidimensional problems. However, there are ways to address your concern - take a look at http://en.wikipedia.org/wiki/Halton_sequence and http://en.wikipedia.org/wiki/Sparse_grid.

Answer 5

Sure it does; however it comes with much larger CPU usage. The problem increases especially in many dimensions, where grids become effectively unusable.