Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

   

 

A computable figure of merit for quasi-Monte Carlo point sets


Authors: Makoto Matsumoto, Mutsuo Saito and Kyle Matoba
Journal: Math. Comp. 83 (2014), 1233-1250
MSC (2010): Primary 11K38, 11K45, 65C05; Secondary 65D30, 65T50
Published electronically: September 23, 2013
MathSciNet review: 3167457
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ \mathcal {P} \subset [0,1)^S$ be a finite point set of cardinality $ N$ in an $ S$-dimensional cube, and let $ f:[0,1)^S \to \mathbb{R}$ be an integrable function. A QMC integral of $ f$ by $ \mathcal {P}$ is the average of values of $ f$ at each point in $ \mathcal {P}$, which approximates the integral of $ f$ over the cube. Assume that $ \mathcal {P}$ is constructed from an $ \mathbb{F}_2$-vector space $ P\subset (\mathbb{F}_2^n)^S$ by means of a digital net with $ n$-digit precision. As an $ n$-digit discretized version of Josef Dick's method, we introduce the Walsh figure of merit (WAFOM) $ {\mathrm {WAFOM}}(P)$ of $ P$, which satisfies a Koksma-Hlawka type inequality, namely, QMC integration error is bounded by $ C_{S,n}\vert\vert f\vert\vert _n {\mathrm {WAFOM}}(P)$ under $ n$-smoothness of $ f$, where $ C_{S,n}$ is a constant depending only on $ S,n$.

We show a Fourier inversion formula for $ {\mathrm {WAFOM}}(P)$ which is computable in $ O(n SN)$ steps. This effectiveness enables us to do a random search for $ P$ with small value of $ {\mathrm {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 naïve search finds point sets $ P$ with small $ {\mathrm {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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11K38, 11K45, 65C05, 65D30, 65T50

Retrieve articles in all journals with MSC (2010): 11K38, 11K45, 65C05, 65D30, 65T50


Additional Information

Makoto Matsumoto
Affiliation: Graduate School of Science, Hiroshima University, Hiroshima 739–8526 Japan
Email: m-mat@math.sci.hiroshima-u.ac.jp

Mutsuo Saito
Affiliation: Graduate School of Science, Hiroshima University, Hiroshima 739-8526 Japan
Email: saito@math.sci.hiroshima-u.ac.jp

Kyle Matoba
Affiliation: Finance Department,UCLA Anderson School of Management,Los Angeles,California
Email: kmatoba@anderson.ucla.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-2013-02774-3
Keywords: quasi-Monte Carlo, numerical integration, digital nets, low discrepancy sequences, Walsh functions, figure of merit, WAFOM, computational finance
Received by editor(s): July 3, 2012
Received by editor(s) in revised form: September 19, 2012
Published electronically: September 23, 2013
Additional Notes: The first author was partially supported by JSPS/MEXT Grant-in-Aid for Scientific Research No. 24654019, No. 23244002, No. 21654017, No. 19204002, and JSPS Core-to-Core Program No. 18005
The second author was partially supported by JSPS/MEXT Grant-in-Aid for Scientific Research No. 21654004
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.