---

Monte Carlo Methods

• Wikipedia

Monte Carlo methods are a broad class of computational algorithms based on repeated random sampling.

Monte Carlo methods are mainly used in three distinct problem classes:

• Optimization
• Numerical integration
• Pseudo-random number sampling

Monte Carlo methods vary, but tend to follow a particular pattern:

1. Define a domain of possible inputs.
2. Generate inputs randomly from a probability distribution over the domain.
3. Perform a deterministic computation of the outputs.
4. Aggregate the results.

Computational costs: in general the method requires many samples to get a good approximation, which may incur an arbitrarily large total runtime if the processing time of a single sample is high. However since the “embarassingly parallel” nature of the algorithm allows this large cost to be reduced through parallel computing strategies in local processors, clusters, cloud computing, GPU, FPGA, etc.

Explain estimating Pi with Monte Carlo methods

Consider a square target with a circle perfectly inscribed inside it with a radius , the side length of the square , the area of the circle is and the area of the square is .

To find we look at the ratio of the areas:

By rearrrearranging this formula, we can isolate :

In practice:

1. Generate coordinates: generate random pairs of numbers between and .
2. Check for hits: for each point calculate its distance from the center using the Pythagorean theorem: , if then the shot landed inside the circle
3. Calculate after throwing shots, multiply the fraction of hits by .

The following is a toy simulation made with Manim: