A random walk in Monte Carlo

How far, on average, does a two-dimensional Brownian particle move from its origin in a given number of steps? The answer to this question can, for example, provide insight into the rate at which a fluid spreads or the extent of an animal’s foraging territory.

The distance traveled in any one particular random walk is meaningless; the particle may return the origin, walk away from the origin at every step, or do something in between. None of these outcomes tells us anything about the expected, or average, behavior of the system. Instead, to model the expected behavior, we need to compute the average distance over many, many random walks. This kind of simulation is called a Monte Carlo simulation.

As we will be calling randomWalk many times, we would like to speed things up by skipping the turtle visualization of the random walks. We can prevent drawing by incorporating a flag variable as a parameter to randomWalk. A flag variable takes on a Boolean value, and is used to switch some behavior on or off. In Python, the two possible Boolean values are named True and False (note the capitalization). In the randomWalk function, we will call the flag variable draw, and cause its value to influence the drawing behavior with another if statement:

def randomWalk(steps, tortoise, draw):
        ⋮   
 
        if draw:
            tortoise.goto(x * moveLength, y * moveLength)
        ⋮   

Now, when we call randomWalk, we pass in either True or False for our third argument. If draw is True, then tortoise.goto(…) will be executed but, if draw is False, it will be skipped.

To find the average over many trials, we will call our randomWalk function repeatedly in a loop, and use an accumulator variable to sum up all the distances.

def rwMonteCarlo(steps, trials):
    """A Monte Carlo simulation to find the expected distance
       that a random walk finishes from the origin.
 
     Parameters:
         steps: the number of steps in the random walk
         trials: the number of random walks
 
     Return value: the average distance from the origin
     """
 
     totalDistance = 0
     for trial in range(trials):
         distance = randomWalk(steps, None, False)
         totalDistance = totalDistance + distance
     return totalDistance / trials

Notice that we have passed in None as the argument for the second parameter (tortoise) of randomWalk. With False being passed in for the parameter draw, the value assigned to tortoise is never used, so we pass in None as a placeholder “dummy value.”

Ultimately, we want to understand the distance traveled as a function of the number of steps. In other words, if the particle moves n steps, does it travel an average distance of n/2 or n/25 or n or log₂ n or ... ? To empirically discover the answer, we need to run the Monte Carlo simulation for many different numbers of steps, and try to infer a pattern from a plot of the results. The following function does this with steps equal to 100, 200, 300, ..., maxSteps, and then plots the results.

import matplotlib.pyplot as pyplot
 
def plotDistances(maxSteps, trials):
    """Plots the average distances traveled by random walks of
       100, 200, ..., maxSteps steps.
 
    Parameters:
        maxSteps: the maximum number of steps for the plot
        trials: the number of random walks in each simulation
 
    Return value: None
    """
 
    distances = [ ]
    stepRange = range(100, maxSteps + 1, 100)
    for steps in stepRange:
        distance = rwMonteCarlo(steps, trials)
        distances.append(distance)
 
    pyplot.plot(stepRange, distances, label = 'Simulation')
    pyplot.legend(loc = 'center right')
    pyplot.xlabel('Number of Steps')
    pyplot.ylabel('Distance From Origin')
    pyplot.show()

The function we are seeking has actually been mathematically determined, and is approximately n. You can confirm this empirically by plotting this function alongside the simulated results. To do so, insert each of these three statements in their appropriate locations in the plotDistances function:

y = [ ]  # before loop
 
y.append(math.sqrt(steps))  # inside loop
 
pyplot.plot(stepRange, y, label = 'Model Function')   # after loop

The result is shown in Figure 5.2. This result tells us that after a random particle moves n unit-length steps, it will be about n units of distance away from where it started, on average. In any particular instance, however, a particle may be much closer or farther away.

As you discovered in Reflection 5.1, the quality of any Monte Carlo approximation depends on the number of trials. If you call plotDistances a few more times with different numbers of trials, you should find that the plot of the simulation results gets “smoother” with more trials. But more trials obviously take longer. This is another example of the tradeoffs that we often encounter when solving problems.

Histograms

As we increase the number of trials, our average results become more consistent, but what do the individual trials look like? To find out, we can generate a histogram of the individual random walk distances. A histogram for a data set is a bar graph that shows how the items in the data set are distributed across some number of intervals, which are usually called “buckets” or “bins.”

The following function is similar to rwMonteCarlo, except that it initializes an empty list before the loop, and appends one distance to the list in every iteration. Then it passes this list to the matplotlib histogram function hist. The first argument to the hist function is a list of numbers, and the second parameter is the number of buckets that we want to use.

def rwHistogram(steps, trials):
    """Draw a histogram of the given number of trials of
       a random walk with the given number of steps.
 
      Parameters:
          steps: the number of steps in the random walk
          trials: the number of random walks
 
      Return value: None
      """
 
      distances = [ ]
      for trial in range(trials):
          distance = randomWalk(steps, None, False)
          distances.append(distance)
 
      pyplot.hist(distances, 75)
      pyplot.show()

Exercises

5.1.1. Sometimes we want a random walk to reflect circumstances that bias the probability of a particle moving in some direction (i.e., gravity, water current, or wind). For example, suppose that we need to incorporate gravity, so a movement to the north is modeling a real movement up, away from the force of gravity. Then we might want to decrease the probability of moving north to 0.15, increase the probability of moving south to 0.35, and leave the other directions as they were. Show how to modify the randomWalk function to implement this situation.

5.1.2. Suppose the weather forecast calls for a 70% chance of rain. Write a function

weather()

that prints 'RAIN' (or something similar) with probability 0.7, and 'SUN!' otherwise.

Now write another version that snows with probability 0.66, produces a sunny day with probability 0.33, and rains cats and dogs with probability 0.01.

5.1.3. Write a function

loaded()

that simulates the rolling of a single “loaded die” that rolls more 1’s and 6’s than it should. The probability of rolling each of 1 or 6 should be 0.25. The function should use the random.random function and an if/elif/else conditional construct to assign a roll value to a variable named roll, and then return the value of roll.

5.1.4. Write a function

roll()

that simulates the rolling of a single fair die. Then write a function

diceHistogram(trials)

that simulates trials rolls of a pair of dice and displays a histogram of the results. (Use a bucket for each of the values 2–12.) What roll is most likely to show up?

5.1.5. The Monty Hall problem is a famous puzzle based on the game show “Let’s Make a Deal,” hosted, in its heyday, by Monty Hall. You are given the choice of three doors. Behind one is a car, and behind the other two are goats. You pick a door, and then Monty, who knows what’s behind all three doors, opens a different one, which always reveals a goat. You can then stick with your original door or switch. What do you do (assuming you would prefer a car)?

We can write a Monte Carlo simulation to find out. First, write a function

montyHall(choice, switch)

that decides whether we win or lose, based on our original door choice and whether we decide to switch doors. Assume that the doors are numbered 0, 1, and 2, and that the car is always behind door number 2. If we originally chose the car, then we lose if we switch but we win if we don’t. Otherwise, if we did not originally choose the car, then we win if we switch and lose if we don’t. The function should return True if we win and False if we lose.

