Minimization of computational costs of non-analogue Monte Carlo methods. (English) Zbl 0778.65007
Series on Soviet and East European Mathematics. 5. Singapore etc.: World Scientific. ix, 161 p. (1991).
Non-analogue Monte Carlo methods are used when the direct simulation is not sufficient to attain the required accuracy. Thus the problem arises of minimizing the computational cost of such procedures that can noticeably differ from the analogous problem for simple Monte Carlo. For this, given a family of random variables \(\{X\}\) with \(E(X)=J\) and finite variance \(DX\) an approximate value of \(J\) can be obtained by using \(n\) independent samples and considering the mean \(J=Z_ n=\Sigma X_ i/n\) for which we have \(E(Z_ n)=J\), \(DZ_ n=DX/n\). Denoting by \(t\) the average cost for obtaining a single value \(X_ i\) the problem is that of minimizing the product \(nt\) with the condition \(DX/n\leq \delta^ 2\), or more simply of minimizing \(tDX\).
Non-analogue Monte Carlo methods, on the contrary, can consider a parametric family of biased estimates \(X(\varepsilon)\) with the cost \(t(\varepsilon)\), variance \(V(\varepsilon)\) and bias of order \(\varepsilon\), so that \(| E(X(\varepsilon))-J|^ 2\leq C\varepsilon^ 2\) and the \(E(Z_{n,\varepsilon}-J)^ 2\leq V(\varepsilon)/n+C\varepsilon^ 2\). The problem is now that of minimizing \(nt(\varepsilon)\) with the condition \(V(\varepsilon)/n+C\varepsilon^ 2=\delta^ 2\) or \(t(\varepsilon)V(\varepsilon)/(\delta^ 2-C\varepsilon^ 2)\) with the condition \(C\varepsilon^ 2<\delta^ 2\).
The author considers several problems treated with non-analogue Monte Carlo methods. The book is mostly concerned with the solution of integral equations, transfer theory, boundary problems for elliptic equations. Those problems are exposed in detail with the various techniques which can be employed for their solutions. In the last chapter the evaluations of the cost of various algorithms for the solution of different problems are widely treated.
The bibliography contains fifty titles of books and papers.
Non-analogue Monte Carlo methods, on the contrary, can consider a parametric family of biased estimates \(X(\varepsilon)\) with the cost \(t(\varepsilon)\), variance \(V(\varepsilon)\) and bias of order \(\varepsilon\), so that \(| E(X(\varepsilon))-J|^ 2\leq C\varepsilon^ 2\) and the \(E(Z_{n,\varepsilon}-J)^ 2\leq V(\varepsilon)/n+C\varepsilon^ 2\). The problem is now that of minimizing \(nt(\varepsilon)\) with the condition \(V(\varepsilon)/n+C\varepsilon^ 2=\delta^ 2\) or \(t(\varepsilon)V(\varepsilon)/(\delta^ 2-C\varepsilon^ 2)\) with the condition \(C\varepsilon^ 2<\delta^ 2\).
The author considers several problems treated with non-analogue Monte Carlo methods. The book is mostly concerned with the solution of integral equations, transfer theory, boundary problems for elliptic equations. Those problems are exposed in detail with the various techniques which can be employed for their solutions. In the last chapter the evaluations of the cost of various algorithms for the solution of different problems are widely treated.
The bibliography contains fifty titles of books and papers.
Reviewer: M.Cugiani (Milano)
MSC:
65C05 | Monte Carlo methods |
65C20 | Probabilistic models, generic numerical methods in probability and statistics |
65-02 | Research exposition (monographs, survey articles) pertaining to numerical analysis |
65R20 | Numerical methods for integral equations |
65Z05 | Applications to the sciences |
35J25 | Boundary value problems for second-order elliptic equations |