Random Numbers part 9

Adaptive and Recursive Monte Carlo MethodsThis section discusses more advanced techniques of Monte Carlo integration. As examples of the use of these techniques, we include two rather different, fairly sophisticated, multidimensional Monte Carlo codes: vegas [1,2] , and miser [3]. The techniques that we discuss all fall under the general rubric of reduction of variance (§7.6), but are otherwise quite distinct.
Nội dung trích xuất từ tài liệu:
Random Numbers part 9316 Chapter 7. Random Numbers7.8 Adaptive and Recursive Monte Carlo Methods This section discusses more advanced techniques of Monte Carlo integration. Asexamples of the use of these techniques, we include two rather different, fairly sophisticated,multidimensional Monte Carlo codes: vegas [1,2] , and miser [3]. The techniques that we visit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America). readable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMs Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine- Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)discuss all fall under the general rubric of reduction of variance (§7.6), but are otherwisequite distinct.Importance Sampling The use of importance sampling was already implicit in equations (7.6.6) and (7.6.7).We now return to it in a slightly more formal way. Suppose that an integrand f can be writtenas the product of a function h that is almost constant times another, positive, function g. Thenits integral over a multidimensional volume V is f dV = (f /g) gdV = h gdV (7.8.1)In equation (7.6.7) we interpreted equation (7.8.1) as suggesting a change of variable toG, the indefinite integral of g. That made gdV a perfect differential. We then proceededto use the basic theorem of Monte Carlo integration, equation (7.6.1). A more generalinterpretation of equation (7.8.1) is that we can integrate f by instead sampling h — not,however, with uniform probability density dV , but rather with nonuniform density gdV . Inthis second interpretation, the first interpretation follows as the special case, where the meansof generating the nonuniform sampling of gdV is via the transformation method, using theindefinite integral G (see §7.2). More directly, one can go back and generalize the basic theorem (7.6.1) to the caseof nonuniform sampling: Suppose that points xi are chosen within the volume V with aprobability density p satisfying p dV = 1 (7.8.2)The generalized fundamental theorem is that the integral of any function f is estimated, usingN sample points xi , . . . , xN , by f f f 2 /p2 − f /p 2 I≡ f dV = pdV ≈ ± (7.8.3) p p Nwhere angle brackets denote arithmetic means over the N points, exactly as in equation(7.6.2). As in equation (7.6.1), the “plus-or-minus” term is a one standard deviation errorestimate. Notice that equation (7.6.1) is in fact the special case of equation (7.8.3), withp = constant = 1/V . What is the best choice for the sampling density p? Intuitively, we have alreadyseen that the idea is to make h = f /p as close to constant as possible. We can be morerigorous by focusing on the numerator inside the square root in equation (7.8.3), which isthe variance per sample point. Both angle brackets are themselves Monte Carlo estimatorsof integrals, so we can write 2 2 2 f2 f f2 f f2 S≡ − ≈ pdV − pdV = dV − f dV (7.8.4) p2 p p2 p pWe now find the optimal p subject to the constraint equation (7.8.2) by the functional variation 2 δ f2 0= dV − f dV +λ p dV (7.8.5) δp p 7.8 Adaptive and Recursive Monte Carlo Methods ...