CS(3) Monte Carlo Convergence and the Law of Large Numbers

Almost Sure Convergence

Concept of Almost Sure Convergence and the Law of Large Numbers

The Law of Large Numbers (LLN) is a key principle that explains why the Monte Carlo method works. It states that as the number of samples increases, the sample average will “almost sure”, or with a probability of 1, converge to the true expected value of the function.

In Monte Carlo integration, this means that our estimates of an integral become more accurate as we increase the number of samples. This convergence “almost surely” ensures that, although individual samples are random, the average will get closer and closer to the actual value as the sample size grows.

Observing the convergence with increasing samples

Let’s return to the integral of

over the interval [0,1] as an example as we have seen in article 1 of this series. We will calculate the Monte Carlo estimate for this integral, gradually increasing the number of samples, and observe how the estimate approaches the exact value.

The integral we want to estimate is: