Adaptive algorithm of Monte Carlo type for calculating the integral characteristics of complex systems (Q580885)

The authors consider a method for reducing the variance generally called selective sampling or importance sampling, and give an adaptive procedure for improving it. It is well known that the method consists in evaluating the integral \(J=\int^{1}_{0}f(x)dx\) by the estimator \(\hat J=(1/N)\sum (f(\xi_ i)/p(\xi_ i)).\) Where the \(\xi_ i\) are random values in accordance with the distribution \(F(t)=\int^{t}_{- \infty}p(x)dx\), and we suppose \(\int^{+\infty}_{- \infty}p(x)dx=\int^{1}_{0}p(x)dx=1.\) The variance of \(\hat J\) could be reduced to zero if we could assume \(p(x)=f(x)/J\), what is practically impossible. The method proposed by the authors consists in obtaining successive approximations \(f_ n(x)\), of the function f(x), from the values \(f(x_ i)\) \((i=1,2,...,n)\) calculated at the random points \(x_ i\). From it we obtain \(I_ n=\int^{1}_{0}f_ n(x)dx\) as an approximation of J, and \(p_ n(x)=f_ n(x)/I_ n\) as an approximation of p(x). The successive random point \(x_{n+1}\) can be obtained in accordance with the density \(p_ n(x).\) If now we assume an estimator of the form: \(\hat J_ N=\sum^{N}_{i=0}\alpha_ i(f(x_ i)/p_ i(x_ i))\), \(\alpha_ i\geq 0\), \(\sum \alpha_ i=1\) it can be proved that the variance of \(\hat J_ N\) will have an order of \(1/N^ 2\), or \(1/N^ 3\) (depending from the procedures used for obtaining \(f_ n(x)\) and for a suitable choice of the \(\alpha_ i)\).