## Monte Carlo Simulation

The Monte Carlo method is any technique of random sampling employed to approximate solutions to quantitative problems. Often the system being simulated is clearly one that involves random processes, as, for example the Random Walk problem, sometimes described as the path a drunk takes as he staggers away from a telephone pole. If he takes N steps, each of length /, and each in a completely random direction, how far will he be from the telephone pole after the N steps? The problem can be solved algebraically (the answer is but it's apparent that a suitable answer can be obtained by using a random number to obtain an angle (the direction of each step relative to the one before), and thus the distance from the start point after each step. Figure 15-10 illustrates the result of such a calculation. Phenomena such as collisions of molecules in a gas, or neutron shielding, can be modeled similarly.

In other examples, the simulation appears little more than a game or diversion, but provides unexpected information. A classic example is the problem called Buffon's Needle, first proposed in 1777. A needle of length I is dropped on a sheet of paper with parallel rulings of spacing D. What is the probability of the needle crossing one of the lines? The surprising result is that the answer provides an estimate of the value of n.

A

K

\

A\

h

À

\

I i\

^tfii I

 10 - ~ ., ,.,.,.,... ^F^Sb^^BfefeTlS 2D

Figure 15-10. Random walk, 2000 steps of length 1. The large diamond symbol is the position at the end of 2000 steps, a distance of 48.9

from the start point at 0,0. The "theoretical" distance /Vat = 44.7. (folder 'Chapter 15 Examples', workbook 'Random Walk', worksheet 'Random Walk')

Figure 15-10. Random walk, 2000 steps of length 1. The large diamond symbol is the position at the end of 2000 steps, a distance of 48.9

from the start point at 0,0. The "theoretical" distance /Vat = 44.7. (folder 'Chapter 15 Examples', workbook 'Random Walk', worksheet 'Random Walk')

We can solve the problem in the following way: (i) generate a random number to calculate an angle 6, (ii) generate two more random numbers to obtain the x and y coordinates of one end of the needle, (iii) from the coordinates of the end, the length I of the needle and the angle 6, calculate the coordinates of the other end of the needle, (iv) use these two pairs of coordinates to determine whether either end of the needle crosses a gridline, (v) repeat the process N times, counting the number of needles that cross a gridline. Figure 15-11 illustrates the situation after 2000 needles of length 1 = 2 have been dropped on a sheet of paper with ruling spacing D = 2 (the calculation is simplified when / = D). According to statistical theory, the ratio N/Nc (N = total needles dropped, Nc = number of needles that cross a line) is equal to n/2.

Figure 15-11. The Buffon's Needle experiment, (folder 'Chapter 15 Examples', workbook 'Buffon's Needle', worksheet 'Calculation')

Since only the y coordinate of the end of the needle is used to determine whether the needle crosses a horizontal ruling, the spreadsheet shown in Figure 15-12 provides a simplified calculation. Only two horizontal rulings are assumed, at 0 and 1. Two random numbers are generated: one to specify the angle of the needle (0 < 6 < 360), the other to specify the y coordinate of the middle of the needle (0 < y < 1). Using these two values we calculate the y coordinate of the ends of the needle and determine whether it crosses either of the horizontal rulings. In the worksheet shown in Figure 15-12, the calculation was performed 2000 times (rows 5 through 2004) and the values in column H were summed.

The formulas used are

 in cell A5: =360*RAND() in cell B5: =RAND() in cell C5: =0.5*SIN(PI()*A5/180) in cell D5: =MIN(B5-C5,B5+C5) in cell E5: =MAX(B5-C5, B5+C5) in cell F5: =D5<=0 in cell G5: =E5>=1 in cell H5: =OR(F5,G5)*1 Figure 15-11. The Buffon's Needle experiment, (folder 'Chapter 15 Examples', workbook 'Buffon's Needle', worksheet 'Calculation')

 A B C D E F G H vertical Y coord. V coord. Y coord. y Of lower of upper crosses crosses 4 angle,0 of middle distance end encf iower? upper? Crossing 5 345,7 0,5477 -0.1233 0.4244 0.6710 FALSE FALSE 0 6 158.7 0.4928 0.1817 0.3110 0.6745 FALSE FALSE 0 7 20.6 0.2276 0.1761 0.0514 0.4037 FALSE FALSE 0 8 201.7 0.4285 -01846 0.2439 0 6132 FALSE FALSE 0 9 22.8 0.2546 0 1934 0.0614 0.4482 FALSE FALSE 0 10 287.0 0.3133 -0.4781 -0.1648 0.7914 TRUE FALSE 1 11 54.0 0.6497 0.4044 0.2453 1.0541 FALSE TRUE 1 12 60.2 0.0564 0.4338 -0.3773 0.4902 TRUE FALSE 1

Figure 15-12. Portion of table to calculate n by Buffon's Needle method. There are

2000 rows of calculation in the spreadsheet, (folder 'Chapter 15 Examples', workbook 'Buffon's Needle', worksheet 'Calculation')

Figure 15-13 shows the result of recalculating the sheet 100 times, to provide a total of 200,000 calculations. As you can see, the calculation does not "converge" very efficiently. Compare the result with the evaluation of n by evaluation of a series (Chapter 4) or by integration of a function (Chapter 7); both methods are much more efficient.

0 50000 100000 150000 200000 250000

Number of trials

Figure 15-13. Approach of simulation result to the value n as the number of trials increases.

(folder 'Chapter 15 Examples', workbook 'Buffon's Needle', worksheet 'Many trials')

### Monte Carlo Integration

The Monte Carlo method can be used to integrate a function that is difficult or impossible to evaluate by direct methods. Often the process of "integration" is the determination of the area of a figure. We'll illustrate the technique by determining the area of two figures: first, the area of a circle (from which we can evaluate 7t), and second, the area of an irregular figure.

The evaluation of % is a classic illustration of the determination of an area by the Monte Carlo method. Two random numbers in the range -1 to +1 are used to determine the coordinates of a point in the x, y plane. The number of points inside the circle, defined by the equation x2 + y2 = 1, divided by the total number of points, gives the ratio of the circle to the circumscribing square. Figure 15-14 illustrates such a calculation, using 4000 points.

Figure 15-14. Estimation of n by using RAND. This particular calculation gave 3.129 as the value of n.