26
$\begingroup$

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?

$\endgroup$
29
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ +1 This reply shines because it offers quantitative reasoning in its support. $\endgroup$ – whuber Nov 18 '11 at 16:49
11
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
-2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – whuber Nov 18 '11 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.