CMU 15-112: Fundamentals of Programming and Computer Science
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.
  
  
  • 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 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.