Introduction to Monte Carlo simulation

Monte Carlo simulation is a computerized mathematical technique that relys on repeated random sampling to obtain numerical results. It is used to model the probability of different outcomes in a process which is impractical or impossible to solve analytically. The modern version of this technique was first used to work on nuclear weapons projects. It is named after the Monte Carlo Casino in Monaco. The technique is used by professionals to tackle a wide range of fields such as finance, insurance, manufacturing, engineering, transportation, and science. Due to the increasing availability and affordability of powerful computational engines, Monte Carlo methods have become an increasingly popular tool for conducting simulations.

Approximation of the Value of 𝛑

Monte Carlo method can be used to estimate the value of 𝛑. Consider a quadrant inscribed in a unit square, where a large number of uniformly distributed random points are generated and sampled. If the point falls within the circle, it is colored blue, otherwise it is colored red. We keep track of the number of points inside the circle and the total number of points. The approximation of the ratio of the areas is 𝛑/4.

Buffon’s Needle Problem

Buffon’s needle problem can also be used to design a Monte Carlo method to estimate 𝛑. Suppose we have a floor made of an infinite number of parallel, equidistant lines, a width d apart. We now toss a needle of length l < d onto the floor. The probability that the needle will lie across a line on the floor is

We can conduct a Monte Carlo simulation of a large number of tossed needles to predict the probability that a needle intersects a line on the floor.

Monte Carlo Integration

Monte Carlo simulations, can estimate the area of irregular geometrical figures that may be difficult to compute using standard analytic geometric methods. In light of fundamental theorem of calculus, the function f(x) from a to b can be numerically integrated as follows:

Alternatively, we can also calculate this definite integral by Monte Carlo algorithm. The random points can be obtained by producing uniformly distributed numbers in the interval [a, b]. As the number of samples N increases, the average of f(x) can be estimated. Therefore, the area under the irregular curve can be approximated by the area of the the rectangle with the heigh of the average of f(x), which is defined as the Monte Carlo estimator:

It can be verified that the expected value of this estimator is equal to the desired integral F.

where p(x) is the probability density function (PDF).

Importance sampling

Importance sampling is a general technique for estimating the properties of a distribution by drawing samples from an alternative distribution. When the PDF of the samples is not uniformly distributed, we can extend Monte Carlo integration to random variables with arbitry PDFs. Therefore, we can oversample the important region of the distribution to make the simulations converge much faster. The theory behind importance sampling boils down to the following result.

where p(x) is the PDF of the target distribution, q(x) is the PDF of the importance distribution, and the fraction p(x)/q(x) is the importance weight.