15-110 Summer 2017

Lab 10


For this lab you will work with Monte Carlo methods to estimate the answers to questions about a simple problem involving baking cookies. When you are done, you should be able to do the following:
  1. Use randrange() to randomly generate integers in a given range
  2. Distinguish between the simulation and estimation parts of a Monte Carlo method
  3. Use an error range to control the estimate of an expected value by repeated trials


  1. raisins.py

Place this file in a lab9 folder. Before leaving lab, zip up the lab9 folder and hand the zip file in.

The Monte Carlo Method

The Monte Carlo method is a computational technique that works by calculating a statistical summary of a large number of random operations. In this lab, we will use the Monte Carlo method to estimate the outcome of a stochastic process.

Suppose you want to make a batch of 25 raisin cookies. How many raisins should you use to make sure nearly every cookie has at least 1 raisin? Assume that raisins are randomly distributed in the batter, so each raisin is equally likely to go into each cookie.

CA-Led Activities/Demonstration


All of your work should go into the file raisins.py.

PART I. Make a function named make_batch(num_cookies, num_raisins) that returns True if and only if every one of num_cookies cookies has at least 1 raisin. Implement the function as follows:

  1. Create a list of num_cookies zeros. This list represents a set of counters that keep track of the number of raisins in each cookie.
  2. Distribute the raisins randomly (do this num_raisins times):
  3. Does every cookie have a raisin?

PART II. Make a function monte_carlo(num_cookies, num_raisins) to estimate the probability that every cookie will have at least one raisin:

  1. Set count = 0
  2. Do this 1000 times:
  3. After the loop, return the fraction of times every cookie has at least one raisin: count / 1000.
Call monte_carlo(25, 100) to estimate the probability that every cookie in a batch of 25 cookies will have at least 1 raisin if there are 100 raisins in all.

Call monte_carlo(25, 100) again. Make sure you understand why you do not get the same answer.

PART III. Now we want to answer a different question: how many raisins do we have to use to get a good probability that every cookie has a raisin? Write a function raisins_needed(num_cookies, error). The idea is to start with the same number of raisins as cookies (we need at least that many), and call monte_carlo to get the probability that every cookie has a raisin. Keep increasing the number of raisins until the answer from monte_carlo is close enough to 1 (certainty). The uncertainty to allow is given by error. For example, an error of 0.1 means that we want an answer with certainty of 99%.

The algorithm:

  1. Set num_raisins = num_cookies
  2. Set diff to 1 - monte_carlo(num_cookies, num_raisins)
  3. While diff is greater than error, increase num_raisins by one and recalculate diff as above
  4. Once diff is less than or equal to error, return num_raisins

Example (note that for large numbers of cookies and/or small error values this will take a while to run):

>>> raisins_needed(1, .1)
>>> raisins_needed(2, .1)
>>> raisins_needed(10, .1)

Acknowledgement: The raisin cookie problem was suggested by Greg Kochanski.