Monte Carlo Calculation of Pi

Original notebook: monte_carlo_pi.ipynb

Goals

Monte Carlo (MC) methods constitute a large category of computational algorithms and techniques, which rely on random number sampling to solve problems numerically. In this notebook we introduce the Monte Carlo method via a simple simulation used to calculate the value of Pi.
Understand the concept of the Monte Carlo method.
Learn how to calculate the value of Pi via Monte Carlo simulation.
Familiarize yourself with the Quasi-Monte Carlo method.
Appreciate the effect of the number of samples on the accuracy of the results of MC calculations.

Background theory

Tasks and exercises

What is meant by a uniformly distributed random number?

Solution
If a discrete random number $x$ is distributed according to the uniform distribution, $x \sim \mathcal{U}\{a,b\}$ , this means that the probability of $x$ taking on an integer value between the two integers $a$ and $b$ (both inclusive) is simply $1/n$ where $b-a+1=n$ . For example, if $b=5$ and $a=2$ , then $x$ may assume the values 2,3,4,5, each with probability $\frac{1}{5-2+1}=1/4$ . In the case that $x$ is continuous, uniformly distributed takes on an analogous meaning. Now however, we must talk of $x$ assuming a value in some range $dx$ . Then “x is continuously, uniformly distributed on the interval $(a,b)$ , means that the probability of finding $x$ in some range $(x_0,x_0+dx)$ in that interval is simply $\frac{dx}{b-a}$ . In other words, there is a uniform probability of finding $x$ at any point within the interval $(a,b)$ .
In this notebook, we are using pseudorandom numbers. Why is it that the generated numbers we use are not true random numbers?

Solution
In computational science, “random” numbers are generated by some algorithm. Ultimately, such algorithms are intrinsically deterministic: after having specified an input to the algorithm, referred to as a seed, the sequence of generated “random” numbers is fully determined. This seed is typically chosen in a way so as to try and introduce as much randomness into the simulation in possible. Examples include the current time, or physical quantities which possess some inherent noise like temperature, etc. So, in summary, we cannot have a truly random number generator for this notebook.
How could one obtain a better estimate for the value of Pi from the simulation?

Solution
The accuracy of the simulation largely depends on the quality of the random numbers employed and the total number of samples used in the computation. Using the quasi-random number approach can improve the quality of the random numbers and thus convergence of the calculation. On the other hand, one can also improve the accuracy of the result by increasing the number of samples generated. Of course, the latter implies that longer simulation times shall be necessary and thus we have a time-accuracy trade-off.

Interactive visualization

Monte Carlo calculation of π

Number of inside coins:

Number of outside coins:

Quasi-Monte Carlo

Number of coins100

Legend

(How to use the interactive visualization)

The left panel shows the simulated square referred to in the theory notebook. The light blue area shows the quarter circle. When the coin is dropped inside the circle, it will show up as a blue dot in the figure. Otherwise, it is indicated by a red dot. The right panel shows the calculated value of Pi as a function of the number of dropped coins.

You can choose how many coins to drop at each time from the slider. Use the Quasi-Monte Carlo method (using quasi-random numbers) by ticking the checkbox. The “Throw” button is used to throw the coins into the square. You can clear the simulation by clicking the “Clear” button.