Let us define a random variable $X$ with density function $p(x)$. We wish to calculate $\mathbb{E}[f(X)] = \int f(x)p(x)dx$. We can compute the expectation by Monte Carlo simulations as

$$\mathbb{E}[f(X)] =\frac{1}{N} \sum_{i=1}^{N} f(x_i)p(x_i)$$

where $x_i$ are sampled from $p(x)$.

Sometimes it is impossible to generate random samples from $p(x)$. In such cases we use importance sampling and estimate

$$\mathbb{E}[f(X)] =\frac{1}{N} \sum_{i=1}^{N} \frac{f(x_i)p(x_i)}{g(x_i)}$$

where $x_i$ are sampled from $g(x)$.

My question is that if we know that $\delta_1 \le \mathbb{E}[f(X)] \le \delta_2$, then how do we exploit this information in estimating $\mathbb{E}[f(X)]$ using importance sampling.

I've done a lot of google search looking for importance sampling with prior information etc. However, the closest that I have come to involve evaluating the $\mathbb{E}[f(X)]$ over some subset of the support of the random variable $X$.

Still it does not help me with utilizing the additional information that I have about $\mathbb{E}[f(X)]$ from the bounds.

I would like to know the following:

Has such a thing been studied?

If yes, can somebody point me to a useful reference?

  • $\begingroup$ I changed sorry for the mistake $\endgroup$ – user123884 Feb 12 '14 at 18:37

Having explicit bounds on $\mathbb{E}[f(X)]$ does not appear to be useful. The variance can still be arbitrarily large, and the variance governs the rate of convergence for MC sampling. And if the variance is infinite, Monte Carlo estimation does not even converge to the expected value.

If you strengthen your assumptions slightly, you can say something more interesting. First, assume that $\Pr(f(X)<0)=0$. Then we can apply Markov's inequality to conclude that for any $a>0$, $$p(x>\delta_2 + a)\leq \delta_2/a$$ We could then (in principle) use this bound to inform our selection of $g$ in order to reduce the variance. However, because the variance could still be infinite, this assumption does not buy us much.

Next, assume that $\mathbb{E}[f(X)^2]\leq \delta_3$ (so we can bound the standard deviation $\sigma<\delta_3$). Then we can apply Chebyshev's inequality to get, for any $a>0$, $$p(|x-\delta_2|>a\delta_3)\leq 1/a^2$$

Finally, suppose that if $f(x)>0$ then $\delta_1\leq x\leq \delta_2$-- then we can apply Hoeffding's inequality to get even stronger (exponential) convergence. $$p(x>\delta_2 + a)\leq (\delta_2-\delta_1)/a$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.