Monte Carlo methods

What is it?

Why does it exist?

Formulas

$$\int_\Omega f(x)\,\dd x \approx \frac{|\Omega|}{N}\sum_{i=1}^N f(x_i), \qquad \varepsilon_N \approx \frac{\sigma}{\sqrt N}$$

$$\int f(x)\,\dd x = \E_{x\sim q}\Big[\frac{f(x)}{q(x)}\Big]$$

importance sampling

Why does it matter?

The mathematics behind it

• Definite integral★★★★★fundamental

  Monte Carlo estimates $\int f$ as an average of $f$ at random points; error $O(N^{-1/2})$ in any dimension.

• Multiple integrals and change of variables★★★★★fundamental

  Grid quadrature in $d$ dimensions needs $n^d$ points; Monte Carlo's $O(N^{-1/2})$ error does not depend on $d$.

• Cumulative distribution function★★★★★fundamental

  Inverse transform sampling: e.g. $-\ln(1 - U)/\lambda$ is exponential with rate $\lambda$.

• Expectation★★★★★fundamental

  Monte Carlo estimates expectations by sample averages.

• Variance★★★★★fundamental

  MC error is $\sigma/\sqrt N$; variance reduction (importance sampling, control variates) is the main lever.

• Inverse functions★★★★★frequent

  Inverse transform sampling: if $U$ is uniform on $(0,1)$, $F^{-1}(U)$ has distribution $F$.

• Asymptotic notation (O, o, Ω, Θ)★★★★★frequent

  Monte Carlo error is $O(N^{-1/2})$ in any dimension — 100 times more samples for one more digit.

• Continuous random variables★★★★★frequent

  Monte Carlo methods draw samples of continuous random variables to estimate integrals.

• Riemann sums★★★★★frequent

  Monte Carlo integration is a Riemann-like sum with random sample points instead of a grid.

• Integration by substitution★★★★★frequent

  Importance sampling and inverse-transform sampling are changes of variable in the integral being estimated.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

What depends on it

• The rendering equation