Name: _________________________________________
It may surprise you to learn that random events such as coin flips, dice rolls, and roulette wheel spins are central to many computer science applications, such as cryptography and database management. While events such as these are random in nature, their behavior over the long run is predictable and so can be used to construct deterministic solutions to complex problems. Problem solutions that use such random events are known as Monte Carlo methods, named after the city famous for its casinos. In this lab, you will use related Monte Carlo methods to approximate the value of π.
Our first approach to approximating π will involve estimating the ratio of the area of a circle to the area of the square that circumscribes it (see the picture on the right). This can be accomplished using a Monte Carlo method involving random points.
Think of the square as a dartboard with the a circle inscribed in it. If you threw darts randomly at the board so that each dart is equally likely to land at any point, then the distribution of the darts would allow you to estimate the ratio of the areas of the circle and square. For example, if you threw 500 darts and 400 of them landed inside the circle, then the area of the circle could be estimated as 400/500 = 0.80 = 80% of the area of the square.
The Web page MontePI.html can be
used to simulate the generation of random darts (or points)
within a square, and also keep track of the number of darts that land
inside the inscribed circle. By default, 100 random
darts will be displayed and tallied each time you click on the
button labeled "Click to generate the darts." The number of darts can be changed, however, by entering a
new number in the box above the button.
EXERCISE 1: Load this Web page and perform 10 different experiments. For each experiment, generate 100 random darts and list the number of darts that land inside the circle. Be sure to clear the display and reset the counts (by clicking the button labeled "Clear darts and reset counts") between experiments. List your results below.
Due to the random nature of these experiments, there will no doubt be some variability in your results. In order to arrive at a single answer, a natural approach is to average the results obtained via repeated experiments. What is the average of your results from the 10 experiments? You may use a calculator or spreadsheet if you wish.
How consistent were your results from the 10 different experiments? That is, did you get close to the same count each time, or were there fairly large differences? One formal way of quantifying consistency is to consider the maximum relative difference between any one result and the average of the results. First, find the single result that differs most from the average of the results. Then, take the difference between those two and divide by the average. For example, suppose you conducted 4 experiments with results 60, 80, 75, and 85. The average of these 4 results is 75. The maximum difference between 75 and any one of the results is 15 (i.e., 75-60), and so the maximum relative difference is 15/75 = 0.20 = 20%. What is the maximum relative difference using the numbers from your 10 experiments?
Monte Carlo methods rely on the fact that while the outcome of a single random event cannot be predicted, the distribution of repeated random events often can be. Consider a coin flip, for example. While it is impossible to predict whether a single flip will produce heads or tails, it is extremely likely that given a large number of flips, the number of heads and tails will be approximately the same. Since there are only two possible outcomes of a coin flip, each equally likely, we say that the expected distribution of heads and tails is 50/50.
A key phrase in determining the expected distribution of random events is "given a large number...". It shouldn't surprise you that in the short run, statistical anomalies can occur. For example, if you flipped a coin twice, you might get two heads or two tails as opposed to the expected distribution of one of each. When the number of events is small, such anomalies can greatly skew statistics (based on two flips, we might conclude that the expected distribution is 100% heads!). In the long run, however, anomalies will balance out (e.g., streaks of heads will be counter-balanced by streaks of tails) and the expected distribution will be achieved. The more flips you make, the closer you are likely to come to the expected 50/50 distribution.
EXERCISE 2: Perform 10 experiments with 1,000 random darts and list the results below. What is the average of the 10 results? What is the maximum relative difference, i.e., (maximum distance from average)/average? Are the numbers you obtained more or less consistent than your experiments involving 100 darts? What would you expect? Explain your answers.
EXERCISE 3: Perform 10 experiments with 10,000 random darts and list the results below. What is the average of the 10 results? What is the maximum relative difference, i.e., (maximum distance from average)/average? Are the numbers you obtained more or less consistent than your experiments involving 1,000 darts? What would you expect? Explain your answers.
EXERCISE 4: The dartboard in the simulation is 400 pixels high and 400 pixels wide. As a result, there are 160,000 potential points for each dart. If you threw one million darts at random, would you expect every one of those 160,000 points to be hit at least once? Explain your reasoning.
Perform a single experiment with one million random darts to confirm or refute your prediction. Are there any points that were not hit by a dart? Report the result as well as the number of the darts that landed inside the circle?
Using the experimental data from the previous exercises, it is a relatively simple task to approximate π. The formulas for the area of a square (side2) and circle (π*radius2) are taught in high school geometry. In the special case of a circle inscribed in a square, the radius of that circle is (side/2), making its area π*(side/2)2 = π*side2/4. Thus, the ratio of the areas of the inscribed circle and the square is:
(area of inscribed circle/area of square) = (π*side2/4)/side2 = π/4
Solving for π, we see that:
π = 4*(area of inscribed circle/area of square)
Assuming the ratio (darts in circle/total darts) is a reasonable approximation of (area of circle/area of square), we find that:
π ≈ 4*(darts in circle/total darts)
For example, suppose we generated 10,000 random darts, and 8,000 of them landed inside the circle. From that, we can estimate that the area of the circle is 80% of the area of the square, and so π is
approximately 4 * (8,000/10,000) = 4 * .80 = 3.2.
EXERCISE 5: Using the average result from your experiments involving 100 darts (EXERCISE 1), calculate an approximation of π. How accurate is the approximation compared to the actual value of π (3.141592653...)?
EXERCISE 6: Using the average result from your experiments involving 1,000 darts (EXERCISE 2), calculate an approximation of π. Is the approximation more or less accurate than the one made using 100 darts (EXERCISE 5)? What would you expect? Explain your answers.
EXERCISE 7: Using the average result from your experiments involving 10,000 darts (EXERCISE 3), calculate an approximation of π. Is the approximation more or less accurate than the one made using 1,000 darts (EXERCISE 6)? What would you expect? Explain your answers.
EXERCISE 8: Using the number from your experiment involving one million darts (EXERCISE 4), calculate an approximation of π.
A second Monte Carlo method for approximating π was first posed by the 18th-century French mathematician, Georges-Louis Leclerc, Comte de Buffon. Buffon described a floor consisting of evenly spaced planks onto which a needle was dropped. If the needle length is half the width of the planks, it can be proven that the probability of a randomly dropped needle landing on a boundary between two boards is 1/π.
The Web page MontePI.html contains a second simulation for dropping random needles on a floor. By clicking on the button labeled "Click to generate the needles," you can drop needles at random on the floor and the page will keep track of how many cross a line (i.e., the boundaries between the planks).
EXERCISE 9: Use the Web page to perform repeated simulations of needle drops and record your numbers here. Are needle drops more or less consistent than darts? That is, if you perform several trials of 100 needles, are the numbers more or less consistent than throwing 100 darts (EXERCISE 1)? How about repeated trials of 1,000 needles vs. 1,000 darts (EXERCISE 2)? 10,000 needles vs. 10,000 darts (EXCERCISE 3)?
EXERCISE 10: According to Buffon's formula, π ≈ (total number of needles)/(number of needles that cross lines). Using this formula and your numbers from EXERCISE 9, calculate approximations of π using averages from 100 needles, 1,000 needles, and 10,000 needles. Are these approximations more or less accurate than the corresponding approximations using darts (EXERCISES 5-7)?
EXERCISE 11: Perform a single experiment with one million random needles and use the result to approximate π. Is this approximation more or less accurate than the approximation using one million darts (EXERCISE 8)?
For the last part of the lab, you will need to do some research about Monte Carlo methods. When answering these questions, you should include a reference to the source of your answer. Since the Web is not always a reliable source, any factual answer obtained from the Web should be verified with a second source (and the specific Web address of both sources listed).
EXERCISE 12:
- Who is credited with the invention of Monte Carlo methods?
- What connection is there between Monte Carlo methods and the development of the atomic bomb?
- In addition to the simple examples we have discussed in class (and the atomic bomb connection), describe a scientific application of a Monte Carlo method. That is, describe a problem from some field of science in which randomness was used to help solve that problem.