# On the optimal distribution for importance sampling

Let's say $$X$$ is a rv, $$p(x)$$ is its pmf. I want to importance-sample $$\mu := \mathbb E[f(X)]$$, for some bounded function $$0, using another distribution $$q(x)$$. Then what I should do is summing $$\hat\mu := \frac{1}{n} \sum_{k=1}^n \frac{f(Y_k)p(Y_k)}{q(Y_k)}$$ where $$Y_k$$ are generated using $$q$$.

According to this lecture note, there is an optimal $$q$$, denoted by $$q'$$, that minimizes the variance of $$\hat\mu$$: $$q'(x)\propto f(x)p(x)$$ If I sample using $$q'$$, then all summands in the definition of $$\hat\mu$$ becomes constant. So yeah, it does give me a variance-zero experience. Really appreciate.

What I don't seem to understand is that, if I now want to importance-sample $$g := 1 - f$$ instead, then suddenly $$q'$$ is not the best distribution, as $$q'$$ is no longer $$\sim gp = (1 - f)p$$.

Yet another example is that, if I want to sample $$h := 100 + f$$, then $$hp$$ is just $$100(p \pm \epsilon)$$, so the optimal $$q$$ is very close to $$p$$. Or maybe it's telling me that I shouldn't bother.

How is it possible that the optimal choice of $$q$$ depends on an affine transformation I applied to $$f$$? Does that mean that I should optimize over the affine transformations that can be applied to $$f$$?

If you choose the importance distribution ($$q$$) to be proportional to $$f(x)p(x)$$, i.e., $$\rho(x) := f(x)p(x)/\mu$$, you achieve a zero variance estimator:

$$\frac{1}{n} \sum_{k=1}^n \frac{f(x)p(x)}{f(x)p(x)/\mu} = \frac{\mu}{n} \sum_{k=1}^n \frac{f(x)p(x)}{f(x)p(x)} = \mu.$$ The idea essentially says the optimal estimator of the integral is obtained by drawing samples exactly from the integrand (normalized) and evaluating the weight, which is exactly equal to the integral itself.

RE first example: the optimal $$q$$ will no longer be $$\rho(x) = f(x)p(x)/\mu$$ because $$\frac{1}{n}\sum_{i=1}^n \frac{(1-f(X_i))p(X_i)}{q(X_i)} = \frac{1}{n}\sum_{i=1}^n \frac{p(X_i)}{q(X_i)}q(X_i) - \frac{1}{n}\sum_{j=1}^n\frac{f(X_j)p(X_j)}{q(X_j)},$$ you can see that if you use $$\rho(x)$$ as your proposal, the first term on the RHS will no longer be optimal; $$\rho(x)$$ is only optimal for the second term.

RE second example: In this case, $$\frac{1}{n}\sum_{i=1}^n \frac{(100 + f(X_i))p(X_i)}{q(X_i)} = \frac{100}{n}\sum_{i=1}^n \frac{p(X_i)}{q(X_i)} + \frac{1}{n}\sum_{j=1}^n\frac{f(X_j)p(X_j)}{q(X_j)},$$ the same idea applies; the first term on the RHS should use a $$p$$ as $$q$$.

• I did get that the optimal estimator is different if I rewrite $f$ using an affine transformation. What I didn't get is why the choice of a sampling distribution, $q$, should depend on the arbitrarily affine transformation I applied to $f$? Jan 1, 2022 at 12:35
• @Symbol1 could you explain why you think it shouldn't depend on a transformation? (So I can understand where you're coming from)
– user
Jan 2, 2022 at 21:30
• Because, although what I really want is $\mathbb E[f(X)]$, I can always claim that I am interested in $\mathbb E[1-f(X)]$. You then proceed to sample an empirical value of $\mathbb E[1-f(X)]$ for me. So depending on what I claim, you will use different $q$ for simulations, some of them must be better than the others. The question is, how do I know if one $q$ is better than another $q$, if they are all optimal up to some affine transformation of $f$? Jan 2, 2022 at 21:34
• Ah, thank you for the clarification, looks like I totally misunderstood your question. Hopefully I understand now. So for the specific estimator $\hat \mu_f := (1/n)\sum f(X_i)p(X_i)/q(X_i)$, we have the optimal $q(x) \propto f(x)p(x)$. If you change your test function to say $h = 1-f$, then WITH RESPECT TO $\hat\mu_h$, sampling from the distribution proportional to $h$ is optimal. Alternatively, you can sample proportionally to $f(x)p(x)$, and change your estimator $\hat\mu_h$ to $\tilde \mu_h := 1- \hat\mu_f$, then this will also have 0 variance.
– user
Jan 2, 2022 at 21:59
• OK. It seems like I did not aware of that $\hat\mu_h$ is different from $\tilde\mu_h$ (not equivalent by an affine transformation), so it now makes sense that different estimators have different $q$. Jan 3, 2022 at 0:15

There's more than one optimal choice of $$q$$.

Suppose $$p(x)=2x$$ on $$[0,1]$$ and 0 otherwise, and $$f(x)=x$$. You can optimally choose $$q(x)=p(x)$$ and get zero variance or you can choose $$q(x)=2-2x$$ and estimate $$E[f(X)]=1-\frac{1}{2}E_Q[2-2x]$$ and get zero variance that way. There's a whole affine family of zero-variance estimators. The optimality proofs don't claim the optimum is unique.

• But then which (estimator, $q$) is the best one in the following sense: Say I am allowed to query $f$ at 100 points generated $p$. From those data points I can define a $q$ and query $f$ at 10000 points generated by $q$. How should I choose (estimator, $q$) then? (Maybe this question doesn't make sense but this is where I came from.) Dec 31, 2021 at 7:58
• Intuitively I know that I should sample from regions where $f$ is more unstable/fluctuating. But the so-called optimum $q$ doesn't address that. Instead it just says that I should bias toward a larger $f$ value, which make no sense to me because $1 - f$ is the other way around. Dec 31, 2021 at 8:10