Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 46 ยท Stochastic Models and Simulation

Monte Carlo methods

Use Monte Carlo simulation to estimate pi, project schedule risk and the birthday-problem probability, and learn why the error shrinks like one over root N.

Some questions are painful to solve with formulas but easy to play out. What is the chance that two people in a room of 23 share a birthday? How likely is a three-task project to finish by day 30? Instead of deriving the answer, you can let a computer run the situation thousands of times with random inputs and count how often the event happens. This is the Monte Carlo method, named after the casino in Monaco by Stanislaw Ulam, John von Neumann and Nicholas Metropolis, who used it in the 1940s at Los Alamos.

Random points in a unit square; points inside the quarter circle are indigo and the others pink; a card shows the count and the pi estimate.
Throw random darts at the square. The fraction landing inside the quarter circle estimates pi/4.

What you will learn

  • The Monte Carlo recipe: simulate, count, divide.
  • Why the error shrinks like 1/โˆšN, so 100 times more runs give only 10 times more accuracy.
  • How to use simulation for risk: percentiles and probabilities of bad outcomes.
  • How to check a simulation against an exact formula.

Key terms

Monte Carlo method: estimating a quantity by averaging the results of many random simulations.

Law of large numbers: averages of many independent samples approach the true expected value.

Standard error: the typical size of the error in an estimate, ฯƒ/โˆšN for the mean of N samples.

Percentile: the value below which a given fraction of the outcomes fall.

Estimating ฯ€ with darts

The quarter circle of radius 1 in the unit square has area ฯ€/4; the square has area 1. If you throw N darts uniformly at the square, the fraction that lands inside the circle (where xยฒ + yยฒ < 1) should be about ฯ€/4. So ฯ€ โ‰ˆ 4 ร— (number inside) / N.

In the picture, 400 points gave 311 hits and an estimate of 4 ร— 311/400 = 3.11: close but not great. This is typical. Each dart is a coin flip with success probability p = ฯ€/4 โ‰ˆ 0.785. The count of hits has standard deviation โˆš(Nยทp(1โˆ’p)), so the estimate of ฯ€ has standard deviation 4ยทโˆš(p(1โˆ’p)/N) โ‰ˆ 1.64/โˆšN. With N = 400 that is about 0.08, so 3.11 is within one standard error of the truth.

The 1/โˆšN rule is the main fact of Monte Carlo. To gain one more correct decimal digit you need 100 times more samples. That is a slow rate, but it does not depend on how many dimensions the problem has, which is why Monte Carlo is the tool of choice for hard, high-dimensional integrals.

Python Estimating pi and watching the error shrink

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Monte Carlo for risk

Here is a use that exact formulas handle badly. A small project has three tasks in sequence. Durations are uncertain, so we describe each by a minimum, a most likely value and a maximum (a triangular distribution):

Task Min Most likely Max
A: design 5 days 8 14
B: build 10 12 20
C: test 4 6 9

A plan that adds the most likely durations says 8 + 12 + 6 = 26 days. But each distribution is skewed to the right (long delays are more likely than big savings), so the average total is (5+8+14)/3 + (10+12+20)/3 + (4+6+9)/3 = 29.33 days, about three days longer than the plan. Simulation answers questions that no single number can: what is the chance of finishing within 26 days, within 30, and what deadline can we promise with 90 percent confidence?

Python Schedule risk by simulation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common misconceptions

"More simulations always make the model more correct." They make the estimate more precise, but not the model more truthful. If the input distributions are wrong, 10 million runs will give a very precise wrong answer.

"A random seed makes the numbers less random." A seed fixes the sequence so you can reproduce it. The sequence still behaves like random draws, and you should test several seeds.

"One simulation of 1,000 runs is enough to see rare events." An event with probability 1 in 10,000 will appear in only 0.1 of your runs on average. For rare events you need far more runs or special techniques.

The birthday problem

In a group of n people, what is the probability that at least two share a birthday (ignoring 29 February and assuming all days are equally likely)? The exact answer is 1 โˆ’ (365/365)(364/365)ยทยทยท((365โˆ’n+1)/365). For n = 23 it is 50.7 percent, which surprises most people. Simulation reproduces it with a few lines of code and gives you a way to check your reasoning, a habit worth keeping even when you know a formula.

Python Birthdays: simulation against the exact formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the dart method, what does 4 * (hits / N) estimate?

    The hit fraction estimates the area ratio pi/4, so four times it estimates pi.
  2. 2. To reduce the typical Monte Carlo error by a factor of 10, how many more samples do you need?

    The error scales like 1/sqrt(N), so 10 times less error needs 100 times more samples.
  3. 3. Why is the average project duration longer than the sum of the most likely durations?

    Right-skewed distributions have a mean above their mode, and the sum inherits that skew.
  4. 4. What is the 90th percentile of the simulated project duration?

    A percentile is the value that a given fraction of outcomes fall below.
  5. 5. What does running 10 million simulations NOT fix?

    More runs reduce sampling error but cannot repair a flawed model.

Summary

  • Monte Carlo estimates quantities by averaging many random simulations.
  • Error shrinks like 1/โˆšN: 100 times more runs for one more digit.
  • Simulation answers risk questions: probabilities, percentiles and tails.
  • Check simulations against exact answers when you have them; more runs never fix a bad model.

Next: Random walks and Markov chains