Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 38 ยท Getting Started

The Law of Large Numbers and Simulation Error

See why Monte Carlo averages converge to the true value, plot running averages, and learn the 1/sqrt(N) rule for simulation error.

Why should an average of random samples be close to the true answer at all? The reason is a theorem called the law of large numbers (LLN). It is the guarantee behind every Monte Carlo method. This lesson states it in plain words, shows it in action, and introduces the error rule you will use in every later chapter.

The law of large numbers

Let Xโ‚, Xโ‚‚, Xโ‚ƒ, โ€ฆ be independent random values that all have the same distribution with mean (expected value) ฮผ. The sample mean is

Text
Xฬ„โ‚™ = (Xโ‚ + Xโ‚‚ + โ€ฆ + Xโ‚™) / n

The law of large numbers says: as n grows, Xฬ„โ‚™ gets closer and closer to ฮผ. (The "strong" version says this happens with probability 1.) Monte Carlo uses it directly: to learn ฮผ, average many samples.

Probabilities are a special case. If X is 1 when an event happens and 0 otherwise, then ฮผ = P(event), and the sample mean is the fraction of times the event happened.

Watching convergence

A running average after k samples uses only the first k values. Plot it against k and you see the wobble die down.

Python Running average of die rolls

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.

The true mean of a fair die is (1+2+3+4+5+6)/6 = 3.5. Early on the line jumps around; later it hugs 3.5. Note that the average converges, but individual rolls stay as random as ever.

The law of large numbers does not say that streaks "even out". After ten heads in a row, the next flip is still 50/50. The average converges because new data dilutes old data, not because the coin compensates.

How fast? The standard error

Convergence needs a speed. Let ฯƒ be the standard deviation of one sample (a measure of how spread out single values are). Then the typical size of the error of the sample mean, called the standard error, is

Text
SE = ฯƒ / โˆšn

Two facts follow:

  • More spread in single samples (larger ฯƒ) means larger error.
  • Error shrinks like 1/โˆšn. To halve the error you need 4 times as many samples; for 10 times smaller error, 100 times as many.

For a probability estimate pฬ‚ the single-sample variance is p(1-p), so SE = โˆš(p(1-p)/n).

Measuring the error by repetition

You can see the standard error by repeating the whole experiment many times and looking at how much the answers vary.

Python Spread of estimates versus N

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.

Each time N is multiplied by 4, the spread should about halve. The observed and theoretical columns agree closely, which confirms SE = ฯƒ/โˆšn.

Estimating the error from a single run

In real work you run the simulation once, so you cannot repeat it 2,000 times. Instead you estimate ฯƒ from the samples themselves (the sample standard deviation) and compute SE = s / โˆšn.

Python Mean and standard error from one run

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.

The interval estimate ยฑ 2 SE should contain the true value 7 in roughly 95% of runs. The next lesson turns this into a proper confidence interval.

Bias and variance

An estimator can fail in two ways.

  • Variance: the estimates scatter from run to run. More samples fix this.
  • Bias: the estimates are off on average, for example because of a coding bug or a wrong model. More samples do not fix bias.

Always ask: is my estimator unbiased, meaning its average over many runs equals the true value? The sample mean is unbiased; many cleverly modified estimators are not.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the law of large numbers say about the sample mean?

    For independent, identically distributed samples with a finite mean, the sample mean converges to that mean as n grows.
  2. 2. The standard error of a sample mean is ฯƒ / โˆšn. If you quadruple n, the standard error is multiplied by

    โˆš4 = 2, so the standard error is divided by 2.
  3. 3. A coin lands heads 8 times in a row. According to the law of large numbers, the next flip

    Flips are independent. The running average converges because later data dilutes early data, not because the coin compensates.
  4. 4. Which problem is NOT fixed by simply increasing the number of samples?

    A biased estimator converges to the wrong value; more samples only make you more confident in it.

Summary

  • The law of large numbers: sample means converge to the true mean as n grows.
  • Standard error ฯƒ/โˆšn measures the typical size of the error; you can estimate ฯƒ by the sample standard deviation.
  • Quadrupling the samples halves the error.
  • Variance shrinks with more samples; bias does not.
  • Streaks do not "even out"; averages converge by dilution.

Next: Confidence Intervals for Monte Carlo Estimates