Now write a function

monteMonty(trials)

that performs a Monte Carlo simulation with the given number of trials to find the probability of winning if we decide to switch doors. For each trial, choose a random door number (between 0 and 2), and call the montyHall function with your choice and switch = True. Count the number of times we win, and return this number divided by the number of trials. Can you explain the result?

5.1.6. The value of π can be estimated with Monte Carlo simulation. Suppose you draw a circle on the wall with radius 1, inscribed inside a square with side length 2.

You then close your eyes and throw darts at the circle. Assuming every dart lands inside the square, the fraction of the darts that land in the circle estimates the ratio between the area of the circle and the area of the square. We know that the area of the circle is C = πr² = π1² = π and the area of the square is S = 2² = 4. So the exact ratio is π/4. With enough darts, f, the fraction (between 0 and 1) that lands in the circle will approximate this ratio: f ≈ π/4, which means that π ≈ 4f. To make matters a little simpler, we can just throw darts in the upper right quarter of the circle (shaded above). The ratio here is the same: (π/4)/1 = π/4. If we place this quarter circle on x and y axes, with the center of the circle at (0, 0), our darts will now all land at points with x and y coordinates between 0 and 1.

Use this idea to write a function

montePi(darts)

that approximates the value π by repeatedly throwing random virtual darts that land at points with x and y coordinates in [0, 1). Count the number that land at points within distance 1 of the origin, and return this fraction.

5.1.7. The Good, The Bad, and The Ugly are in a three-way gun fight (sometimes called a “truel”). The Good always hits his target with probability 0.8, The Bad always hits his target with probability 0.7, and The Ugly always hits his target with probability 0.6. Initially, The Good aims at The Bad, The Bad aims at The Good, and The Ugly aims at The Bad. The gunmen shoot simultaneously. In the next round, each gunman, if he is still standing, aims at his same target, if that target is alive, or at the other gunman, if there is one, otherwise. This continues until only one gunman is standing or all are dead. What is the probability that they all die? What is the probability that The Good survives? What about The Bad? The Ugly? On average, how many rounds are there? Write a function

goodBadUgly()

that simulates one instance of this three-way gun fight. Your function should return 1, 2, 3, or 0 depending upon whether The Good, The Bad, The Ugly, or nobody is left standing, respectively. Next, write a function

monteGBU(trials)

that calls your goodBadUgly function repeatedly in a Monte Carlo simulation to answer the questions above.

5.1.8. What is printed by the following sequence of statements in each of the cases below? Explain your answers.

if votes1 >= votes2:
    print('Candidate one wins!')
elif votes1 <= votes2:
    print('Candidate two wins!')
else:
    print('There was a tie.')

(a) votes1 = 184 and votes2 = 206

(b) votes1 = 255 and votes2 = 135

(c) votes1 = 195 and votes2 = 195

5.1.9. There is a problem with the code in the previous exercise. Fix it so that it correctly fulfills its intended purpose.

5.1.10. What is printed by the following sequence of statements in each of the following cases? Explain your answers.

majority = (votes1 + votes2 + votes3) / 2
if votes1 > majority:
    print('Candidate one wins!')
if votes2 > majority:
    print('Candidate two wins!')
if votes3 > majority:
    print('Candidate three wins!')
else:
    print('A runoff is required.')

(a) votes1 = 5 and votes2 = 5 and votes3 = 5

(b) votes1 = 9 and votes2 = 2 and votes3 = 4

(c) votes1 = 0 and votes2 = 15 and votes3 = 0

5.1.11. Make the code in the previous problem more efficient and fix it so that it fulfills its intended purpose.

5.1.12. What is syntactically wrong with the following sequence of statements?

if x < 1:
    print('Something.')
else:
    print('Something else.')
elif x > 3:
    print('Another something.')

5.1.13. What is the final value assigned to result after each of the following code segments?

(a)     n = 13
        result = n
        if n > 12:
            result = result + 12
        if n < 5:
            result = result + 5
        else:
            result = result + 2

(b)     n = 13
        result = n
        if n > 12:
            result = result + 12
        elif n < 5:
            result = result + 5
        else:
            result = result + 2

5.1.14. Write a function

computeGrades(scores)

that returns a list of letter grades corresponding to the numerical scores in the list scores. For example, computeGrades([78, 91, 85]) should return the list ['C', 'A', 'B']. To test your function, use lists of scores generated by the following function.

import random
 
def randomScores(n):
    scores = []
    for count in range(n):
        scores.append(random.gauss(80, 10))
    return scores

5.1.15. Determining the number of bins to use in a histogram is part science, part art. If you use too few bins, you might miss the shape of the distribution. If you use too many bins, there may be many empty bins and the shape of the distribution will be too jagged. Experiment with the correct number of bins for 10,000 trials in rwHistogram function. At the extremes, create a histogram with only 3 bins and another with 1,000 bins. Then try numbers in between. What seems to be a good number of bins? (You may also want to do some research on this question.)

Implementation

But first, let’s implement the PRNG “black box” in Figure 5.3, based on the Lehmer PRNG difference equation. It is a very simple function!

def lehmer(r, m, a):
    """Computes the next pseudorandom number using a Lehmer PRNG.
 
     Parameters:
         r: the seed or previous pseudorandom number
         m: a prime number
         a: an integer between 1 and m - 1
 
     Return value: the next pseudorandom number
     """
 
     return (a * r) % m

The parameter r represents R(t − 1) and the value returned by the function is the single value R(t).

Now, for our function to generate good pseudorandom numbers, we need some better values for m and a. Some particularly good ones were suggested by Keith Miller and Steve Park in 1988:

m = 2³¹ − 1 = 2, 147, 483, 647 and a = 16, 807.

A Lehmer generator with these parameters is often called a Park-Miller psuedorandom number generator. To create a Park-Miller PRNG, we can call the lehmer function repeatedly, each time passing in the previously generated value and the Park-Miller values of m and a, as follows.

def randomSequence(length, seed):
    """Returns a list of Park-Miller pseudorandom numbers.
 
    Parameters:
        length: the number of pseudorandom numbers to generate
        seed: the initial seed
 
    Return value: a list of Park-Miller pseudorandom numbers
                  with the given length
    """
 
    r = seed
    m = 2**31 - 1
    a = 16807
    randList = [ ]
    for index in range(length):
        r = lehmer(r, m, a)
        randList.append(r)
    return randList

In each iteration, the function appends a new pseudorandom number to the end of the list named randList. (This is another list accumulator.) The randomSequence function then returns this list of length pseudorandom numbers. Try printing the result of randomSequence(100, 1).

Because all of the returned values of lehmer are modulo m, they are all in the interval [0 . . m – 1]. Since the value of m is somewhat arbitrary, random numbers are usually returned instead as values from the interval [0, 1), as Python’s random function does. This is accomplished by simply dividing each pseudorandom number by m. To modify our randomSequence function to returns a list of numbers in [0, 1) instead of in [0 . . m – 1], we can simply append r / m to randList instead of r.

