Monte Carlo methods are widely used for estimating expectations of complicated probability distributions. Here I provide the well-known $L_2$ bound.

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 much more complicated when this sampling scheme is not exact but approximate, e.g. in the case of MCMC or particle filters. I hope to pursue these bounds also for vanilla sampling algorithms.

## 2 comments:

Thanks for this helpful post. It's worth mentioning that C < \infty . Also there's a repeated line in the equation array starting after "Let us compute the expectation:".

Ah thanks! Both of them are corrected.

## Post a Comment