Lecture 12: Monte Carlo Integration (52)
brandonlouie

Here is another really great resource on sampling from a distribution given its PDF: http://prob140.org/textbook/content/Chapter_16/03_Simulation_via_the_CDF.html

This resource gives a more formal proof on the "inversion method" and helps with giving intuition on what's happening. We are effectively using a Uniform(0,1) distribution as a random number generator, then applying the inverse of our CDF to randomly generated values to find the corresponding sample from our distribution of interest

adam2451

In applications, how would we go about integrating the integrals required. I assume this is done numerically. Does this limit the types of things we can model?

SudhanvaKulkarni123

Another method that one can use would be rejection sampling. Inversion sampling can often be hard for algebraically complicated distributions. In such a case, one can use rejection sampling - which is often less efficient but easier to implement. It works on any distribution. One can check the wiki for a more detailed description. But the idea is essentially, we generate a random variable from a reference distribution and return only certain generated samples in order to approximate our target distribution.

zeddybot

It's cool that since the CDF is always an increasing function, we don't need to compute its inverse necessarily. We can use binary search to find the x value that corresponds to a particular choice of y. You can choose the tolerance on your binary search to tune how much error you allow to come from any given random sample.

stephanie-fu

I can imagine some efficient implementations of this CDF search that cache previously-found values to help with faster retrieval for future values of eta.

You must be enrolled in the course to comment