Computer Science 15-110, Spring 2011
Monte Carlo Methods

• Monte Carlo Methods:
• Definition:
• Using (pseudo)random numbers to solve (not-so-random) problems.
• Application Areas
• See here
  
• 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 ouside 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)
  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.
  
  
• The Gambler's Ruin (see gamblersRuin.py)
  This problem dates back to Christian Huygens, who also invented the pendulum clock and discovered the mathematical properties of pendulums that we recently studied.  He discovered this seeming paradox:  if you play a fair game with a finite bankroll against an opponent with an infinite bankroll, you will eventually  lose all your money.  That is, fair games, played long enough, are losing games.  This also relates to random walks, Brownian motion, and diffusion (do you see how?).  Here we will write a program that explores this principle.  For more information, see the Wikipedia page on the Gambler's Ruin.

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