Monte Carlo Methods – Intuition of the Work Done by Random Variables in Monte Carlo Methods

intuitionpr.probabilitysampling

(I've tried Math SE, but have so far come up empty handed, so I'm trying my luck here.)

I would like to get a better intuitive understanding of why Monte Carlo works so well in approximating a solution to complex problems, such as calculating irrational numbers or the Particle Filter / Monte Carlo Localization to interpret noisy data from a sensor for instance. I have restated my question in two parts.

Part 1: One of the key's to random sampling is that the random sample will reflect the characteristics of the population from which it is drawn. So when we approximate Pi by defining an area with a circle-quadrant within a square box and let random samples inside vs. outside the quadrant approach the ratio of Pi, are we in essence re-sampling our "deterministicly" defined circle-quadrant and box, using random variables as a mechanism to be able to re-sample the pre-defined areas over and over again?

Part 2: My question stated differently with Monte Carlo Localization (MCL); if I understand correctly, we first scatter random particles (our random sampling/"hypotheses") across our map and then attach larger weight to the particles that overlap/match with our noisy sensor readings as more important. We then repeat to do a new re-sampling. Are the random variables here used as a "fair" measurement mechanism to allow the obscured truth hidden in our noisy sensor reading to be re-sampled so that we approach a cleaner approximate sensor-reading/localization?

[Edit] So in summary, are the random variables here acting as a tool/mechanism for us to be able to create multiple observations of an otherwise deterministic experiment? And if so, at each iteration which we are observing and measuring, how does this avoid simply adding random noise to the data?

Or is there a better way to view the work the random variables do here?

Also, if appropriate, any recommended further reading (including books/papers) that you think can help with the intuition in this mechanism is much appreciated!

Best Answer

Q: Are random variables acting as a tool for us to be able to create multiple iterations (to measure and average) of an otherwise deterministic experiment?

A: An answer has two ingredients:

  • firstly, many deterministic questions can be formulated as asking for the expectation of a random variable. For example, the integral $\int_a^b f(x)dx$ is the expectation of $(b-a)f(x)$ for a random variable $x$ which is uniformly distributed in the interval $(a,b)$.
  • secondly, the law of large numbers allows us to approximate the expectation by random sampling.

This is the essence of the Monte Carlo method. A further refinement could then be to reduce the variance of the estimator (importance sampling).

Q: Follow-up question: Why doesn't each iteration simply add random noise to the data?

A: After $N$ iterations, the signal has increased by a factor $N$, while the uncertainty due to the noise has increased by a factor $\sqrt N$, hence the relative uncertainty, which is what matters for the expectation, decays as $1/\sqrt N$.

Related Question