As an aside, you can set the seed used by Python’s random function by calling the seed function. The default seed is based on the current time.

The ability to generate an apparently random, but reproducible, sequence by setting the seed has quite a few practical applications. For example, it is often useful in a Monte Carlo simulation to be able to reproduce an especially interesting run by simply using the same seed. Pseudorandom sequences are also used in electronic car door locks. Each time you press the button on your dongle to unlock the door, it is sending a different random code. But since the dongle and the car are both using the same PRNG with the same seed, the car is able to recognize whether the code is legitimate.

Testing randomness

How can we tell how random a sequence of numbers really is? What does it even mean to be truly “random?” If a sequence is random, then there must be no way to predict or reproduce it, which means that there must be no shorter way to describe the sequence than the sequence itself. Obviously then, a PRNG is not really random at all because it is entirely reproducible and can be described by simple formula. However, for practical purposes, we can ask whether, if we did not know the formula used to produce the numbers, could we predict them, or any patterns in them?

One simple test is to generate a histogram from the list of values.

If the list is random, each bucket should contain about 1%, or 10,000, of the numbers. The following function generates such a histogram.

import matplotlib.pyplot as pyplot
 
def histRandom(length):
    """Displays a histogram of numbers generated by the Park-Miller PRNG.
 
     Parameter:
         length: the number of pseudorandom numbers to generate
 
     Return value: None
     """
 
     samples = randomSequence(length, 6)
     pyplot.hist(samples, 100)
     pyplot.show()

There are several other ways to test for randomness, many of which are more complicated than we can describe here (we leave a few simpler tests as exercises). These tests reveal that the Lehmer PRNG that we described exhibits some patterns that are undesirable in situations requiring higher-quality random numbers. However, the Python random function uses one of the best PRNG algorithms known, called the Mersenne twister, so you can use it with confidence.

Exercises

5.2.1. We can visually test the quality of a PRNG by using it to plot random points on the screen. If the PRNG is truly random, then the points should be uniformly distributed without producing any noticeable patterns. Write a function

testRandom(n)

that uses turtle graphics and random.random to plot n random points with x and y each in [0, 1). Here is a “skeleton” of the function with some turtle graphics set up for you. Calling the setworldcoordinates function redefines the coordinate system so that the lower left corner is (0, 0) and the upper right corner is (1, 1). Use the turtle graphics functions goto and dot to move the turtle to each point and draw a dot there.

def testRandom(n):
    """ your docstring here """
 
     tortoise = turtle.Turtle()
     screen = tortoise.getscreen()
     screen.setworldcoordinates(0, 0, 1, 1)
     screen.tracer(100)    # only draw every 100 updates
     tortoise.up()
     tortoise.speed(0)
 
     # draw the points here
 
     screen.update()       # ensure all updates are drawn
     screen.exitonclick()

5.2.2. Repeat Exercise 5.2.1, but use the lehmer function instead of random.random. Remember that lehmer returns an integer in [0 . . m – 1], which you will need to convert to a number in [0, 1). Also, you will need to call lehmer twice in each iteration of the loop, so be careful about how you are passing in values of r.

5.2.3. Another simple test of a PRNG is to produce many pseudorandom numbers in [0, 1) and make sure their average is 0.5. To test this, write a function

avgTest(n)

that returns the average of n pseudorandom numbers produced by the random function.

The uniform distribution

The simplest general probability distribution is the uniform distribution, which assigns equal probability to every value in a range, or to every equal length interval in a range. A PRNG like the random function returns values in [0, 1) according to a uniform distribution. The more general Python function random.uniform(a, b) returns a uniformly random value in the interval [a, b]. In other words, it is equally likely to return any number in [a, b]. For example,

>>> random.uniform(0, 100)
77.10524701669804

The normal distribution

Measurements of most everyday and natural processes tend to exhibit a “bell curve” distribution, formally known as a normal or Gaussian distribution. A normal distribution describes a process that tends to generate values that are centered around a mean. For example, measurements of people’s heights and weights tend to fall into a normal distribution, as do the velocities of molecules in an ideal gas.

A normal distribution has two parameters: a mean value and a standard deviation. The standard deviation is, intuitively, the average distance a value is from the mean; a low standard deviation will give values that tend to be tightly clustered around the mean while a high standard deviation will give values that tend to be spread out from the mean.

The normal distribution assigns probabilities to intervals of real numbers in such a way that numbers centered around the mean have higher probability than those that are further from the mean. Therefore, if we are generating random values according to a normal distribution, we are more likely to get values close to the mean than values farther from the mean.

The Python function random.gauss returns a value according to a normal distribution with a given mean and standard deviation. For example, the following returns a value according to the normal distribution with mean 0 and standard deviation 0.25.

>>> random.gauss(0, 0.25)
-0.3371607214433552

Figure 5.4 shows a histogramhistogram of 100,000 values returned by random.gauss(0, 0.25). Notice that the “bell curve” of frequencies is centered at the mean of 0.

The central limit theorem

Intuitively, the normal distribution is so common because phenomena that are the sums of many additive random factors tend to be normal. For example, a person’s height is the result of several different genes and the person’s health, so the distribution of heights in a population tends to be normal. To illustrate this phenomenon, let’s create a histogram of the sums of numbers generated by the random function. Below, the sumRandom function returns the sum of n random numbers in the interval [0, 1). The sumRandomHist function creates a list named samples that contains trials of these sums, and then plots a histogram of them.

import matplotlib.pyplot as pyplot
import random
 
def sumRandom(n):
    """Returns the sum of n pseudorandom numbers in [0,1).
 
     Parameter:
         n: the number of pseudorandom numbers to generate
 
     Return value: the sum of n pseudorandom numbers in [0,1)
     """
 
     sum = 0
     for index in range(n):
         sum = sum + random.random()
     return sum
 
def sumRandomHist(n, trials):
    """Displays a histogram of sums of n pseudorandom numbers.
 
     Parameters:
         n: the number of pseudorandom numbers in each sum
         trials: the number of sums to generate
 
     Return value: None
     """
 
     samples = [ ]
     for index in range(trials):
         samples.append(sumRandom(n))
     pyplot.hist(samples, 100)
     pyplot.show()

When we call sumRandomHist with n = 1, we get the expected uniform distribution of values, shown in the upper left of Figure 5.5. However, for increasing values of n, we notice that the distribution of values very quickly begins to look like a normal distribution, as illustrated in the rest of Figure 5.5. In addition, the standard deviation of the distribution (intuitively, the width of the “bell”) appears to get smaller relative to the mean.

The mathematical name for this phenomenon is the central limit theorem. Intuitively, the central limit theorem implies that any large set of independent measurements of a process that is the cumulative result of many random factors will look like a normal distribution. Because a normal distribution is centered around a mean, this also implies that the average of all of the measurements will be close to the true mean.

