Monte Carlo Algorithm
Resources
Purpose
Understand the random nature of Monte Carlo Algorithms and how they are written.
Overview
Sometimes the best way to approach a problem is to allow it to chance. Monte Carlo uses probability models and couples it with weights to run the problem many times to determine the correct outcome within a certain margin of error. In this project, we will find an estimate of the value of pi given a series of random numbers, several iterations, and a circle.
Vocabulary
Probability- How likely an event is to occur, typically determined after many repeated trials.
Uniform Distribution- A probability distribution where every value has an equal probability.
Random number seed- A number used to initialize a random number generator to get a specified set of random numbers so the results are the same across runs.
Monte Carlo Algorithm- a randomized algorithm that gives an answer with a specified amount of uncertainty within a determinate amount of time.
Getting Started
Pi can easily calculated by the Leibniz series using, where k is a positive integer:
However, given our limitation to finite numbers in computers, we cannot have an upper limit of infinity in our sum. Therefore, Monte Carlo comes in handy with estimating the value of pi. By inscribing a circle into a square, we can “drop” random points onto the square and see if it is within the circle, estimating pi to be:
Watch this video to understand the derivation a bit more: Approximating Pi
Activities
Write a function in StudentAnswer.py that:
1. Uses a random seed.
2. Generates an x and y value for a point based off a random uniform distribution from -1 to 1.
3. Calculates the distance from the point to the center of the circle at (0,0)
4. Determines if the distance is within the radius of the circle.
a. If it is add the x,y value pair to circle_val.
b. Otherwise, add the x,y pair to no_circle
5. Run the program for n number of times.
Discussion:
Set the seed to 5 and the number of iterations to 500.
What is the runtime?
What is the estimate of pi?
Restart the program and set the seed to 42 and the number of iterations to 500.
What is the runtime?
What is the estimate of pi?
What difference does the seed make?
Restart the program and set the seed to 5 and the number of iterations to 12.
What is the runtime?
What is the estimate of pi?
Restart the program and set the seed to 5 and the number of iterations to 10,000.
What is the runtime?
How many points does it generate?
Restart the program and set the seed to 5 and the number of iterations to 100,000.
What is the runtime?
What is the estimate of pi?
What difference does the radius make?
Find the point of diminishing return (when does the number of iterations hurt the estimation of pi).
Assessment Questions:
What is Monte Carlo?
Does the seed impact the runtime?
Does the seed impact the estimate of pi?
Does the number of iterations impact the runtime?
Does the number of iterations impact the estimation of pi?
Is there a point of diminishing return?
Is there a point where you get the best estimate of pi and an ok runtime?