A COMPUTABLE FIGURE OF MERIT FOR QUASI-MONTE CARLO POINT SETS

作者：Matsumoto Makoto^*; Saito Mutsuo; Matoba Kyle

来源：Mathematics of Computation, 2014, 83(287): 1233-1250.

• quasi-Monte Carlo
• numerical integration
• digital nets
• low discrepancy sequences
• Walsh functions
• figure of merit
• WAFOM
• computational finance

Let P subset of [0, 1) S be a finite point set of cardinality N in an Sdimensional cube, and let f : [0, 1)(S)-%26gt; R be an integrable function. A QMC integral of f by P is the average of values of f at each point in P, which approximates the integral of f over the cube. Assume that P is constructed from an F-2-vector space P subset of (F-2(n)) S by means of a digital net with n-digit precision. As an n-digit discretized version of Josef Dick%26apos;s method, we introduce the Walsh figure of merit (WAFOM) WAFOM(P) of P, which satisfies a Koksma-Hlawka type inequality, namely, QMC integration error is bounded by C-S,(n)parallel to f parallel to(n) WAFOM(P) under n-smoothness of f, where CS, n is a constant depending only on S, n. %26lt;br%26gt;We show a Fourier inversion formula for WAFOM(P) which is computable in O(nSN) steps. This effectiveness enables us to do a random search for P with small value of WAFOM(P), which would be difficult for other figures of merit such as discrepancy. From an analogy to coding theory, we expect that a random search may find better point sets than mathematical constructions. In fact, a naive search finds point sets P with small WAFOM(P). In experiments, we show better performance of these point sets in QMC integration than widely used QMC rules. We show some experimental evidence on the effectiveness of our point sets to even nonsmooth integrands appearing in finance.

• 出版日期2014-5