Exercises

5.3.1. A more realistic random walk has the movement in each step follow a normal distribution. In particular, in each step, we can change both x and y according to a normal distribution with mean 0. Because the values produced by this distribution will be both positive and negative, the particle can potentially move in any direction. To make the step sizes small, we need to use a small standard deviation, say 0.5:

x = x + random.gauss(0, 0.5)
y = y + random.gauss(0, 0.5)

Modify the randomWalk function so that it updates the position of the particle in this way instead. Then use the rwMonteCarlo and plotDistances functions to run a Monte Carlo simulation with your new randomWalk function. As we did earlier, call plotDistances(1000, 10000). How do your results differ from the original version?

5.3.2. Write a function

uniform(a, b)

that returns a number in the interval [a, b) using only the random.random function. (Do not use the random.uniform function.)

5.3.3. Suppose we want a pseudorandom integer between 0 and 7 (inclusive). How can we use the random.random() and int functions to get this result?

5.3.4. Write a function

randomRange(a, b)

that returns a pseudorandom integer in the interval [a . . b] using only the random.random function. (Do not use random.randrange or random.randint.)

5.3.5. Write a function

normalHist(mean, stdDev, trials)

that produces a histogram of trials values returned by the gauss function with the given mean and standard deviation. In other words, reproduce Figure 5.4. (This is very similar to the sumRandomHist function.)

5.3.6. Write a function

uniformHist(a, b, trials)

that produces a histogram of trials values in the range [a, b] returned by the uniform function. In other words, reproduce the top left histogram in Figure 5.5. (This is very similar to the sumRandomHist function.)

5.3.7. Write a function

plotChiSquared(k, trials)

that produces a histogram of trials values, each of which is the sum of k squares of values given by the random.gauss function with mean 0 and standard deviation 1. (This is very similar to the sumRandomHist function.) The resulting probability distribution is known as the chi-squared distribution (χ² distribution) with k degrees of freedom.

Short circuit evaluation

The and and or operators exhibit a behavior known as short circuit evaluation that comes in handy in particular situations. Since both operands of an and expression must be true for the expression to be true, the Python interpreter does not bother to evaluate the second operand in an and expression if the first is false. Likewise, since only one operand of an or expression must be true for the expression to be true, the Python interpreter does not bother to evaluate the second operand in an or expression if the first is true.

For example, suppose we wanted to write a function to decide, in some for-profit company, whether the CEO’s compensation divided by the average employees’ is at most some “fair” ratio. A simple function that returns the result of this test looks like this:

def fair(employee, ceo, ratio):
    """Decide whether the ratio of CEO to employee pay is fair.
 
    Parameters:
        employee: average employee pay
        ceo: CEO pay
        ratio: the fair ratio
 
    Return: a Boolean indicating whether ceo / employee is fair
    """
 
    return (ceo / employee <= ratio)

This function will not always work properly because, if the average employees’ compensation equals 0, the division operation will result in an error. Therefore, we have to test whether employee == 0 before attempting the division and, if so, return False (because not paying employees is obviously never fair). Otherwise, we want to return the result of the fairness test. The following function implements this algorithm.

def fair(employee, ceo, ratio):
    """ (docstring omitted) """
 
    if employee == 0:
        result = False
    else:
        result = (ceo / employee <= ratio)
    return result

However, with short circuit evaluation, we can simplify the whole function to:

def fair(employee, ceo, ratio):
    """ (docstring omitted) """
 
     return (employee != 0) and (ceo / employee <= ratio)

If employee is 0, then (employee != 0) is False, and the function returns False without evaluating (ceo / employee <= ratio). On the other hand, if (employee != 0) is true, then (ceo / employee <= ratio) is evaluated, and the return value depends on this outcome. Notice that this would not work if the and operator did not use short circuit evaluation because, if (employee != 0) were false and then (ceo / employee <= ratio) was evaluated, the division would result in a “divide by zero” error!

To illustrate the analogous mechanism with the or operator, suppose we wanted to write the function in the opposite way, instead returning True if the ratio is unfair. The first version of the function would look like this:

def unfair(employee, ceo, ratio):
    """Decide whether the ratio of CEO to employee pay is unfair.
 
     Parameters:
         employee: average employee pay
         ceo: CEO pay
         ratio: the fair ratio
 
     Return: a Boolean indicating whether ceo / employee is not fair
     """
 
     if employee == 0:
         result = True
     else:
         result = (ceo / employee > ratio)
     return result

However, taking advantage of short circuit evaluation with the or operator, we can simplify the whole function to:

def unfair(employee, ceo, ratio):
    """ (docstring omitted) """
 
     return (employee == 0) or (ceo / employee > ratio)

In this case, if (employee == 0) is True, the whole expression returns True without evaluating the division test, thus avoiding an error. On the other hand, if (employee == 0) is False, the division test is evaluated, and the final result is equal to the outcome of this test.

Complex expressions

Some situations require Boolean expressions that are more complex than what we have seen thus far. To illustrate, let’s consider how to test whether a particle in a random walk at position (x, y) is in one of the four corners of the screen, as depicted by the shaded regions below.

There are (at least) two ways we can write a Boolean expression to test this condition. One way is to test whether the particle is in each corner individually.

1. For the point to be corner 1, x > d and y > d must be True;

2. for the point to be corner 2, x < -d and y > d must be True;

3. for the point to be corner 3, x < -d and y < -d must be True; or

4. for the point to be corner 4, x > d and y < -d must be True.

Since any one of these can be True for our condition to be True, the final test, in the form of a function, looks like the following. (The “backslash” () character below is the line continuation character. It indicates that the line that it ends is continued on the next line. This is sometimes handy for splitting very long lines of code.)

>>> def corners(x, y, d):
        return x > d and y > d or x < -d and y > d or 
               x < -d and y < -d or x > d and y < -d
>>> corners(11, -11, 10)
True
>>> corners(11, 0, 10)
False

Although our logic is correct, this expression is only correct if the Python interpreter evaluates the and operator before it evaluates the or operator. Otherwise, if the or operator is evaluated first, then the first expression evaluated will be y > d or x < -d, shown in red below, which is not what we intended.

x > d and y > d or x < -d and y > d or x < -d and y < -d or x > d and y < -d

Therefore, understanding the order in which operators are evaluated, known as operator precedence, becomes important for more complex conditions such as this. In this case, the expression is correct because and has precedence over or, as illustrated in Table 5.2. Also notice from Table 5.2 that the comparison operators have precedence over the Boolean operators, which is also necessary for our expression to be correct. If in doubt, you can use parentheses to explicitly specify the intended order. Parentheses would be warranted here in any case, to make the expression more understandable:

>>> def corners(x, y, d):
        return (x > d and y > d) or (x < -d and y > d) or 
               (x < -d and y < -d) or (x > d and y < -d)

Now let’s consider an alternative way to think about the corner condition: for a point to be in one of the corners, it must be true that x must either exceed d or be less than -d and y must either exceed d or be less than -d. The equivalent Boolean expression is enclosed in the following function.

