Computer Science 15-112, Fall 2011
Class Notes: Monte Carlo Methods

• Monte Carlo Methods:
• Definition:
• Using (pseudo)random numbers to solve (not-so-random) 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.
• Time-Accuracy 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.
  
• Dice Throwing Tables (see diceThrowing.py and betterDiceThrowing.py)
  Here we compute the odds of getting various sums by rolling different numbers of different-sided dice (say, rolling 4 5-sided 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.

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem