Monte-Carlo Estimation

Created December 26, 2020 · Updated August 5, 2025

Motivation

We are often interested to compute quantities (statistics) on random variables. For ex,

  • the average response to a drug
  • probability of a particular sum when throwing two dice
  • average reconstructions in VAE given an input.

These statistics often intractable to compute.

  • Cannot derive a perfect drug response model (too complex)
  • Cannot enumerate all possible dice combinations (too lazy)
  • Computationally infeasible (intractable integrals)

Monte Carlo Integration

Use random sampling instead of analytical computation. A single random sample might not be enough. Many random samples can give us a reliable quantification. E.g, by throwing dice many times we can obtain a histogram of probabilities for each possible sum. If we throw dice once, the histogram will be very wrong (just a single bar). But if we repeat hundreds of times and average, we are gonna get very close (law of large numbers).

More formally, in MC integration we treat inputs $x$ as random variables with pdf $p(x)$. Our desired statistic $y$ is the output and integrate over all possible $x$

$$ y=\int_{x} f(x) p(x) d x $$

This integral is equivalent to an expectation

$$ y = \int_{x} f(x) p(x) d x = \mathbb{E}_{x \sim p(x)}[f(x)] $$

We can approximate this expectation by random sampling and summation

$$ y=\mathbb{E}_{x \sim p(x)}[f(x)] \approx \frac{1}{n} \sum_{i} f\left(x_{i}\right)=\hat{y} $$
where $x_{i}$ is sampled from $p(x)$.

Note that $\hat{y}$ is an estimator because it only approximately estimates the value of $y$.

If we want to compute a quantity $y$ that we can express it as an integral of a function $f$ over a probability space $x$ that has a known and easy to sample pdf $p(x)$ we can replace the exact but intractable computation with a tractable $\mathrm{MC}$ estimator

$$ y=\mathbb{E}_{x \sim p(x)}[f(x)] \approx \frac{1}{n} \sum_{i} f\left(x_{i}\right), x_{i} \sim p(x) $$

If we can't translate the quantity as such an integral, we can't estimate it. For instance, we cannot use $\mathrm{MC}$ on the following because neither the $\log p(x \mid z)$ nor the $\nabla_{\varphi} q_{\varphi}(z \mid x)$ are probability densities:

$$ \nabla_{\varphi} \mathbb{E}_{\mathbf{z} \sim q_{\varphi}(\mathbf{z} \mid x)}[\log p(\boldsymbol{x} \mid \mathbf{z})]=\int_{Z} \log p(\boldsymbol{x} \mid \mathbf{z}) \nabla_{\varphi} q_{\varphi}(\mathbf{z} \mid \boldsymbol{x}) d \mathbf{z} $$

Estimator mean and variance

Our estimator is itself a random variable $\rightarrow$. It has its own mean $\mu_{\hat{y}}=\mathbb{E}[\hat{y}]$ and variance $\operatorname{Var}[\hat{y}]=\mathbb{E}\left[\left(\hat{y}-\mu_{\hat{y}}\right)^{2}\right]$.

The higher the variance, the more the estimation fluctuates after every new experiment.

Estimator bias

An estimator is unbiased if its expected value equals the true parameter. For example, the sample mean x̄ is an unbiased estimator of the population mean μ because E[x̄] = μ.

$$ \mathbb{E}[\hat{y}]=y $$

Otherwise, biased with bias

$$ \text { bias }=\mathbb{E}[\hat{y}]-y $$

It is better to have unbiased estimators, but in some cases a bit of bias is ok. Trade tractability for less accurate solutions (than what could be).

MC estimators are unbiased due to linearity of expectation.

For estimating $\mathbb{E}[f(X)]$ using $\hat{\theta} = \frac{1}{n}\sum_{i=1}^n f(X_i)$:

$$ \mathbb{E}[\hat{\theta}] = \mathbb{E}\left[\frac{1}{n}\sum_{i=1}^n f(X_i)\right] = \frac{1}{n}\sum_{i=1}^n \mathbb{E}[f(X_i)] = \mathbb{E}[f(X)] $$

The expectation operator "pushes through" the summation and averaging operations, giving us the true value. This holds for any sample size $n$, making the estimator unbiased regardless of how many samples we use.

This is why MC methods are so powerful - you get this theoretical guarantee basically for free, regardless of how complex your function $f(X)$ is or what distribution you're sampling from (though of course it takes a LOT of samples for good accuracy).

Note: The Law of Large Numbers ensures the estimator is also consistent (converges to the true value as $n \to \infty$), but unbiasedness is a separate property.

Standard error of MC estimator

The MC estimator is a sample mean

$$ \mathbb{E}_{x \sim p(x)}[f(x)] \approx \frac{1}{n} \sum_{i} f\left(x_{i}\right) $$

The standard error of a sample mean is

$$ \sigma_{\hat{f}}=\frac{\sigma}{\sqrt{n}} $$

The more samples we take the less the estimator deviates. But the deviation reduces only as $\sqrt{n}$. With $4 x$ more samples we only improve our error two times.