2015/03/04

Monte Carlo as Intuition

I am doing teaching assistantship for Monte Carlo methods course. I explained the following exercise as an application of the Monte Carlo principle. It is nice because it coincides with a very intuitive guess.

Suppose we have a continuous random variable $X \sim p(x)$ and we would like to estimate its tail probability, i.e. the probability of the event $\{X \geq t\}$ for some $t \in \mathbb{R}$. What is the most intuitive way to do this? I bet that a child can give an answer (along with a reasonable explanation) in the following way: Take many $X$, say $N$, i.e. take $X^{(i)}$ with $i = \{1,\ldots,N\}$. Then simply count the ones that bigger than $t$, and the following quantity gives you an estimate of the tail probability: $$T = \frac{\#\{X^{(i)} \geq t\}}{N}$$ So among $N$ variables, you count ones bigger than $t$ and simply calculate the ratio. Very intuitive.

Let's see how this procedure underlies the rigorous Monte Carlo principle.

The Monte Carlo principle states that one can estimate expectations with respect to any test function $\varphi(x)$ provided that we can draw exact samples from $p(x)$, in other words, if we can take many $X^{(i)}$'s. So let us take $N$ identical copies of these random variables as above, and try to calculate the $\mathbb{E}[\varphi(x)]$. We recall the convention $\mathbb{P}(\mbox{d}x) = p(x)\mbox{d}x$, and write: $$\mathbb{E}[\varphi(x)] = \int \varphi(x) \mathbb{P}(\mbox{d}x) = \int \varphi(x) p(x) \mbox{d}x$$ We take again random variables $X^{(i)}$, and construct the following particle approximation of the measure $\mathbb{P}(\mbox{d}x)$: $$\mathbb{P}^N(\mbox{d}x) = \frac{1}{N} \sum_{k = 1}^N \delta_{X^{(i)}}(\mbox{d}x)$$ The Monte Carlo estimate of the expectation is given by, $$\bar{\varphi} = \int \varphi(x) p(x) \mbox{d}x \approx \int \varphi(x) \frac{1}{N} \sum_{k=1}^N \delta_{X^{(i)}}(x) \mbox{d}x$$ So following this, the empirical expectation can be computed as (recall the properties of Dirac delta function), $$\bar{\varphi} = \frac{1}{N} \sum_{k=1}^N \varphi(X^{(i)})$$ What we are interested in above was to estimate precisely the following quantity: $\mathbb{P}(X \geq t)$. This is of course given by, $$\mathbb{P}(X\geq t) = \int_t^\infty p(x) \mbox{d}x$$ Let us modify the limits of the integral: $$\int_t^\infty p(x) \mbox{d}x = \int_{-\infty}^\infty \mathbf{1}_{\{x \geq t\}}(x) p(x) \mbox{d}x$$ hence we can write the tail probability as an expectation: $$\mathbb{P}(X \geq t) = \mathbb{E}[\mathbf{1}_{\{x\geq t\}}(x)]$$ and the story follows given the samples from $p(x)$. Just by putting $\varphi(x) = \mathbf{1}_{\{x \geq t\}}(x)$ and computing $\bar{\varphi}$ as above, one can conclude as an exercise that application of the MC principle to estimation of this expectation exactly results in counting the samples above $t$ and dividing by $N$.

0 comments:

Post a Comment