A computable figure of merit for quasi-Monte Carlo point sets
HTML articles powered by AMS MathViewer
- by Makoto Matsumoto, Mutsuo Saito and Kyle Matoba PDF
- Math. Comp. 83 (2014), 1233-1250 Request permission
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}||f||_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
- F. Ametrano, L. Ballabio, et al., A free/open-source library for quantitative finance, http://quantlib.org/index.shtml.
- 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, DOI 10.1016/j.jco.2010.06.002
- 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, DOI 10.1007/s11075-011-9497-y
- 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, DOI 10.1515/crll.2002.037
- 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, DOI 10.1137/060666639
- 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, DOI 10.1007/978-3-642-04107-5_{5}
- Josef Dick and Peter Kritzer, Duality theory and propagation rules for generalized digital nets, Math. Comp. 79 (2010), no. 270, 993–1017. MR 2600553, DOI 10.1090/S0025-5718-09-02315-1
- Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394, DOI 10.1017/CBO9780511761188
- S. W. Golomb, Shift register sequences, Aegean Park Press, 1982.
- Peter Hellekalek and Hannes Leeb, Dyadic diaphony, Acta Arith. 80 (1997), no. 2, 187–196. MR 1450924, DOI 10.4064/aa-80-2-187-196
- 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, DOI 10.1016/j.disc.2010.11.002
- L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
- L.H. Loomis, Introduction to abstract harmonic analysis, Dover Books on Mathematics, Dover Publications, 2011.
- 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, DOI 10.1109/18.748992
- Jiří Matoušek and Jaroslav Ne et il, Invitation to discrete mathematics, 2nd ed., Oxford University Press, Oxford, 2009. MR 2469243
- M. Matsumoto and Y. Yoshiki, Existence of fast convergent quasi-Monte Carlo point sets via Walsh figure of merit, 2012, To appear in MCQMC2012.
- 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, DOI 10.1137/1.9781611970081
- 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
- C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948), 379–423, 623–656. MR 26286, DOI 10.1002/j.1538-7305.1948.tb01338.x
- 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
- M. M. Skriganov, Harmonic analysis on totally disconnected groups and irregularities of point distributions, J. Reine Angew. Math. 600 (2006), 25–49. MR 2283797, DOI 10.1515/CRELLE.2006.085
- Hong Hee Sun, Digital nets and sequences for quasi-monte carlo methods, Ph.D. thesis, Hong Kong Baptist University, Hong Kong, China, May 2002.
- 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
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
- 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 - © Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 3167457