# Why use Monte Carlo method instead of a simple grid?

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?

-

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.

-
+1 This reply shines because it offers quantitative reasoning in its support. –  whuber Nov 18 '11 at 16:49

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

-

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.

-
Could you explain why points lying on the same hyperplane do not contribute "extra information" about an integral? I am picturing a generic situation in which the domain of a measurable real-valued function on $\mathbb{R}^n$ is sampled and the integral of $f$ is estimated by the mean of $f$ on the samples. I cannot see any reason in general why such an $f$ couldn't vary substantially on all hyperplanes intersecting its domain. Perhaps you are thinking of Monte Carlo simulation in a different sense? –  whuber Nov 18 '11 at 16:48