Homework 7: Monte Carlo and Friends

Assigned
Friday September 30, 2016
Due
11 p.m., Tuesday October 4, 2016
Summary
The goal of this assignment is to get more experience with while loops, conditionals, random numbers, and accumulators.
Collaboration
Do this assignment with your assigned partner.
Submitting
Submit a Python program using the online turnin form. See below.
Scoring
16 points

Assignment

Create a file named montecarlo.py in which you will write your code. Write the following functions:

Part 1. Estimating π

It turns out that we can estimate the value of π using random numbers. Consider the following image:


Throwing darts at a 1 x 1 square allows us to estimate pi. In particular, the number of darts that fall within a circle centered on the origin estimates pi over four.

The idea is that we know the area of a circle is given by the expression A = π r2. The circle in the image has radius 1, so the circle’s area is just π. One quarter of the circle’s area is then π/4. If we choose enough random points in the square, then the fraction of them that fall inside the circle gives us π/4, which we can then multiply by 4 to estimate π.

Here is the pseudocode for the idea:

Do N times:
Generate two random numbers, x and y, between 0 and 1
If they are within the circle (i.e. the sum of their squares is less than 1), then count it as a hit

Multiply the count of hits by 4, and divide by N

Write a function pi_est(N) that will run this algorithm for N iterations and return the estimated value of π.

Note: For a different explanation of this problem, you can check out problem 5.1.6 in the textbook.

Part 2. Estimating sequence probabilities

Sometimes writing simulations can be helpful in finding answers to complex probability questions. For example, a question such as “how many times, on average, do I need to flip a coin to get 6 heads in a row?” is quite difficult to calculate. But we can simulate this situation.

  1. Write a function flip() that simulates a fair coin flip. Half the time, it should return 1 for heads. Half the time, it should return 0 for tails.
  2. Write a function six_heads() that will simulate flipping a coin until six heads in a row are seen. Then return the number of total flips. Your code should call the flip() function you just wrote.
  3. Write a function average_six(n) that will run your six_heads function n times and calculate the average of the results, and return that.

Part 3. Simulating strange behavior

  1. Write a function hhh() that will flip a coin until it gets three heads in a row. Return the total number of  flips (including the last three).
  2. Write another function hht() that will flip a coin until it gets heads followed by heads followed by tails. Again, return the total number of  flips (including the last three).
  3. Write a third function simulate_flips(n) that will call each of the previous functions n times and calculate the average number of coin flips required for each situation. Have this function print out the results.
Note: Did the average numbers of flips differ for these two situations? Does that make sense? Drawing a finite state machine (p. 27) may help you understand what is happening.

Submitting your work

Please document your functions and organize your code per section 3.4 of the textbook.

I expect that you will write a main() function to test the functions specified above. Before submitting, however, please delete your call to main().

Submit one file, montecarlo.py, using the turnin form.

Point distribution


Janet Davis (davisj@whitman.edu).
This assignment was developed with Andy Exley based on exercises in the textbook.

Created September 29, 2016
Last revisedSeptember 30, 2016, 10:53:05 AM PDT
CC-BY-NC-SA This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.