Classic Computer Magazine Archive CREATIVE COMPUTING VOL. 11, NO. 6 / JUNE 1985 / PAGE 70

Probability and computers; simulate, then analyze. Glenda Lappan; M.J. Winter.

Probability and Computers

In the past, the study of probability in school has almost of necessity concentrated on formulas and theoretical principles. Situations were simulated by means of spinners, tossing dice and coins, and drawing colored balls out of an urn. While simulations of this sort can be very useful, making a large number of replications is time consuming.

Introducing a microcomputer allows probability to be studied in a new and exciting way. Simulation can become an important mathematical technique for the learner. An event can be replicated a large number of times to determine an empirical probability, which can then provide a check on the theoretical analysis of the problem. In fact, the analysis involved in writing an accurate simulation may form a basis for a later proof.

Many probability statements that we encounter in everyday life are empirically based--weather predictions, for example. Other probability situations, such as the odds of winning the state lottery, are theoretically analyzed. Therefore, it is important that we learn the basic theoretical ideas of probability, but also learn to appreciate the modern role of simulation in making predictive statements.

In this article we will present four probability problems, their simulations and analyses. We have found these four to be an excellent collection for illustrating the power of simulation and how empirical solutions can stimulate an interest in theoretical solutions. The four problems are of varied types.

The first illustrates a discrete situation for which it is possible to list the sample space. The second and third are both continuous--the number of possible outcomes is infinite. The second has a geometric solution, and the third uses elementary trigonometry. The last problem is discrete but has a surprising continuous extension question which leads to 1/e.

Problem 1: How Do You Pay Your Bill?

Mr. Jones owes Pat $5 per week for delivering his paper. He proposes that instead of paying the $5 in cash, each week he will let Pat reach into a sack, which contains a ten dollar bill and five ones, and draw two of the bills. Should Pat go along with Mr. Jones' scheme?

The Simulation and Program

There are six bills in the sack, so we generate randomly an integer from 1 to 6 (line 140 below) and decide, arbitrarily, that the 1 will correspond to the ten dollar bill. If the 1 is generated, then Pat will draw a total of $11 (line 210). If the first bill is not the $10, there are five bills remaining. An integer from 1 to 5 is generated (line 160); again we let the 1 correspond to the $10. We compute Pat's average weekly earnings for a 50 week period (line 230).

Observations and Analysis

The simulated results suggest an average of around $5. Computing the long term average (expected value) is easily done by listing all the possible combinations of two bills that could be drawn from the sack. If the six bills are denoted T, 01, 02, 03, 04, and 05, the possible combinations of the two bills are

One third of these 15 combinations have a value of $11. Two-thirds have a value of $2. Thus the expected value of the two bills is

1/3*11 + 2/3*2 = 5

so that, in the long run, Pat will neither gain nor lose by adopting the sack method. It is a "fair' offer.

Because the sample space is small (15 elements) and because there are only two possible values of the bills, a small number of simulations will give a true picture of the expected value.

Problem 2: Meeting for Lunch

Two friends who have unpredictable lunch hours agree to meet for lunch at their favorite restaurant whenever possible. Neither wishes to eat at that particular restaurant alone and each dislikes waiting for the other, so they agree that:

1. Each will arrive at a random time between noon and 1:00 p.m.

2. Each will wait for the other either for 15 minutes or until 1:00 p.m.

On a given day, what is the probability that the friends will meet?

The Simulation and Program

Each friend can arrive at any instant between noon and 1:00. If arrival at each instant is equally probable, then, since there is an infinite number of instances, the probability of arriving at any particular instant is 0. This point will cause consternation among readers who believe that they have been taught that if the probability is 0, then the event cannot occur. However, the nature of a continuous situation is that the event can actually take place as is shown in the program below, which predicts how often the two friends meet. In the program, the time within the one-hour period that each friend arrives is selected in liens 130 and 140. Line 150 tests to see if the two times are within 15 minutes (.25 of one hour) of each other. The total times they meet in N days is given by M.

Observations and Analysis

An immediate reaction is: they will wait 30 minutes between them. That is half an hour, so the probability is .5. The simulation results strongly suggest that this reasoning is incorrect.

