✐

✐

“91974˙CH02˙ﬁnal” — 2012/12/14 — 13:58 — page 62 — #18

✐

✐

✐

✐

✐

✐

62 CHAPTER 2

π

thon

2.6 A Monte Carlo Simulation

Our ﬁnal technique for approximating pi will make use of probability and random behavior.

These types of solutions are often referred to as Monte Carlo simulations because they

use features that are similar to “games of chance.” In other words, instead of knowing

speciﬁcally what will happen during the simulation, a random element will be introduced

into the simulation so that it will behave diﬀerently each time.

To set up our simulation, consider Figure 2.9. Pretend that we are looking at a dartboard

in the shape of a square that is 2 units wide and 2 units high. A circle has been inscribed

within the square so that the radius of the circle is 1 unit.

Now assume that we cut out the upper right-hand quadrant of the square (see Figure 2.10).

The result will be a square that is 1 unit high and 1 unit wide with a quarter-circle tran-

scribed inside. This piece is what we will use to “play” our simulation. The area of the

original square was 4 units. The area of the original circle was πr

2

= π units since the circle

had a radius of 1 unit. After we cut the upper-right quarter, the area of the quarter-circle

is

π

4

and the area of the entire quarter square is 1.

The simulation will work by randomly “throwing darts” at the dartboard in Figure 2.10.

We will assume that every dart will hit the board but that the location of that strike will

be random. It is easy to see that each dart will hit the square but some will also land inside

the quarter-circle. The number of darts that hit inside or outside the quarter-circle will be

proportional to the areas of each. More speciﬁcally, the fraction of darts that land inside

the quarter-circle will be equal to

π

4

.

1

0

1

Figure 2.9 Setting up the Monte Carlo simulation

✐

✐

“91974˙CH02˙ﬁnal” — 2012/12/14 — 13:58 — page 63 — #19

✐

✐

✐

✐

✐

✐

2.6 A Monte Carlo Simulation 63

0

1

1

Figure 2.10 The upper-right quadrant

In order to implement this simulation, we will use the random module. You may ﬁnd it

useful to invoke the help command on the module to explore the functionality. For our

purposes here, we will use only the random function—a random number generator that

returns a ﬂoating-point number between 0 and 1 each time it is called. Session 2.8 shows

the random function in action.

>>> import random

>>> random.random()

0.57346717619779752

>>> random.random()

0.54832767404135008

>>> for i in range(5):

print (random.random())

0.355533646663

0.607688967224

0.464142190998

0.814134550939

0.712540183514

>>>

Session 2.8 Exercising the random function

We will use these random numbers to simulate the random dart throw we described earlier.

For each round of the simulation, we will randomly generate two numbers between 0 and 1.

✐

✐

“91974˙CH02˙ﬁnal” — 2012/12/14 — 13:58 — page 64 — #20

✐

✐

✐

✐

✐

✐

64 CHAPTER 2

π

thon

These will represent the position that each dart lands on our square. We can think of the

board as having a horizontal and a vertical axis, both labeled between 0 and 1. If we let

the ﬁrst number represent the horizontal distance and the second represent the vertical

distance, then the two numbers give us an exact location for the point.

Now recall that the location of the random point is important in that we need to know

whether it occurs inside or outside the quarter-circle. Our plan is to keep track of the

number of points that land inside that circle and then use that number to compute our

estimate for π. In order to do this, we need to be able to decide whether the point is in the

circle. This will require a few new ideas.

2.6.1 Boolean Expressions

To solve the problem of deciding whether a point is inside or outside of the circle, we need to

be able to ask a question. In computer science, questions are often referred to as Boolean

expressions because the result of asking them is one of the Boolean data values True or

False. These Boolean values are another primitive type in Python.

>>> 6

6

>>> 4.5

4.5

>>> True

True

>>> False

False

>>>

The easiest type of Boolean expression to write compares the results of two expressions.

To make this comparison, the common relational operators from mathematics such as

equal to, less than, and greater than are used. Table 2.1 shows the operators and their

meaning in Python.

Comparisons between two data values using a relational operator are called relational

expressions. Like other expressions in Python, a result is produced when relational ex-

pressions are evaluated. In this case, the result will be a Boolean value. Session 2.9 shows a

few simple examples of relational expressions. Note that the variable apple is assigned the

value 25 and is then used in an equality comparison. It is important to distinguish between

Start Free Trial

No credit card required