>>> def corners2(x, y, d):
        return x > d or x < -d and y > d or y < -d
>>> corners2(11, -11, 10)
True
>>> corners2(11, 0, 10)
True

Due to the operator precedence order, this is a situation where parentheses are required. Without parentheses, the and expression in red below is evaluated first, which is not our intention.

x > d or x < -d and y > d or y < -d

So the correct implementation is

>>> def corners2(x, y, d):
        return (x > d or x < -d) and (y > d or y < -d)
>>> corners2(11, -11, 10)
True
>>> corners2(11, 0, 10)
False

*Using truth tables

To confirm that any Boolean expression is correct, we must create a truth table for it, and then confirm that every case matches what we intended. In this expression, there are four separate Boolean “inputs,” one for each expression containing a comparison operator. In the truth table, we will represent each of these with a letter to save space:

• x > d will be represented by p,

• x < -d will be represented by q,

• y > d will be represented by r, and

• y < -d will be represented by s.

So the final expression we are evaluating is (p or q) and (r or s).

In the truth table below, the first four columns represent our four inputs. With four inputs, we need 2⁴ = 16 rows, one for each possible assignment of truth values to the inputs. There is a trick to quickly writing down all the truth value combinations; see if you can spot it in the first four columns. (We are using T and F as abbreviations for True and False. The extra horizontal lines are simply to improve readability.)

To fill in the fifth column, we only need to look at the first and second columns. Since this is an or expression, for each row in the fifth column, we enter a T if there is at least one T among the first and second columns of that row, or a F otherwise. Similarly, to fill in the sixth column, we only look at the third and fourth column. To fill in the last column, we look at the two previous columns, filling in a T in each row in which the fifth and sixth columns are both T, or a F otherwise.

To confirm that our expression is correct, we need to confirm that the truth value in each row of the last column is correct with respect to that row’s input values. For example, let’s look at the fifth, sixth, and eighth rows of the truth table (in red).

In the fifth row, the last column indicates that the expression is False. Therefore, it should be the case that a point described by the truth values in the first four columns of that row is not in one of the four corners. Those truth values say that x > d is false, x < -d is true, y > d is false, and y < -d is false; in other words, x is less than -d and y is between -d and d. A point within these bounds is not in any of the corners, so that row is correct.

Now let’s look at the sixth row, where the final expression is true. The first columns of that row indicate that x > d is false, x < -d is true, y > d is false, and y < -d is true; in other words, both x and y are less than -d. A point within these bounds is in the bottom left corner, so that row is also correct.

The eighth row is curious because it states that both y > d and y < -d are true. But this is, of course, impossible. Because of this, we say that the implied statement is vacuously true. In practice, we cannot have such a point, so that row is entirely irrelevant. There are seven such rows in the table, leaving only four other rows that are true, matching the four corners.

Many happy returns

We often come across situations in which we want an algorithm (i.e., a function) to return different values depending on the outcome of a condition. The simplest example is finding the maximum of two numbers a and b. If a is at least as large as b, we want to return a; otherwise, b must be larger, so we return b.

def max(a, b):
    """Returns the maximum of a and b.
 
    Parameters:
        a, b: two numbers
 
    Return value: the maximum value
    """
 
    if a >= b:
        result = a
    else:
        result = b
    return result

We can simplify this function a bit by returning the appropriate value right in the if/else statement:

def max(a, b):
    """ (docstring omitted)"""
 
    if a >= b:
        return a
    else:
        return b

It may look strange at first to see two return statements in one function, but it all makes perfect sense. Recall from Section 3.5 that return both ends the function and assigns the function’s return value. So this means that at most one return statement can ever be executed in a function. In this case, if a >= b is true, the function ends and returns the value of a. Otherwise, the function executes the else clause, which returns the value of b.

The fact that the function ends if a >= b is true means that we can simplify it even further: if execution continues past the if part of the if/else, it must be the case that a >= b is false. So the else is extraneous; the function can be simplified to:

def max(a, b):
    """ (docstring omitted)"""
 
     if a >= b:
         return a
     return b

This same principle can be applied to situations with more than two cases. Suppose we wrote a function to convert a percentage grade to a grade point (i.e., GPA) on a 0–4 scale. A natural implementation of this might look like the following:

def assignGP(score):
    """Returns the grade point equivalent of score.
 
     Parameter:
         score: a score between 0 and 100
 
     Return value: the equivalent grade point value
     """
 
     if score >= 90:
         return 4
     elif score >= 80:
         return 3
     elif score >= 70:
         return 2
     elif score >= 60:
         return 1
     else:
         return 0

Suppose score was 92. In this case, the first condition is true, so the function returns the value 4 and ends. Execution never proceeds past the statement return 4. For this reason, the “el” in the next elif is extraneous. In other words, because execution would never have made it there if the previous condition was true, there is no need to tell the interpreter to skip testing this condition if the previous condition was true.

Now suppose score was 82. In this case, the first condition would be false, so we continue on to the first elif condition. Because we got to this point, we already know that score < 90 (hence the omission of that check). The first elif condition is true, so we immediately return the value 3. Since the function has now completed, there is no need for the “el” in the second elif either. In other words, because execution would never have made it to the second elif if either of the previous conditions were true, there is no need to skip testing this condition if a previous condition was true. In fact, we can remove the “el”s from all of the elifs, and the final else, with no loss in efficiency at all.

def assignGP(score):
    """ (docstring omitted) """
 
      if score >= 90:
          return 4
      if score >= 80:
          return 3
      if score >= 70:
          return 2
      if score >= 60:
          return 1
      return 0

Some programmers find it clearer to leave the elif statements in, and that is fine too. We will do it both ways in the coming chapters. But, as you begin to see more algorithms, you will probably see code like this, and so it is important to understand why it is correct.

Exercises

5.4.1. Write a function

password()

that asks for a username and a password. It should return True if the username is entered as alan.turing and the password is entered as notTouring, and return False otherwise.

5.4.2. Suppose that in a game that you are making, the player wins if her score is at least 100. Write a function

hasWon(score)

that returns True if she has won, and False otherwise.

5.4.3. Suppose you have designed a sensor that people can wear to monitor their health. One task of this sensor will be to monitor body temperature: if it falls outside the range 97.9° F to 99.3° F, the person may be getting sick. Write a function

monitor(temperature)

that takes a temperature (in Fahrenheit) as a parameter, and returns True if temperature falls in the healthy range and False otherwise.

5.4.4. Write a function

winner(score1, score2)

that returns 1 or 2, indicating whether the winner of a game is Player 1 or Player 2. The higher score wins and you can assume that there are no ties.

5.4.5. Repeat the previous exercise, but now assume that ties are possible. Return 0 to indicate a tie.

5.4.6. Your firm is looking to buy computers from a distributor for $1500 per machine. The distributor will give you a 5% discount if you purchase more than 20 computers. Write a function

cost(quantity)

that takes as a parameter the quantity of computers you wish to buy, and returns the cost of buying them from this distributor.

