1
$\begingroup$

(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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks! But what is the case for my question, is it a false or true statement that random variables act as a "tool/mechanism" for us to be able to create multiple iterations (to measure and average) of an otherwise deterministic experiment? $\endgroup$
    – litmus
    Commented Dec 27, 2021 at 13:39
  • $\begingroup$ I edited my main question to hopefully make it less vague. Your answer helped, but I am looking at understanding on a micro level (the work/effect of each random variable) rather than the aggregated macro level (averages / LLN).. $\endgroup$
    – litmus
    Commented Dec 27, 2021 at 13:59
  • 1
    $\begingroup$ micro and macro effects work together: both the macro effect (the signal) and the micro effect (the noise) increase with each iteration; what matters is that the signal-to-noise ratio goes up. $\endgroup$
    – Carlo Beenakker
    Commented Dec 27, 2021 at 14:31
  • $\begingroup$ Ok, this is really helpful, thanks! I have looked at Signal-to-Noise in wiki but cant understand how uncertainty is increased by sqrt(N). Does this relation have a specific name? Any article or term you would recommend where I can use to find more info? $\endgroup$
    – litmus
    Commented Dec 28, 2021 at 9:23
  • 1
    $\begingroup$ "uncertainty" is the root-mean-square deviation = square root of the variance; the variance increases linearly with the number $N$ of (independent) iterations, hence the $\sqrt N$ increase of the uncertainty $\endgroup$
    – Carlo Beenakker
    Commented Dec 28, 2021 at 9:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .