CMU 15112: Fundamentals of Programming and Computer Science
Class Notes: Monte Carlo Methods
 Monte Carlo Methods:
 Definition:

Using (pseudo)random numbers to solve (notsorandom) problems.
 General approach
 Run Trials
 In each trial, simulate event (coin toss, dice rolling, etc)
 Count # of successful trials
 Guess that Expected Odds ~= Observed Odds = (successful trials) / (total trials)
 Law of Large Numbers

As total trials increases, observed odds > expected odds.
 TimeAccuracy Tradeoff

More trials == more accurate + more time
 Examples:

Finding pi on a desert isle (see
piOnADesertIsle.py)
Here, we have fun approximating pi by repeatedly throwing a coconut into a circle we inscribed in a square (using a vine we found on the beach). If the coconut throws are random, and we ignore throws that land outside the square, then the odds that a throw lands inside the circle are the ratio of the area of the circle divided by the area of the square, which equals pi/4. So we guess that pi is about 4 times our observed ratio.

Random Run Length (see
randomRunLength.py)
We will say that a "run" of random numbers continues
until you pick one that is smaller than the previous one.
That last number ends the run, and is also counted in the run
(so the shortest possible run length is 2).
With this definition, what is the expected length of
a run of random numbers?

Dice Throwing Tables (see
diceThrowing.py and
betterDiceThrowing.py)
Here we compute the odds of getting various sums by rolling different numbers of differentsided dice (say, rolling 4 5sided dice). There are many web resources to check your answer, such as this one (chosen randomly).

The Birthday Problem (see
birthdayProblem.py)
And here we solve the famous birthday problem: how many people must be in a room so that it is more likely than not that at least two of them share a birthday (same day and month, not necessarily year; and we ignored leap year birthdays)? You can check your answer at the Wikipedia page on the Birthday Problem.