An $L_2$ bound for Perfect Monte Carlo

Suppose that you sample from a probability measure $\pi$ to estimate the expectation $\pi(f) := \int f(x) \pi(\mbox{d}x)$ and formed an estimate $\pi^N(f)$. How close are you to the true expectation $\pi(f)$?

In this post, we work on $\bR$, so all functions and probability space are defined on $\bR$. Suppose we can sample $\pi(\mbox{d}x)$ exactly but cannot evaluate the integral $\pi(f) = \int f(x) \pi(\mbox{d}x)$. We assume also $f$ possesses the following property, \begin{align*} \|f\|_\infty := \sup_x |f(x)| \leq C. \end{align*} for some $0 < C < \infty$. For future reference, we define the $p$-norm of the function $f$: \begin{align*} \|f\|_p = \left( \int |f|^p \pi(\mbox{d}x)\right)^{1/p}, \end{align*} and note that in probabilistic terms, $\|f\|_p^p = \bE[|f|^p]$. As we know from here, we can estimate the expectation $\pi(f)$ by sampling from $\pi$. This estimate is obtained via the particle approximation of $\pi$ using $N$ particles, let us denote it with $\pi^N$. It is given by, \begin{align*} \pi^N(\mbox{d}x) = \frac{1}{N} \sum_{k=1}^N \delta_{X^{(k)}}(\mbox{d}x), \end{align*} where $X^{(k)} \sim \pi$ iid. Consequently the estimate of the $\pi(f)$ is given by, \begin{align*} \pi^N(f) = \frac{1}{N} \sum_{k=1}^N f\left(X^{(k)}\right). \end{align*} So it is natural to wonder about the $L_2$ error, i.e. $\|\pi(f) - \pi^N(f)\|_2$. The rest of the post is devoted to show that this error is bounded.

For future reference, first we prove a simple fact. That is, in a probability space, $\|f\|_p \leq C$. It is simple to show, \begin{align*} \|f\|_p = \left(\int |f|^p \pi(\mbox{d}x)\right)^{1/p} \leq \left(C^p \int \pi(\mbox{d}x)\right)^{1/p} \end{align*} since $\sup_x |f(x)| \leq C$ by assumption.

Let's set $p=2$. We would like to bound the error, \begin{align*} \left\lVert \pi(f) - \pi^N(f) \right\rVert_2 &= \left\lVert \pi(f) - \frac{1}{N} \sum_{k=1}^N f\left(X^{(k)}\right)\right\rVert_2\\ &= \bE\left[\left(\pi(f) - \frac{1}{N} \sum_{k=1}^N f\left(X^{(k)}\right)\right)^2\right]^{1/2} \end{align*} At this point, a few simple facts to note: (i) Since $X^{(k)}$ are iid, so are $f\left(X^{(k)}\right)$, (ii) $\bE[f(X^{(k)}] = \pi(f)$. Let us compute the expectation: \begin{align*} \bE\left[\left(\pi(f) - \frac{1}{N} \sum_{k=1}^N f\left(X^{(k)}\right)\right)^2\right] &= \bE\left[ \pi^2(f) - \frac{2\pi(f)}{N} \sum_{k=1}^N f\left(X^{(k)}\right) + \left(\frac{1}{N}\sum_{k=1}^N f\left(X^{(k)}\right)\right)^2\right] \\ &= \bE\left[\left(\frac{1}{N}\sum_{k=1}^N f\left(X^{(k)}\right)\right)^2\right] - \pi^2(f) \\ &= \bE\left[\frac{f^2\left(X^{(k)}\right)}{N}\right] + \left(\frac{N^2 - N}{N^2} -1 \right)\pi^2(f) \\ &= \bE\left[\frac{f^2\left(X^{(k)}\right)}{N}\right] - \frac{\pi^2(f)}{N} \end{align*} Now the rest of the job is easy. First see $\pi^2(f) > 0$ so if we remove the last term, we have an upper bound. Second notice $\bE[f^2] = \|f\|_2^2 \leq C^2$. Using these facts, we have, \begin{align*} \bE\left[\left(\pi(f) - \frac{1}{N} \sum_{k=1}^N f\left(X^{(k)}\right)\right)^2\right] \leq \frac{C^2}{N} \end{align*} Remember our goal was to bound $\left\lVert \pi(f) - \pi^N(f) \right\rVert_2$ which is the square root of the expectation on the left. So eventually we have proved that, \begin{align*} \left\lVert\pi(f) - \pi^N(f)\right\rVert_2 \leq \frac{C}{\sqrt{N}}, \end{align*} hence the standard Monte Carlo $\mathcal{O}(N^{-\frac{1}{2}})$ rate.

Of course these bounds are more complicated when this sampling scheme is not exact but approximate, e.g. particle filters. I hope to write about these bounds for approximate sampling algorithms in the near future.