The tree.
In this post I will look at a new variant of an old way of approximating pi using random numbers, a so-called “Monte Carlo” method. Yes, Monte Carlo as in the casino.
There is another way of doing this simulation using darts => link and even more different method called “Count Buffons needle” => link. In this post I wanted to change it up a bit, because others have already used the darts analogy and it is nice to do something in a little different way.
Background
I was at my summer-house this week and thought that using the idea of an apple tree would make the core idea of the Monte Carlo method even more clear and we can all eat apple pi(e) afterwards. By the way,
The classic way of calculating
Tree with square.
Make like a tree and get outta here
Question: Why not show the idea using the darts idea, isn’t darts good enough for you? Well, I wanted something different and I thought that the idea of throwing darts is not random. A person throwing darts will never achieve a completely random distribution, because that is not the goal of darts, so using darts to explain the idea is not perfect because uniformly random distribution of points is the most important idea in this simulation. Instead, using apples that are dropped from a height is almost as random as it gets, it feels more like Monte Carlo.
Besides, a apple tree is very common, we associate it with Newton and apple pie. We can also instead of counting the number of apples, we can actually weigh them. The answer will be the same and there are usually lots of them, as opposed to darts.
Food for thought
We begin by placing a square plastic sheet under the tree, so the sheet is just inscribed in the shadow of the tree (if the sun is above the tree). We ignore that the tree has a stem, the calculations will be different, but by argument we can see that the result will be the same.
Tree with the fallen apples.
Imagine we gently shake the tree, the apples will land on the sheet. When we are finished, the sheet is weighed and recorded and the other apples are also weighed. That’s it, this is all we need to do. How is this approximating
The math
The disc and the square.
We define the radius of the disc and the side of the square with r and d respectively. Using Pythagoras’ theorem, we can get the side of the square, d, expressed as r. For simplicity, say d = 2k. We then have
We define the area of the shadow of the tree as
So if we let r=1 then
– The ratio of the areas are the same as the ratio of the number of apples in the areas. If the area is twice as large, then we will have twice as many apples. The problem is that we need many apples. Millions of them. This is why I use a Matlab script to do it for me.
The coding
We need to randomly place points on a disc. In the dart version we generate random points in a square and find how many points are within a inscribed circle, this is trivial. In this version it is the opposite, which presents an interesting problem.
To generate the random points we can simply use polar coordinates. The problem with this is that the number of points are not evenly distributed over the disk. To convince ourselves, we can plot the density by counting the number of points within a radius r for a couple of points.
Distribution of points over disc.
The reason the points are denser in the center of the disk is a known problem and the solution is to map the radius to
r = 2*rand(n, 1); r = sqrt(r); %mapping to uniform distributed samples theta = 2*pi*rand(n, 1); x = r.*cos(theta); y = r.*sin(theta); %pick out the points on the square mask = abs(x) < 1 & abs(y) < 1; xs = x(mask); ys = y(mask);
The variable mask is a binary vector, where the ones are the points within the square and the zeroes are the points outside. By using the number of points to approximate the area, we can use the equation of
Convergence.
An interesting part of my version is that we can use physical apples and weigh them instead of counting them, if we would like. The weight doesn’t add anything to the ratio. In fact, if you try this at home, you just need a couple of thousand apples to get a good approximation of
As we can see, the approximation is converging very slowly. It takes about a million apples to get only three decimals. This is about the same as the dart version.
How do you like those apples?
We used a new variant of an old Monte Carlo simulation to approximate
Apple pi(e).
Illustrated, conceived and written by Matz JB 2014