5.4.7. Repeat the previous exercise, but now add three additional parameters: the cost per machine, the number of computers necessary to get a discount, and the discount.

5.4.8. The speeding ticket fine in a nearby town is $50 plus $5 for each mph over the posted speed limit. In addition, there is an extra penalty of $200 for all speeds above 90 mph. Write a function

fine(speedLimit, clockedSpeed)

that returns the fine amount (or 0 if clockedSpeed ≤ speedLimit).

5.4.9. Write a function

gradeRemark()

that prompts for a grade, and then returns the corresponding remark (as a string) from the table below:

5.4.10. Write a function that takes two integer values as parameters and returns their sum if they are not equal and their product if they are.

5.4.11. Write a function

amIRich(amount, rate, years)

that accumulates interest on amount dollars at an annual rate of rate percent for a number of years. If your final investment is at least double your original amount, return True; otherwise, return False.

5.4.12. Write a function

max3(a, b, c)

the returns the maximum value of the parameters a, b, and c. Be sure to test it with many different numbers, including some that are equal.

5.4.13. Write a function

shipping(amount)

that returns the shipping charge for an online retailer based on a purchase of amount dollars. The company charges a flat rate of $6.95 for purchases up to $100, plus 5% of the amount over $100.

5.4.14. Starting with two positive integers a and b, consider the sequence in which the next number is the digit in the ones place of the sum of the previous two numbers. For example, if a = 1 and b = 1, the sequence is

1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, ...

Write a function

mystery(a, b)

that returns the length of the sequence when the last two numbers repeat the values of a and b for the first time. (When a = 1 and b = 1, the function should return 62.)

5.4.15. The Chinese zodiac relates each year to an animal in a twelve-year cycle. The animals for the most recent years are given below.

Write a function

zodiac(year)

that takes as a parameter a four-digit year (this could be any year in the past or future) and returns the corresponding animal as a string.

5.4.16. A year is a leap year if it is divisible by four, unless it is a century year in which case it must be divisible by 400. For example, 2012 and 1600 are leap years, but 2011 and 1800 are not. Write a function

leap(year)

that returns a Boolean value indicating whether the year is a leap year.

5.4.17. Write a function

even(number)

that returns True if number is even, and False otherwise.

5.4.18. Write a function

between(number, low, high)

that returns True if number is in the interval [low, high] (between (or equal to) low and high), and False otherwise.

5.4.19. Write a function

justone(a, b)

that returns True if exactly one (but not both) of the numbers a or b is 10, and False otherwise.

5.4.20. Write a function

roll()

that simulates rolling two of the loaded dice implemented in Exercise 5.1.3 (by calling the function loaded), and returns True if the sum of the dice is 7 or 11, or False otherwise.

5.4.21. The following function returns a Boolean value indicating whether an integer number is a perfect square. Rewrite the function in one line, taking advantage of the short-circuit evaluation of and expressions.

def perfectSquare(number):
    if number < 0:
        return False
    else:
        return math.sqrt(number) == int(math.sqrt(number))

5.4.22. Consider the rwMonteCarlo function on Page 193. What will the function return if trials equals 0? What if trials is negative? Propose a way to deal with these issues by adding statements to the function.

5.4.23. Write a Boolean expression that is True if and only if the point (x, y) resides in the shaded box below (including its boundary).

5.4.24. Use a truth table to show that the Boolean expressions

(x > d and y > d) or (x < -d and y > d)

and

(y > d) and (x > d or x < -d)

are equivalent.

5.4.25. Write a function

drawRow(tortoise, row)

that uses turtle graphics to draw one row of an 8 × 8 red/black checkerboard. If the value of row is even, the row should start with a red square; otherwise, it should start with a black square. You may want to use the drawSquare function you wrote in Exercise 3.3.5. Your function should only need one for loop and only need to draw one square in each iteration.

5.4.26. Write a function

checkerBoard(tortoise)

that draws an 8 × 8 red/black checkerboard, using the function you wrote in Exercise 5.4.25.

1. Ending the game if we win

Our current for loop, like all for loops, iterates a prescribed number of times. Instead, we want the loop to only iterate for as long as we need another guess. So this is another instance that calls for a while loop. Recall that a while loop iterates while some Boolean condition is true. In this case, we need the loop to iterate while we have not guessed the secret number, in other words, while myGuess != secretNumber. But we also need to stop when we have used up all of our guesses, counted in our current function by the index variable guesses. So we also want our while loop to iterate while guesses < maxGuesses. Since both of these conditions must be true for us to keep iterating, our desired while loop condition is:

while (myGuess != secretNumber) and (guesses < maxGuesses):

Because we are replacing our for loop with this while loop, we will now need to manage the index variable manually. We do this by initializing guesses = 0 before the loop and incrementing guesses in the body of the loop. Here is the function with these changes:

def guessingGame(maxGuesses):
    """ (docstring omitted) """
 
    secretNumber = random.randrange(1, 101)
    myGuess = 0
    guesses = 0
    while (myGuess != secretNumber) and (guesses < maxGuesses):
        myGuess = input('Please guess my number: ')
        myGuess = int(myGuess)
        guesses = guesses + 1          # increment # of guesses
        if myGuess == secretNumber:    # win
            print('You got it!')
        else:                          # try again
            print('Nope. Try again.')

If we comment out myGuess = 0, we will see the following error on the line containing the while loop:

UnboundLocalError: local variable 'myGuess' referenced before assignment

This error means that we have referred to an unknown variable named myGuess. The name is unknown to the Python interpreter because we had not defined it before it was first referenced in the while loop condition. Therefore, we need to initialize myGuess before the while loop, so that the condition makes sense the first time it is tested. To make sure the loop iterates at least once, we need to initialize myGuess to a value that cannot be the secret number. Since the secret number will be at least 1, 0 works for this purpose. This logic can be generalized as one of two rules to always keep in mind when designing an algorithm with a while loop:

1. Initialize the condition before the loop. Always make sure that the condition makes sense and will behave in the intended way the first time it is tested.

2. In each iteration of the loop, work toward the condition eventually becoming false. Not doing so will result in an infinite loop.

To ensure that our condition will eventually become false, we need to understand when this happens. For the and expression in the while loop to become false, either (myGuess != secretNumber) must be false or (guesses < maxGuesses) must be false.

Prompting for a new guess creates the opportunity for the first part to become false, while incrementing guesses ensures that the second part will eventually become false. Therefore, we cannot have an infinite loop.

This reasoning is enshrined in the first of De Morgan’s laws, named after 19th century British mathematician Augustus De Morgan. De Morgan’s two laws are:

1. not (a and b) = not a or not b

2. not (a or b) = not a and not b

You may recognize these from Exercises 1.4.10 and 1.4.11. The first law says that a and b is false if either a is false or b is false. The second law says that a or b is false if both a is false and b is false. Applied to our case, the first law tells us that the negation of our while loop condition is

(myGuess == secretNumber) or (guesses >= maxGuesses)

