🤔 Monte Carlo Sampling

Optimization and inference often require computing intractable sums or integrals, sometimes due to expectations. If they have an infeasible or exponential number of terms, we approximate them instead with Monte Carlo sampling.

The core idea is to view the sum or integral as an expectation over some distribution:

We can approximate this expectation by drawing samples from and computing the empirical average,

Note

We use the empirical average since it's unbiased and, by the law of large numbers, converges to the actual value as goes to infinity.

We can also calculate the variance of our estimate,

Our empirical average thus follows a normal distribution with mean and variance , so we can estimate confidence intervals.