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

Post a comment