I'm having some trouble understanding Monte Carlo method with and without Importance Sampling. Please alert me of any mistakes! We desire $I=\int_{a}^{b}f(x)dx$.
Simple Monte Carlo, hit'n'miss: By taking the quantity of randomly and uniformly generated points under the function and dividing this by the total number of generations, one approaches the ratio of the integrand to the domain area, A, in which the random number were generated.$$\frac{I}{A}=\lim_{n\to\infty}\frac{n_{hit}}{n}$$ One could code this process along the following lines ($y_{max}$ and $y_{min}$ are the bounds that help define A):
hits = 0
do i = 0, n
x = ran()*(b-a)+a
y = ran()*(ymax-ymin)+ymin
if (y <= f(x)) hits = hits + 1
end do
I = (b-a)*(ymax-ymin)*(hits/n)
Importance Sampling: Accuracy can be improved by changing the integrand (to say $g(x)$) such that the variance is decreased. To preserve the integrals' value however, we must offset this change by altering the distribution of random numbers. Say $p(x)$ is this normalized distribution. $$I=\int_{a}^{b}f(x)dx=\int_{a}^{b}\bigg(\frac{f(x)}{p(x)}\bigg)p(x)dx=\int_{a}^{b}g(x)p(x)dx$$ In our Simple Monte Carlo discussion, $p(x)= (b-a)^{-1}$. Loosely speaking, we'd like to pick $p(x)$ such that $g(x)$ is as constant as possible.
My Questions:
- Is my understanding of the two forms of Monte Carlo Integration correct?
- In a code utilizing the Importance Sampling, is there anything else to gain aside from improved accuracy?
- What might the pseudo-code of the Importance Sampling method look like?
This last question is my greatest concern. Is the implementation as simple as writing $g(x)$ in place of $f(x)$, and $x=rand()\cdot(b-a)+a$ for whatever the new distribution gives by inverting, $$rand()=\int_{a}^{x}p(x')dx'$$ Is $y$ still generated uniformly random?