Mathematical Foundations of Monte Carlo Methods

Mathematical Foundations of Monte Carlo Methods(scratchapixel.com)

93 points by poindontcare 4 years ago | 8 comments

Spivakov 4 years ago |

An informal perspective on some implication of Monte Carlo on integral:

One of the most intuitive (and used in applications) definition of being integrable is Riemann integral based on the geometric idea that you can compute the area/volume by dividing region into pieces and summing them all up. Now you can (mathematically) prove that for any such integrable function, its integral can be approximated by Monte Carlo and the results are consistent.

Now what about the other direction? You can theoretically run Monte Carlo approx on wildly zigzag functions that does not make any geometry sense (i.e. not Riemann integrable), if the "probability" in the space is well-defined. The idea that uses probability, instead of geometry, turns out to give a broader class of integrable objects.

One interesting observation is that these ideas are intuitive and meaningful if put informally. But when you formally look into these ideas (integration/measure theory) it suddenly collapses into lines of terse mathematical constructs.

l33t2328 4 years ago | |

You’re certainly aware of this, but for those that aren’t: asking that the “probability” in the space to be well defined you are essentially invoking the idea that the function is _measurable_. Measure is a way to generalize things like length and volume to sets which have no length or volume in the traditional sense. One good way to do this is say that lines have “measure” equal to their length, and if you can combine line segments(even infinitely many) to get some new line then that line has measure as well. If you do make this precise, you get the so-called “Borel measure” on the real line.

If you want all subsets of sets with 0 Borel measure to also have 0 measure, then this leads to the notion of the lebesgue measure, and it can be used to define the lebesgue integral.

pfortuny 4 years ago | | |

Two insights more

a) But for probability you nees the measure of the whole space to be 1, which forces points “far away” to have very small “weight”. Thus, there is no uniform distribution in the whole R.

b) and then your mind blows up when you realize that discrete probability is the very same thing, and that an integral in a finite set is just summation.

ronald_raygun 4 years ago | |

Yeah to add to this when you study probability at a more advanced level, you learn that really what a probability is "just" an integral ie P(x) = integral{Indicator function(X)}. So it's actually not a crazy object to pop up when you're thinking about integrals and integral approximations.

it 4 years ago |

Here's an alternative for Bayesians: http://georglsm.r-forge.r-project.org/site-projects/pdf/7113...

arc-in-space 4 years ago |

When I was beginning to study path tracing I've learned to avoid this domain, the presentation always seems so friendly but the actual material is unfortunately much too barebones

johnnyanmac 4 years ago | |

really? I found it to be an invaluable source for understanding the mathematics behind some fundamental computer graphics topics. But I'm also bad at math, so the diagrams helped a lot for me to visualize all the calculus discussed. It's "beginner friendly" but for advanced topics, which is a rarity. There's still a huge gap between reading this and then picking up a SIGGRAPH paper to implement, but that's an industry wide issue.

My only reservation was that it updated at a glacial pace for topics I really wanted. I was waiting for volume rendering 4 years ago, and it looks like they started making articles last month. But I can't really complain about updates to completely free resources.

reverses 4 years ago | | |

In the reverse, some days ago somebody wrote that also '77777' may be the result as a randomly generated number, think about somebody asking for 'your lucky number?' and all the other people (probabilly thought in/told numbers from 1 to XX), some choose the same numbers and you are the only one answering: 'ma lucky number's 37289!' and all the people around are watching you saying: 'hu?' So saying that a number may be perceived as random ^^ ...may be valid in terms of your topic 'computer-graphics' (for what people see -or even think they do ?!) (-;

Have a nice weekend, regards...