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 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.
EXERCISE 2: 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 simple way of quantifying consistency is to consider the relative difference between the smallest and largest results. That is, take the difference between the largest and smallest results, then divide by the smallest result. For example, suppose you conducted 4 experiments with results 60, 70, 75, and 68. The smallest result is 60 and the largest is 75. Their relative difference is (75-60)/60 = 15/60 = 0.25= 25%. What is the relative difference between the smallest and largest numbers from your 10 experiments (EXERCISE 1)? You may use a calculator or spreadsheet if you wish.
EXERCISE 3: 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 (EXERCISE 1)?
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. This general idea, that more experiments lead to more accurate results, is captured by the mathematical Law of Large Numbers. Technically, the Law of Large Numbers states that as the number of experiments approaches infinity, the experimental results will converge on the expected value.
EXERCISE 4: Perform 10 experiments with 1,000 random darts and list the results. Are the numbers you obtained more or less consistent than your experiments involving 100 darts (using the same relative difference measure as in EXERCISE 2)? What is the average of the 10 results?
EXERCISE 5: Perform 10 experiments with 10,000 random darts and list the results. Are the numbers you obtained more or less consistent than your experiments involving 1,000 darts (using the same relative difference measure as in EXERCISES 2 and 4)? What is the average of the 10 results?
It is worth noting that position of each dart within the square is completely random. As a result, it is possible that the same position might be randomly selected more than once. You wouldn't see it in the display, as the same red or white pixel would just be displayed on top of the old one. However, we can conduct an experiment to confirm this. 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 we threw 160,000 darts at the board and some points were still not hit, that would prove that some were hit more than once.
EXERCISE 6: To confirm that duplicate positions are being selected, throw 160,000 darts. Are there any points within the square that are not hit (meaning some are hit more than once)? If you increase the number of darts by a factor of 10, up to 1.6 million darts, is that enough darts to cover all of the points in the square? If not, that would imply that some points are getting hit more than 10 times while others are not hit at all!
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 7: Using the average result from your experiments involving 100 darts (EXERCISE 3), calculate an approximation of π. How accurate is the approximation compared to the actual value of π (3.141592653...)?
EXERCISE 8: Using the average result from your experiments involving 1,000 darts (EXERCISE 4), calculate an approximation of π. Is the approximation more or less accurate than the one made using 100 darts?
EXERCISE 9: Using the average result from your experiments involving 10,000 darts (EXERCISE 5), calculate an approximation of π. Is the approximation more or less accurate than the one made using 1,000 darts?
EXERCISE 10: Perform a single experiment with one million darts. This might take a few seconds, so be patient. List the number of darts inside the circle and use that number to calculate an approximation of π. The Law of Large Numbers would suggest that this would be the most accurate approximation. Is that the case?
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 11: Use the Web page to perform repeated simulations of needle drops and list your numbers. Are needle drops more or less consistent than darts? That is, if you perform ten trials of 100 needles, are the numbers of needles crossing lines more or less consistent than throwing 100 darts (using the same relative difference measure as in EXERCISE 2)? How about repeated trials of 1,000 needles vs. 1,000 darts (EXERCISE 4)? 10,000 needles vs. 10,000 darts (EXCERCISE 5)? Show your data.
EXERCISE 12: According to Buffon's formula, π ≈ (total number of needles)/(number of needles that cross lines). Using this formula and your numbers from above, calculate approximations of π using averages from 100 needles, 1,000 needles, and 10,000 needles (EXERCISE 11). Are these approximations more or less accurate than the corresponding approximations using darts (EXERCISES 7-9)? Show your calculations.
EXERCISE 13: Perform a single experiment with one million random needles and list the number of needles crossing lines. Use this number to approximate π. Is the approximation more or less accurate than the approximation using one million darts (EXERCISE 10)?
For the last part of the lab, you will need to do some research about Monte Carlo methods. When answering questions such as these, you must provide a reference to the source of your answer. If the source is a Web page, be sure to list the specific Web address for the page that contained the information. When using the Web to answer a factual question, such as the first question below, provide two independent sources (since Web pages are not always reliable).
EXERCISE 14:
- 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.