To analyze the problem, draw a unit (one hour) square (see below); a point, (F1, F2), within the square will represent one possible set of arrival times for Friend 1 and Friend 2. If the point lies within the shaded strip representing times 15 minutes or less apart, the friend meet.

Comparing the area of the non-shaded triangles to unity, we see that

2* areas of each triangle = 2{1/2){3/4){3/4)=9/16

is the proportion of time the friends do not meet. Hence 7/16 = .44 is the probability of meeting. In the continuous case, it is impossible to "list' the sample space, but it is sometimes possible to represent it with a picture.

Problem 3: Points on the Unit Circle

Pick two points at random on the unit circle (a circle of radius 1). What is the probability that the distance between them is less the one?

The Simulation and Program

For readers who have studied trigonometry, the easiest way to obtain a random point on the unit circle is to generate a real number Z between 0 and 2* , and let the point have coordinates, Z=cos(Z) and Y=(Z). (See program.) The points are selected in lines 130 and 150, and the coordinates calculated in lines 140 and 160. The distance between the points is then calculated in line 170.

Observations and Analysis

This is another continuous problem; the answer is unchanged if the question is worded "what is the probability the distance is less than or equal to one?' To analyze the problem, draw the unit circle and select a point P on it. Draw the radius OP. Let Q be any other point on the circle except that point diagonally opposite P. Look at the triangle QOP. If the angle QOP < 60~, then QP < 1. If the angle = 60~, then an equilateral triangle has been formed and QP = 1. One third of the points on the circle are within +60~ of OP. Hence the probability that the distance QP is less than (or equal to) one is 1/3.

Algebra students may employ the following line of reasoning: if (x, y) is on the circle, then both

-1<x<1 and y2=1-x2.

To find (x, y) at random, we generate x between -1 and 1, take y= 1-x2, and let y be negative with probability .5:

X=INT(2 ND(1)-1)

Y = SQR(1-XX)

IF RND(1) < .5 THEN Y = -Y

When this method of selecting "random' points is used, the results are noticeably different. To see why, suppose P(XY) is chosen this way. Then -.5<x<.5 with probability 1/2, and P lies on one of the two thickened arcs, with probability 1/2. Equivalently, half the points generated will lie on the arcs. The central angle, 0, subtended by each arc is 60~, i.e., the arcs together form 1/3 of the unit circle. If half the points chosen lie on one third of the circle, then the points are not "picked at random.'

Problem 4: Catching the Counterfeiter

You, the ruler of the kingdom of Wellsall, suspect that your treasurer is robbing you by substituting counterfeit coins for gold ones. The coins are packed 25 to a bag, and, in fact, the treasurer is placing one false coin in every bag. You command the treasurer to bring in 25 bags of coins. From each bag you select one coin; the coins are then analyzed. What is the probability that you will find a false coin?

Change both 25's to 50. What is the probability now? Change both 25's to 100. What is the probability now?

The Simulation and Program

We will replicate the "trial' of the counterfeiter several times (N, line 100) (See below). For each trial we examine 25 bags (line 180). For each bag we must select a coin. We select a coin by generating a random number from 1 to 25 (line 140); if the number generated is 12, we have found a false coin. One false coin will prove the guilt of the treasurer, so the trial is terminated (line 150) and the treasurer dispatched.

Observations and Analysis

Your first reaction to this problem is likely to be that the treasurer is very safe. After all, there is only one false coin in each bag of 25, so the probability of being caught is about 1/25. With more coins in the bags, the treasurer should be even safer. For these students the simulated results are a shock. The probability of being caught seems to be approximately .60. Moreover, the number of coins in the bag does not appear to influence that result.

For the first bag, the probability of detecting the false coin is 1/25. This means that the treasurer has probability (1-1/25) of escaping detection when bag 1 is opened. However, the probability of escaping for two bags is (24/25){24/25). The probability of being safe through 25 bags is:

[24/25]25 .36

The probability of being caught is 1-.36=.64.

When more coins are placed in each bag, correspondingly more bags are examined. If there are N coins to a bag and N bags each have one coin removed, then the probability the treasurer escapes is

[N-1/N]N = (1-1/N)N

which approaches 1/e as N . For large N, therefore, the probability of detection is 1-1/e=.63.