This is just a more formal way of deriving what we already concluded.

2. Friendly hints

Inside the loop, we currently handle two cases: (1) we win, and (2) we do not win but get another guess. To be friendlier, we should split the second case into two: (2a) our guess was too low, and (2b) our guess was too high. We can accomplish this by replacing the not-so-friendly print('Nope. Try again.') with another if/else that decides between the two new subcases:

if myGuess == secretNumber:                   # win
    print('You got it!')
else:                                         # try again
    if myGuess < secretNumber:                # too low
        print('Too low. Try again.')
    else:                                     # too high
        print('Too high. Try again.')

Now, if myGuess == secretNumber is false, we execute the first else clause, the body of which is the new if/else construct. If myGuess < secretNumber is true, we print that the number is too low; otherwise, we print that the number is too high.

The conditional construct above is really just equivalent to a decision between three disjoint possibilities: (a) the guess is equal to the secret number, (b) the guess is less than the secret number, or (c) the guess is greater than the secret number. In other words, it is equivalent to:

if myGuess == secretNumber:            # win
    print('You got it!')
elif myGuess < secretNumber:           # too low
    print('Too low. Try again.')
else:                                  # too high
    print('Too high. Try again.')

3. Printing a proper win/lose message

Now inside the loop, we currently handle three cases: (a) we win, and (b) our guess is too low and we get another guess, and (c) our guess is too high and we get another guess. But we are missing the case in which we run out of guesses. In this situation, we want to print something like 'Too bad. You lose.' instead of one of the “try again” messages.

In the game, if we incorrectly use our last guess, then two things must be true just before the if condition is tested: first, myGuess is not equal to secretNumber and, second, guesses is equal to maxGuesses. So we can incorporate this condition into the if/elif/else:

if (myGuess != secretNumber) and (guesses == maxGuesses): # lose
    print('Too bad. You lose.')
elif myGuess == secretNumber:       # win
    print('You got it!')
elif myGuess < secretNumber:        # too low
    print('Too low. Try again.')
else:                               # too high
    print('Too high. Try again.')

Notice that we have made the previous first if condition into an elif statement because we only want one of the four messages to be printed. However, here is an alternative structure that is more elegant:

if myGuess == secretNumber:            # win
    print('You got it!')
elif guesses == maxGuesses:            # lose
    print('Too bad. You lose.')
elif myGuess < secretNumber:           # too low
    print('Too low. Try again.')
else:                                  # too high
    print('Too high. Try again.')

By placing the new condition second, we can leverage the fact that, if we get to the first elif, we already know that myGuess != secretNumber. Therefore, we do not need to include it explicitly.

There is a third way to handle this situation that is perhaps even more elegant. Notice that both of the first two conditions are going to happen at most once, and at the end of the program. So it might make more sense to put them after the loop. Doing so also exhibits a nice parallel between these two events and the two parts of the while loop condition. As we discussed earlier, the negation of the while loop condition is

(myGuess == secretNumber) or (guesses >= maxGuesses)

So when the loop ends, at least one of these two things is true. Notice that these two events are exactly the events that define a win or a loss: if the first part is true, then we won; if the second part is true, we lost. So we can move the win/loss statements after the loop, and decide which to print based on which part of the while loop condition became false:

if myGuess == secretNumber:            # win
    print('You got it!')
else:                                  # lose
    print('Too bad. You lose.')

In the body of the loop, with these two cases gone, we will now need to check if we still get another guess (mirroring the while loop condition) before we print one of the “try again” messages:

if (myGuess != secretNumber) and (guesses < maxGuesses):
    if myGuess < secretNumber:          # too low
        print('Too low. Try again.')
    else:                               # too high
        print('Too high. Try again.')

if (myGuess != secretNumber) and (guesses < maxGuesses) 
                             and (myGuess < secretNumber):
    print('Too low. Try again.')
else:
    print('Too high. Try again.')

Hint: what does the function print when guesses < maxGuesses is false and myGuess < secretNumber is true?

These changes are incorporated into the final game that is shown below.

import random
 
def guessingGame(maxGuesses):
    """ (docstring omitted) """
 
      secretNumber = random.randrange(1, 101)
      myGuess = 0
      guesses = 0
      while (myGuess != secretNumber) and (guesses < maxGuesses):
          myGuess = input('Please guess my number: ')
          myGuess = int(myGuess)
          guesses = guesses + 1         # increment # of guesses used
 
         if (myGuess != secretNumber) and (guesses < maxGuesses):
             if myGuess < secretNumber:          # guess is too low
                 print('Too low. Try again.')    #   give a hint
             else:                               # guess is too high
                 print('Too high. Try again.')   #     give a hint
 
      if myGuess == secretNumber:      # win
          print('You got it!')
      else:                            # lose
          print('Too bad. You lose.')
 
def main():
    guessingGame(10)
 
main()

As you play the game, think about what the best strategy is. How many guesses do different strategies require? Exercise 5.5.7 asks you to write a Monte Carlo simulation to compare three different strategies for playing the game.

Exercises

5.5.1. Write a function

ABC()

that prompts for a choice of A, B, or C and uses a while loop to keep prompting until it receives the string 'A', 'B', or 'C'.

5.5.2. Write a function

numberPlease()

that prompts for an integer between 1 and 100 (inclusive) and uses a while loop to keep prompting until it receives a number within this range.

5.5.3. Write a function

differentNumbers()

that prompts for two different numbers. The function should use a while loop to keep prompting for a pair of numbers until the two numbers are different.

5.5.4. Write a function

rockPaperScissorsLizardSpock(player1, player2)

that decides who wins in a game of rock-paper-scissors-lizard-Spock¹. Each of player1 and player2 is a string with value 'rock', 'paper', 'scissors', 'lizard', or 'Spock'. The function should return the value 1 if player 1 wins, -1 if player 2 wins, or 0 if they tie. Test your function by playing the game with the following main program:

def main():
    player1 = input('Player1: ')
    player2 = input('Player2: ')
 
     outcome = rockPaperScissorsLizardSpock(player1, player2)
 
     if outcome == 1:
         print('Player 1 wins!')
     elif outcome == -1:
         print('Player 2 wins!')
     else:
         print('Player 1 and player 2 tied.')

5.5.5. Write a function

yearsUntilDoubled(amount, rate)

that returns the number of years until amount is doubled when it earns the given rate of interest, compounded annually. Use a while loop.

5.5.6. The hailstone numbers are a sequence of numbers generated by the following simple algorithm. First, choose any positive integer. Then, repeatedly follow this rule: if the current number is even, divide it by two; otherwise, multiply it by three and add one. For example, suppose we choose the initial integer to be 3. Then this algorithm produces the following sequence:

3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1 ...

For every initial integer ever tried, the sequence always reaches one and then repeats the sequence 4, 2, 1 forever after. Interestingly, however, no one has ever proven that this pattern holds for every integer!

Write a function

hailstone(start)

