## N p

a a lEP

Notice that now the function f / P is integrated on points distributed according to P. The function P is of course analytically known and normalized to unity. There would be less fluctuations in the integrand f / P if the distribution function P, which we could choose at will, looks like the original function f.

At any rate, the central idea in importance sampling is to choose P so that it looks like f and therefore f / P does not fluctuate much and the variance of the result is small. In other words, the estimated value of the integral is accurate, even with a relatively small number of points. Table 1 shows a comparison of the estimation of the integral using uniform sampling and importance sampling of the function f (x) = e10x with a quartic distribution function [1] in [0,1).

Table 1: Results [1] of the integral I = J ei0xdx =-- 2202.5466

o 10

using uniform and importance sampling with P(x) = 5x4 + 0.0001.

Table 1: Results [1] of the integral I = J ei0xdx =-- 2202.5466

o 10

using uniform and importance sampling with P(x) = 5x4 + 0.0001.

 N Uniform Importance Exact 100 2243.5107 2181.7468 2202.5466 1000 2295.6793 2208.6427 2202.5466 10000 2163.6349 2207.1890 2202.5466 100000 2175.3975 2203.7892 2202.5466 1000000 2211.7200 2202.8075 2202.5466 10000000 2203.8063 2202.5431 2202.5466

Note that we preferably want the distribution function P to be non zero in the regions where the function f is non zero, otherwise the ratio f / P leads to infinity if a random point is generated in that region. This is called undersampling and may cause large jumps in f / P in the regions where P(x) is too small. This is the reason why a small number was added to P(x) to avoid undersampling near x=0.

The error can be estimated as the following: The average deviation of the function from its mean value is about 5000 as can be seen in the plot of e10x in [0,1). However, a better estimate for the average deviation can be computed from _the deviations from the numerically calculated mean (or integral) so v ~ 5000. Therefore, the standard deviation is of the order of 5000/VN for uniform sampling (from the CLT). As for importance sampling, one must evaluate the mean standard deviations of the function f / P in [0,1), and then multiply it by i/VN. We can conclude from the above numerical data that the agreement of the last line to within 6 digits is not expected, and therefore, fortuitous. The following is the statement of CLT in mathematical terms:

0 0