A pi-pie named Monte Carlo

A lively community of people including students, researchers and tinkerers from Marseille (France) celebrate the so-called "π-day" on the 3rd month, 14th day of each year. A nice occasion for general talks on mathematics and society in a lively athmosphere and of course to ... a pie contest!

I participated last year (in 2016) with a pie called "Monte Carlo". Herein, I give the recipe by giving some clues on its design... This page is a notebook - meaning that you can download it and re-run the analysis I do here at home (and most importantly comment or modify it and correct potential bugs...).

Let's first initialize the notebook:

The pie looked like this:

the recipe¶

The global design of the pie was to start from its round shape ...

and to trace the biggest square inside it. To do that, you do not need anything special, but to draw the diagonals on the cardinals:

and finally to join their extremities to get this square:

Note something : the disk within the blue circle has a diameter of $2$, thus its surface is equal to $\pi$. The green square is composed of $4$ isocele rectangular triangles which can be shuffled to be reorganized in two unit squares: its surface is thus equal to $2$. Equivalently, the edge length is $\sqrt 2 $ (because it is the hypothenuse of the unit square and by Pythagoras' theorem its length is $\sqrt{1^2 + 1^2}$) such that we verify that the surface is $2$.

Let's now take a bunch (let's say $22$) of smarties (©) and let's throw them all at random on the pie. (Say that if one falls outside , you do not eat it but throw it again until it lands on the pie.)

It's ready! We have our finished pie with the square and the smarties.

Monte Carlo?¶

Now, why "Monte Carlo"? Because it is a city in southern France which is well known for casinos, where randomness rules the game (most often is favor of the owners of the casino, but this is another story). As a consequence, mathematicians used this term (jokingly) to designate a method that will use randomness to compute results. This is in particular much used to compute surfaces, which bear the name of "integrals" (their symbol being $\int$) in mathematics. They have many practical uses in mathematics and physics and the variables are often in very high dimensional spaces, but for now we will land back to the 2D space of our pie...

Indeed, what is the relationship with our pie?

First, let's note that it's easy to count the number of smarties that are in the square:

We have thrown the smarties at random: their probability to land anywhere on the pie is uniform. As a consequence, their probability to land inside the square is the ratio between the respective surfaces of the square and the circle, that is, $\frac{2}{\pi}\approx 63\%$. Let's see what this gives:

pretty close! But we also get something fun: the relative number of smarties (hence the name "smarts" [ref. needed]) may give an approximation of $\pi$ as

$$ \pi \approx 2 * \frac {N}{n} $$

where $N$ is the total number of smarties and $n$ the number of smarties in the square. I found that the possibility of approximating such a highly respected number as π simply by using randomness and a pie a good enough reason to submit my recipe to the contest...

Let's now see what our particular pie (which can be considered as one instance of a Monte Carlo experiment):

GREAT! We get an estimate of the order of $0.04 \%$!

a quantitative evaluation¶

We may summarize our method and evaluate it for arbitrary numbers of smarties:

Let's now see what this method gives with 10, 100, ..., one million smarties (what a pie!):

We see that our estimate gets better, the bias gets lower. How variable is the algorithm?

When we do not have as many smarties, one can repeat the experiment many times. To do this we use an important aspect of random number generators: they are pseudo-random. Indeed, such functions most often give by default completely different sequences of numbers, but one has the possibility of generating the same sequence (of random numbers) if one specifies the "seed", that is a number which intializes the number genrator. As such one says that the generated sequence is pseudo-random (because it can be guessed if and only if one knows the seed), or also that it is frozen. Here, we simply use the seed to generate different sequences in a reproducible way:

But what? The method is very fine for some seeds, but not for other... How come and what do we learn from that observation?

Let's imagine $N=1000$ and let's do many ($10000$) repetitions of our estimate:

We can thus draw an histogram, that is, a diagram showing the number of values obtained by independent repetitions of our method:

This is often occuring in science: Imagine you try to find an unknown value (in machine learning terminology, this is a hidden or latent variable), and that is here $\pi$, but you have an approximate measurement (our Monte Carlo algorithm, a device that sometimes fails, a telescope which looks at a faint, very far away light source, a neuron that fires in an unpredictive way, ...). Evaluating this variability is therefore essential in the scientific process and (instead of being thrown under the carpet) should be assessed explictly.

Luckily, mathematics provides some useful tools and we will just explore some examples of them. First, you may have recognized the shape of the histogram, it is a Gaussian (or normal, or bell-shaped) distribution characterized by only two parameters (what statisticians call the 2 first moments):

This result is the consequence of an ubiquitous theorem : the central limit theorem. The latter states that whenever you collect values which are noisy around a mean value and that this level of variability (given by the standard deviation) is constant, then the distribution is Gaussian.

It also states an important result: whenever you increase the number of samples you take (that is, in our case the number of smarties), the mean and standard deviation are always similar but their precision get better with respect to the true value:

In particular, this shows that the squared root of the error scales with the square root of the number of smarties. As such, one important value is to consider the precision as the inverse of the squared standard deviation (that is of the variance) as it scales linearly with the number of trials.

Just remember the hierarchy of our procedure:

• we test our distributions at different levels
• for each level, we make different trials,
• for each trial, we make a pie with many smarties and count the ones in the squares.

Yet, it only takes some seconds on the computer - hence the popularity of the method nowadays.

As a consequence, scientists use some caution whenever they get a result. Any inferred value is most often given within a confidence interval, for instance by giving:

• the median value of the different repetitions (that is the value that corresponds to that where half of the other values are below and the other half above),
• the confidence interval as the values around the median correponding to 95% of the cases

The journey is almost over: from a pie, we devised an algorithm in the form of a recipe to compute the value of π. Then we observed that the result of our recipe varied, but that we could use some mathematical tools to quantify this variablity. We now know that π is around $3.15$ and almost surely between $3.05$ and $3.25$. Nice.

the elephant in the room¶

But wait... This result is at stake with the result we got in our $22$-smarties pie for which we triumphed with an estimate of the order of $0.04 \%$! This is far, far better than the result we got with $10000$ of $1000$-smarties-pies... What happened?

Above we saw that the results depended on the instance of how we chose to seed the random number generator:

and if we make many of these experiments, this is what we get:

We can thus draw an histogram, that is, a diagram showing the number of values obtained by independent repetitions of our method:

Since, we use a small number of smarties, the estimate can take only a small number of values : the distribution still has a gaussian envelope, but is non-null only for certain values. Among these values, the one which is the most probable is the value which gives for an approximation of π:

This approximation of π is known from a long time [ref needed], and two questions arise:

• did the cook lie?
• why is that approximation so good?

For the first question, you can answer quite easily. Either the cook cheated and placed 7 smarties outside the square on purpose, or he did not cheat

Pretty high, and I must admit this was the case... It teaches us also to be cautious whenever we hear about some (too) extraordianry scientific results - especially if it has not been carefully designed to avoid such biases. Our bias here is that the cook new that $22$ may give a good estimate.

This leads to a second question, why 22 and not 42? A priori, there is no reason that one approximation of π should be better than any other. Let's see the error when we change the denominator:

$$ \pi \approx \frac n d $$

such that $$ n = I( \pi \cdot d) $$ where $I(x)$ is the integer value of $x$.

Let's plot the error as a function of the denominator

Interestingly, the envelope of this curve (the error with respect to the denominator) follows a decreasing trend: this was to be expected when we think again at the central limit theorem: as the denominator increases, the precision increases. We have shown this in the plot above by showing the $1/d$ line, which is a straight line in this plot, because we used log scales on both axis.

Compared to this baseline, what is more surprising is that the error decreases, then makes a "spike" then goes back to baseline. The first spike lies at 7 and for the 16 next repetitions:

The fact that we see a repetition of same pattern is to be expected as it is the same approximation scaled by an integer:

$$ \frac {22} {7} = \frac {22*2} {7*2} =\frac {44} {14} = \frac {22*3} {7*3} = \frac {66} {21} = \ldots $$

In retrospect, the shape before the spike can be understood as the error quite smoothly approaches the 22 / 7 approximation (green line):