that prints the hailstone number sequence starting from the parameter start, until the value reaches one. Your function should return the number of integers in your sequence. For example, if n were 3, the function should return 8. (Use a while loop.)

5.5.7. In this exercise, we will design a Monte Carlo simulation to compare the effectiveness of three strategies for playing the guessing game. Each of these strategies will be incorporated into the guessing game function we designed in this chapter, but instead of checking whether the player wins or loses, the function will continue until the number is guessed, and then return the number of guesses used. We will also make the maximum possible secret number a parameter, so that we can compare the results for different ranges of secret numbers.

The first strategy is to just make a random guess each time, ignoring any previous guesses:

def guessingGame1(maxNumber):
    """Play the guessing game by making random guesses."""
 
     secretNumber = random.randrange(1, maxNumber + 1)
     myGuess = 0
     guesses = 0
     while (myGuess != secretNumber):
         myGuess = random.randrange(1, maxNumber + 1)
         guesses = guesses + 1
 
     return guesses

The second strategy is to incrementally try every possible guess from 1 to 100, thereby avoiding any duplicates:

def guessingGame2(maxNumber):
    """Play the guessing game by making incremental guesses."""
 
     secretNumber = random.randrange(1, maxNumber + 1)
     myGuess = 0
     guesses = 0
     while (myGuess != secretNumber):
         myGuess = myGuess + 1
         guesses = guesses + 1
 
     return guesses

Finally, the third strategy uses the outcomes of previous guesses to narrow in on the secret number:

def guessingGame3(maxNumber):
    """Play the guessing game intelligently by narrowing in
       on the secret number."""
 
     secretNumber = random.randrange(1, maxNumber + 1)
     myGuess = 0
     low = 1
     high = maxNumber
     guesses = 0
     while (myGuess != secretNumber):
         myGuess = (low + high) // 2
         guesses = guesses + 1
 
          if myGuess < secretNumber:
              low = myGuess + 1
          elif myGuess > secretNumber:
              high = myGuess - 1
 
     return guesses

Write a Monte Carlo simulation to compare the expected (i.e., average) behavior of these three strategies. Use a sufficiently high number of trials to get consistent results. Similarly to what we did in Section 5.1, run your simulation for a range of maximum secret numbers, specifically 5, 10, 15, ..., 100, and plot the average number of guesses required by each strategy for each maximum secret number. (The x-axis of your plot will be the maximum secret number and the y-axis will be the average number of guesses.) Explain the results. In general, how many guesses on average do you think each strategy requires to guess a secret number between 1 and n?

Project 5.1 The magic of polling

According to the latest poll, the president’s job approval rating is at 45%, with a margin of error of ±3%, based on interviews with approximately 1,500 adults over the weekend.

We see news headlines like this all the time. But how can a poll of 1,500 randomly chosen people claim to represent the opinions of millions in the general population? How can the pollsters be so certain of the margin of error? In this project, we will investigate how well random sampling can really estimate the characteristics of a larger population. We will assume that we know the true percentage of the overall population with some characteristic or belief, and then investigate how accurate a much smaller poll is likely to get.

Suppose we know that 30% of the national population agrees with the statement, “Animals should be afforded the same rights as human beings.” Intuitively, this means that, if we randomly sample ten individuals from this population, we should, on average, find that three of them agree with the statement and seven do not. But does it follow that every poll of ten randomly chosen people will mirror the percentage of the larger population? Unlike a Monte Carlo simulation, a poll is taken just once (or maybe twice) at any particular point in time. To have confidence in the poll results, we need some assurance that the results would not be drastically different if the poll had queried a different group of randomly chosen individuals. For example, suppose you polled ten people and found that two agreed with the statement, then polled ten more people and found that seven agreed, and then polled ten more people and found that all ten agreed. What would you conclude? There is too much variation for this poll to be credible. But what if we polled more than ten people? Does the variation, and hence the trustworthiness, improve?

In this project, you will write a program to investigate questions such as these and determine empirically how large a sample needs to be to reliably represent the sentiments of a large population.

poll(percentage, pollSize)

pollExtremes(percentage, pollSize, trials)

return min(pollResults), max(pollResults)

plotResults(percentage, minPollSize, maxPollSize, step, trials)

low, high = pollExtremes(percentage, pollSize, trials)

plotErrors(pollSize, minPercentage, maxPercentage, step, trials)

Project 5.2 Escape!

In some scenarios, movement of the “particle” in a random walk is restricted to a bounded region. But what if there is a small opening through which the particle might escape or disappear? How many steps on average does it take the particle to randomly come across this opening and escape? This model, which has become known as the narrow escape problem, could represent a forager running across a predator on the edge its territory, an animal finding an unsecured gate in a quarantined area, a molecule finding its way through a pore in the cell membrane, or air molecules in a hot room escaping through an open door.

escape(openingDegrees, tortoise, draw)

def angle(x, y):
    if x == 0:       # avoid dividing by zero
        x = 0.001
    angle = math.degrees(math.atan(y / x))
    if angle < 0:
        if y < 0:
            angle = angle + 360   # quadrant IV
        else:
            angle = angle + 180   # quadrant II
    elif y < 0:
        angle = angle + 180       # quadrant III
    return angle

def escape(openingDegrees, tortoise, draw):
    x = y = 0                     # initialize (x, y) = (0, 0)
    radius = 1                    # moving in unit radius circle
    stepLength = math.pi / 128    # std dev of each step
 
    if draw:
        scale = 300               # scale up drawing
        setupWalls(tortoise, openingDegrees, scale, radius)
 
    escaped = False               # has particle escaped yet?
    while not escaped:
 
        # random walk and detect wall and opening here
 
        if draw:
            tortoise.goto(x * scale, y * scale)   # move particle
 
    if draw:
        screen = tortoise.getscreen()    # update screen to compensate
        screen.update()                  # for high tracer value
def setupWalls(tortoise, openingDegrees, scale, radius):

    screen = tortoise.getscreen()
    screen.mode('logo')                  # east is 0 degrees
    screen.tracer(5)                     # speed up drawing
 
    tortoise.up()                        # draw boundary with
    tortoise.width(0.015 * scale)        #   shaded background
    tortoise.goto(radius * scale, 0)
    tortoise.down()
    tortoise.pencolor('lightyellow')
    tortoise.fillcolor('lightyellow')
    tortoise.begin_fill()
    tortoise.circle(radius * scale)
    tortoise.end_fill()
    tortoise.pencolor('black')
    tortoise.circle(radius * scale, 360 - openingDegrees)
    tortoise.up()
    tortoise.home()
 
    tortoise.pencolor('blue')      # particle is a blue circle
    tortoise.fillcolor('blue')
    tortoise.shape('circle')
    tortoise.shapesize(0.75, 0.75)
 
    tortoise.width(1)             # set up for walk
    tortoise.pencolor('green')
    tortoise.speed(0)
    tortoise.down()               # comment this out to hide trail

escapeMonteCarlo(openingDegrees, trials)

plotEscapeSteps(minOpening, maxOpening, openingStep, trials)