# Importance sampling algorithm

I'm looking through my notes on importance sampling.

$\mu = \int h(x)\pi(x)dx = \int [h(x) \frac{\pi(x)}{g(x)}]g(x)dx$

draw $x^{(1)},...,x^{(m)}$ i.i.d. from proposal distribution $g(x)$

Calculate the importance weights:

$w^{(i)}=\frac{\pi(x^{(i)})}{g(x^{(i)})},$ for $i = 1,...,m$

This is the part where I'm confused. What is the distribution $\pi(x)$? Where did it come from? Do we choose it, similarly to how we chose $g(x)$?

As an example, I'm asked the following: Suppose $X \sim Unif[0,1]$ and we want to estimate $E[sin(\sqrt{X})]$....

So... $h(x) = \sin(\sqrt{X})$. Is $\pi(x)$ = 1 in this case? Since $X \sim Unif[0,1]$

Edit: I think I'm correct about the above stuff. Would $Unif[0,40]$ be a good choice for $g(x)$? $Unif[0,40]$ covers a lot more of $sin(\sqrt{X})$ than $Unif[0,1]$. Or are we only concerned with the portion of $h(x)$ bounded by [0,1]?

In your notation, $X$ has density $\pi(x)$ and you want to evaluate $\text{E}(h(X))$.

So no, you don't choose $\pi$, it is a feature of your problem.

In your example, you have $\pi$ constant on $[0,1]$.

As you suggest, in that particular case $\pi(x)=1$ in that interval (and $0$ elsewhere, naturally).

A good $g$ will approximate $h\pi$ (or if $h$ might go negative, to $|h|\cdot\pi$).

You need to avoid $g$ being zero if $h\pi$ isn't zero.

If we can sample from $h$, is there any reason why we can't simply set $g(x)=h(x)$?

In that case, you could (thereby avoiding importance sampling altogether), but one of the reasons to use importance sampling is to reduce variance.

That's done by making $g$ more like $h\pi$, rather than like $h$. (You may be thrown off a little because in your example, $\pi$ is constant.)

• Ok, so then if I understand correctly $Unif[0,40]$ would not be an appropriate $g(x)$ choice since $h(x)\pi(x)$ only "exists" on [0, 1]. Feb 25, 2014 at 19:16
• I was thinking to perhaps use $g(x) = 2x$ as on $[0,1]$ it integrates to 1. I can use the inverse CDF method to sample from it. Feb 25, 2014 at 19:42
• Clearly $g(x) = 2x$ isn't appropriate as it yields a variance twice as large as using the naive monte carlo approach Feb 25, 2014 at 20:53
• $\sqrt{x}$ works even better than $\frac{3}{2}\sqrt{x}$ because $\sin\sqrt{x}=\sqrt{x}-x^{3/2}/6+O(x^{5/2}) \le \sqrt{x}$ in the interval $[0,1]$.
– whuber
Feb 25, 2014 at 21:37
• That's a good question, which I'll answer in an edit to my answer. Feb 26, 2014 at 3:34