From frequencies to probabilities

Frequency, the law of large numbers and simulation

A probability is computed; a frequency is observed. Understanding the link between them — and its limit — prevents the most widespread reasoning errors.

Frequency and probability

                number of times A occurred
frequency of A = ---------------------------      (observed, after the fact)
                   number of experiments

probability of A = theoretical value of the model  (computed, beforehand)

The frequency varies from one run to another; the probability does not. Tossing a coin 100 times may give 47 heads, then 53: the probability stays 0.5.

The law of large numbers

This is the theorem linking the two worlds:

As the number of experiments increases, the observed frequency of an event approaches its probability.

frequency
 of "heads"
   1.0 |
       |  •
   0.5 |----•--•---•----•------•--------•-------------  <- 0.5
       |       •      •     •      •
   0.0 |________________________________________
        10   50   100   500  1000  5000   n (tosses)

  early on: very unstable        later: tight around 0.5

What the law does not say. It does not say that deviations get "made up for". After ten heads in a row, the probability of tails on the next toss is still exactly 0.5: the coin has no memory. Believing otherwise is the gambler's fallacy, the reasoning casinos thrive on.

What stabilises is the frequency — because the first ten tosses weigh less and less in the total, not because any mechanism corrects anything.

Simulating to estimate

When an exact computation is too hard, the experiment can be simulated a large number of times and the resulting frequency read off. This is the Monte Carlo method.

repeat 1,000,000 times:
    draw a random point in the square [0;1] × [0;1]
    count whether it falls inside the quarter disc of radius 1

resulting frequency ≈ area of the quarter disc = π/4    ->  estimate of π

    1 +-------------+
      |  ....       |         proportion of points under the arc
      | ......      |              ≈ π/4 ≈ 0.785
      |.......      |
      |......  .    |         so π ≈ 4 × frequency
    0 +-------------+
      0             1

This idea, born with the first computers, is used today to assess financial risk, simulate reactors and compute integrals that resist formal treatment.

The accuracy of the estimate

A simulation never gives the exact value. Its accuracy improves like 1/√n:

n = 100        ->  accuracy of order 10 %
n = 10,000     ->  about 1 %
n = 1,000,000  ->  about 0.1 %

In other words, gaining one significant digit costs a hundred times more computation. That is the structural limit of the method.

Summary