Importance Sampling Simulation

Question

I need to calculate an integral using importance sampling method and, for the stopping criteria of the simulation, it is given an relative error. I've found that the relative error is defined by the ratio of the standard deviation by the mean of the estimator. But I am really having difficults to calculate it.

The estimative of the integral is given by $$I = \frac{1}{n}\sum_{i=1}^n \frac{f(x_i)}{g(x_i)} , x_i \sim g$$

The standard deviation I think is $$ \sigma = \left(\frac{1}{n} \sum_{i=0}^n \left(\frac{f(x_i)}{g(x_i)}-I\right)^2 \right)^{\frac{1}{2}}$$

and the mean is $I$. But this doesn't gives a good stopping criteria, since it tends to be constant for larger values of $n$. So I thought that $\frac{\sigma}{\sqrt{n}}$, the mean standard error, would give a better criteria. But I am not sure about it.

Here some material talking about how to calculate de relative error using importance sampling: http://www2.math.umd.edu/~trivisa/monte-carlo.pdf

I don't know what I am doing wrong, if I am not correctly calculating the standard deviation.

Thanks in advance.

Answer 1

Make sure that you fully understand simple Monte Carlo first.

Let $\{X_i\}_{i\geq 1}$ be a sequence of independent and identically distributed random variables, such that $X_1$ has density $f$. For some function $h$, suppose that $\mathrm{E}[|h(X_1)|]<\infty$.

By the Strong Law of Large Numbers, $$ \hat{I}_n = \frac{1}{n}\sum_{i=1}^n h(X_i) \to \mathrm{E}[h(X_1)] = \int h(t)f(t)\,dt \, , $$ almost surely, when $n\to\infty$. Also, $$ \mathrm{E}[\hat{I}_n] = \mathrm{E}[h(X_1)] \, , $$ and $$ \mathrm{E}\left[\hat{I}^2_n\right] = \frac{\mathrm{E}[(h(X_1))^2]}{n} +\left(1-\frac{1}{n}\right)\mathrm{E}^2[h(X_1)] \, , $$ in which we used the convenient notation $\mathrm{E}^2[\;\cdot\;] = (\mathrm{E}[\;\cdot\;])^2$.

The relative error of $\hat{I}_n$ is defined as $$ \frac{\sqrt{\mathrm{Var}[\hat{I}_n]}}{|\mathrm{E}[\hat{I}_n]|} = \sqrt{\frac{\mathrm{E}\!\left[\hat{I}^2_n\right] - \mathrm{E}^2[\hat{I}_n]}{\mathrm{E}^2[\hat{I}_n]}} = \sqrt{\frac{\mathrm{E}\!\left[\hat{I}^2_n\right]}{\mathrm{E}^2[\hat{I}_n]}-1} = \frac{1}{\sqrt{n}} \sqrt{\frac{\mathrm{E}[(h(X_1))^2]}{\mathrm{E}^2[h(X_1)]}-1} \,\, . $$

Now, just repeat this reasoning for importance sampling.

Let $\{Y_i\}_{i\geq 1}$ be a sequence of independent and identically distributed random variables, such that $Y_1$ has density $g>0$. It follows that $$ \hat{J}_n = \frac{1}{n}\sum_{i=1}^n \frac{h(Y_i)f(Y_i)}{g(Y_i)}\to \mathrm{E}[h(Y_1)f(Y_1)/g(Y_1)] = \int\frac{h(t)f(t)}{g(t)}g(t)\,dt $$ $$ = \int h(t)f(t)\,dt = \mathrm{E}[h(X_1)] \, , $$ almost surely, when $n\to\infty$. Also, $$ \mathrm{E}[\hat{J}_n] = \mathrm{E}[h(Y_1)f(Y_1)/g(Y_1)] \, , $$ and $$ \mathrm{E}\left[\hat{J}^2_n\right] = \frac{\mathrm{E}[(h(Y_1)f(Y_1)/g(Y_1))^2]}{n} +\left(1-\frac{1}{n}\right)\mathrm{E}^2[h(Y_1)f(Y_1)/g(Y_1)] \, . $$

Doing the algebra, the relative error for the importance sampling estimator is $$ \frac{1}{\sqrt{n}} \sqrt{\frac{\mathrm{E}[(h(Y_1)f(Y_1)/g(Y_1))^2]}{\mathrm{E}^2[h(Y_1)f(Y_1)/g(Y_1)]}-1} \, . $$ Hence, you should stop simulating $Y_i$'s when $$ \frac{1}{\sqrt{n}} \sqrt{\frac{\frac{1}{n}\sum_{i=1}^n (h(Y_i)f(Y_i)/g(Y_i))^2}{\left(\frac{1}{n}\sum_{i=1}^n h(Y_i)f(Y_i)/g(Y_i)\right)^2}-1} $$ becomes smaller than the pre-specified relative error.

Answer 2

Your $\sigma$ is the standard deviation of $I$, you're looking for a standard deviation of $E[\hat{I}]=\sigma/\sqrt{N}$. So, yes, your guess is correct.

If you read carefully the PDF in your link, you'd see $\sqrt{N}$ written all over it in relative error formulae.