Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

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
DOI: https://doi.org/10.1090/S0025-5718-2013-02774-3
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?)

  • [1] F. Ametrano, L. Ballabio, et al., A free/open-source library for quantitative finance, http://quantlib.org/index.shtml.
  • [2] Jan Baldeaux, Josef Dick, Julia Greslehner, and Friedrich Pillichshammer, Construction algorithms for higher order polynomial lattice rules, J. Complexity 27 (2011), no. 3-4, 281-299. MR 2793864 (2012b:65028), https://doi.org/10.1016/j.jco.2010.06.002
  • [3] Jan Baldeaux, Josef Dick, Gunther Leobacher, Dirk Nuyens, and Friedrich Pillichshammer, Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules, Numer. Algorithms 59 (2012), no. 3, 403-431. MR 2886448, https://doi.org/10.1007/s11075-011-9497-y
  • [4] W. W. L. Chen and M. M. Skriganov, Explicit constructions in the classical mean squares problem in irregularities of point distribution, J. Reine Angew. Math. 545 (2002), 67-95. MR 1896098 (2003g:11083), https://doi.org/10.1515/crll.2002.037
  • [5] Josef Dick, Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order, SIAM J. Numer. Anal. 46 (2008), no. 3, 1519-1553. MR 2391005 (2009d:42077), https://doi.org/10.1137/060666639
  • [6] Josef Dick, On quasi-Monte Carlo rules achieving higher order convergence, Monte Carlo and quasi-Monte Carlo methods 2008, Springer, Berlin, 2009, pp. 73-96. MR 2743889 (2012d:65050), https://doi.org/10.1007/978-3-642-04107-5_5
  • [7] Josef Dick and Peter Kritzer, Duality theory and propagation rules for generalized digital nets, Math. Comp. 79 (2010), no. 270, 993-1017. MR 2600553 (2011d:11183), https://doi.org/10.1090/S0025-5718-09-02315-1
  • [8] Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394 (2012b:65005)
  • [9] S. W. Golomb, Shift register sequences, Aegean Park Press, 1982.
  • [10] Peter Hellekalek and Hannes Leeb, Dyadic diaphony, Acta Arith. 80 (1997), no. 2, 187-196. MR 1450924 (98g:11090)
  • [11] Jan Baldeaux, Josef Dick, and Friedrich Pillichshammer, Duality theory and propagation rules for higher order nets, Discrete Math. 311 (2011), no. 5, 362-386. MR 2748641 (2012b:11121), https://doi.org/10.1016/j.disc.2010.11.002
  • [12] L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley-Interscience [John Wiley & Sons], New York, 1974. Pure and Applied Mathematics. MR 0419394 (54 #7415)
  • [13] L.H. Loomis, Introduction to abstract harmonic analysis, Dover Books on Mathematics, Dover Publications, 2011.
  • [14] David J. C. MacKay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inform. Theory 45 (1999), no. 2, 399-431. MR 1677007 (99j:94077), https://doi.org/10.1109/18.748992
  • [15] Jiří Matoušek and Jaroslav Nešetřil, Invitation to discrete mathematics, 2nd ed., Oxford University Press, Oxford, 2009. MR 2469243 (2010g:05004)
  • [16] M. Matsumoto and Y. Yoshiki, Existence of fast convergent quasi-Monte Carlo point sets via Walsh figure of merit, 2012, To appear in MCQMC2012.
  • [17] Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997 (93h:65008)
  • [18] Harald Niederreiter, Digital nets and coding theory, Coding, cryptography and combinatorics, Progr. Comput. Sci. Appl. Logic, vol. 23, Birkhäuser, Basel, 2004, pp. 247-257. MR 2090654 (2005f:11161)
  • [19] C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948), 379-423, 623-656. MR 0026286 (10,133e)
  • [20] M. M. Skriganov, Coding theory and uniform distributions, Algebra i Analiz 13 (2001), no. 2, 191-239 (Russian, with Russian summary); English transl., St. Petersburg Math. J. 13 (2002), no. 2, 301-337. MR 1834866 (2002g:11111)
  • [21] M. M. Skriganov, Harmonic analysis on totally disconnected groups and irregularities of point distributions, J. Reine Angew. Math. 600 (2006), 25-49. MR 2283797 (2007k:11122), https://doi.org/10.1515/CRELLE.2006.085
  • [22] Hong Hee Sun, Digital nets and sequences for quasi-monte carlo methods, Ph.D. thesis, Hong Kong Baptist University, Hong Kong, China, May 2002.
  • [23] P. Zinterhof and H. Stegbuchner, Trigonometrische Approximation mit Gleichverteilungsmethoden, Studia Sci. Math. Hungar. 13 (1978), no. 3-4, 273-289 (1981) (German, with English summary). MR 620142 (83a:10088)

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: https://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.

American Mathematical Society