Constant from randomness

Numbers produced with some probability (e.g. the numbers produced by the toss of a single die) are sometimes called random numbers. Here we are going to use random numbers to find the value of a specific number - the constant pi.

Just as the picture above is a fuzzy picture of pi, our determination of its value using random numbers will be fuzzy as well. That is, the value we get will not be exactly pi, but it will be close. And the more random numbers we get, the closer our value will get to the constant pi!

What is pi?

Good question.

The ratio of the circumference of a circle to its diameter is the same no matter what the size of the circle - the ratio is a constant. While this fact has been known since ancient times, the value of the constant ratio cannot be determined exactly because it is not expressible as the ratio of two integers - it is not a rational number. This irrational number is so important in the mathematical sciences that it has a name, pi.

Determination of the value of pi has a long history (see St. Andrews' history of Mathematics site ). Archimedes (287-212 BCE), for example, was able to bound pi between 223/71 and 22/7 by using the following geometric argument.

If one starts with a circle of diameter 1, the circumference or perimeter of that circle is exactly pi units in length. A regular polygon drawn to contain that circle as shown in blue in the following figure has a larger perimeter than the circle. Similarly the regular polygon shown in red is contained by the circle and so has a smaller perimeter.

Pi-bounds

Because the perimeter of the circle is pi, the value of pi lies between the perimeters of the red and the blue polygons. The perimeters of some regular polygons (e.g. those having 3 * n sides) are relatively easy to determine via trigonometry. Instead of hexagons (6-sided regular polygons), Archimedes used 96-sided regular polygons to arrive at his bounds.

Random numbers used to estimate pi.

Here, we will take a similarly geometric approach but one based on the area of a circle rather than its perimeter. Most surprising, perhaps, is that we will use random numbers (pseudo-random actually since they are produced deterministically by a computer) to produce a rational estimate of the irrational constant pi!

If we have a circle of radius 1, then its area is pi * 1 * 1. If we take a quarter of that circle, it will have area pi/4. A unit square can be drawn around the quarter circle so as to completely contain it and the ratio of the area of the quarter circle to that of the unit square will be pi/4. This ratio is constant no matter what the radius of the quarter circle - the square containing it has side = radius.

So if we knew the area of a quarter circle and that of the box which contains it, then the ratio would only have to be multiplied by 4 to get an estimate of pi.

Pardon the pun but this reasoning seems circular in the extreme! After all if we knew the area of a quarter unit circle, we would know the area of the unit circle and hence the value of pi! We seem to be no further ahead.

The way out of this is through probability. If we were to randomly generate points distributed uniformly within the enclosing box, the proportion of points so generated which would also be within the quarter circle would be about pi/4 (on average). Multiplying by 4 gives an estimate of pi!

Estimation of pi is shown via the following Quicktime animation. Use the controls to animate the movie.

Of course, because the positions of the points are selected at random, the estimated value of pi changes as the points are simulated.

At the end of 100,000 simulated point positions, we have an estimate of pi. Of course, every time we conduct a new simulation we get another collection of points and so a different estimate of pi.

Here's a different simulation of 100,000 points (you might want to move the control manually to get to the end of the simulation more quickly.

And another simulation of 100,000 points:

And again:

Many such simulations were done and the final estimate of pi each one produced recorded. The histogram below shows the distribution of the estimates.

histogram of estimates of pi As can be seen there are some low estimates of pi and some high ones, but the average of even these few seems about right. If we were able to conduct an infinite number of truly random simulations, then the average (called the mathematical expectation of this pi estimator) would in fact be exactly the true value of pi!

Though not identical to one another, the histogram does seem to indicate that the estimates are not that different from one another. One measure of how different they are is called the mathematical variance of the estimator. Roughly speaking this is the average squared difference between each estimate and the average of the estimates.

Were we to use 1,000,000 simulated points rather than 100,000 for each estimate, this variance would decrease by a factor of 10.

Finally, the estimated values are not spread out uniformly about the average but seem to concentrate about the true value. It is often the case that estimates which are essentially averages (like the pi estimate used here) seem to concentrate in such a way that the histogram has a bell-shape called a "normal curve".

This means of estimating pi is not very good as it seems to produce estimates (for 100,000 points) which agree with the true value only to a very few decimal places. The number of points which must be generated for each simulation to ensure agreement to a large number of decimal places is huge.

Of course the method is very crude. To compare to Archimedes, it is as if Archimedes used a square as the regular polygon to bound pi. A fairer comparison would be to replace the quarter circle or 1/4 circle by a 1/k circle and the enclosing square by a segment of the regular k-sided polygon which would enclose the circle.

Think about it.

Pi is an irrational number so it cannot be expressed as the ratio of two natural numbers. It is a constant; there is nothing random about it.

Yet ... a sequence of random rational numbers can be used to produce ever better estimates of the value of pi. In the limit, they produce pi exactly.

Now that's interesting.

Buffon's needle

Using random processes to estimate pi also has a long history dating back at least to 1777. At that time the Comte de Buffon pointed out that pi could be estimated by dropping a needle many times on plank floor and observing the number of times the needle landed across a crack! Try an internet search for "Buffon's needle" and you should find several sites that provide discussion and demonstrations of the Comte's proposal!

Notes on the demonstration:

While the animation is paced so as to provide some time for thought on what's going on, by using the video controls available, the student/instructor can proceed through the demonstration at their own pace.
The quantitative analysis environment called Quail was used to produce these dynamic graphics.

Author: R.W. Oldford December 2001.