Tractability of Multivariate Integration Using Low-Discrepancy Sequences

Tezuka, Shu

doi:10.1515/udt-2016-0013

Abstract

We propose a notion of (t, e, s)-sequences in multiple bases, which unifies the Halton sequence and (t, s)-sequences under one roof, and obtain an upper bound of their discrepancy consisting only of the leading term. By using this upper bound, we improve the tractability results currently known for the Halton sequence, the Niederreiter sequence, the Sobol’ sequence, and the generalized Faure sequence, and also give tractability results for the Xing-Niederreiter sequence and the Hofer-Niederreiter sequence, for which no results have been known so far.

References

[1] ATANASSOV, E. I.: On the discrepancy of the Halton sequences, Mathematica Balkanica New Series, 18(1-2) (2004), 15–32.
Search in Google Scholar Back to article
[2] DICK, J.—PILLICHSHAMMER, F.: Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, 2010.10.1017/CBO9780511761188
Search in Google Scholar Back to article
[3] DICK, J.—NIEDERREITER, H.—PILLICHSHAMMER, F.: Weighted star discrepancy of digital nets in prime bases. In: Monte Carlo and quasi-Monte Carlo methods 2004, Springer, (2006), 77–96.10.1007/3-540-31186-6_6
Search in Google Scholar Back to article
[4] DUSART, P.: The k^th prime is greater than k(ln k + ln ln k − 1) for k ≥ 2, Mathematics of Computation, 68 (1999), 411–415.10.1090/S0025-5718-99-01037-6
Search in Google Scholar Back to article
[5] HALTON, J. H.: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numerische Mathematik, 2 (1960), 84–90.10.1007/BF01386213
Search in Google Scholar Back to article
[6] HICKERNELL, F. J.—WANG, X.: The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension, Mathematics of Computation, 71 (2002), 1641–1661.10.1090/S0025-5718-01-01377-1
Search in Google Scholar Back to article
[7] HOFER, R.—NIEDERREITER, H.: A construction of (t, s)-sequences with finite-row generating matrices using global function fields, Finite Fields and Their Applications, 21 (2013), 97–110.10.1016/j.ffa.2012.11.004
Search in Google Scholar Back to article
[8] JÄCKEL, P.: Monte Carlo Methods in Finance, John Wiley and Sons, 2002.
Search in Google Scholar Back to article
[9] KRUSE, M.—STICHTENOTH, H.: Ein Analogon zum Primzahlsatz für algebraische Funktionenkörper, Manuscripta Mathematica, 69 (1990), 219–221.10.1007/BF02567920
Search in Google Scholar Back to article
[10] MATOUŠEK, J.: Geometric Discrepancy: An Illustrated Guide, revised second printing, Springer, 2010.
Search in Google Scholar Back to article
[11] NIEDERREITER, H.: Random Number Generation and Quasi-Monte Carlo Methods, In: CBMS-NSF Regional Conference Series in Applied Mathematics. Vol. 63, SIAM, 1992.10.1137/1.9781611970081
Search in Google Scholar Back to article
[12] NIEDERREITER, H.—XING, C.: Low-discrepancy sequences and global function fields with many rational places, Finite Fields and Their Applications, 2 (1996), 241–273.10.1006/ffta.1996.0016
Search in Google Scholar Back to article
[13] NOVAK, E.—WOŹNIAKOWSKI, H.: Tractability of Multivariate Problems, Volume II: Standard Information for Functionals, EMS Tracts in Mathematics Vol. 12. European Mathematical Society (EMS), Zrich, 2010.10.4171/084
Search in Google Scholar Back to article
[14] PAPAGEORGIOU, A.—TRAUB, J. F.: Beating Monte Carlo, RISK, 9 (June 1996), 63–65.
Search in Google Scholar Back to article
[15] SLOAN, I. H.—WOŹNIAKOWSKI, H.: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals, Journal of Complexity, 14 (1998), 1–33.10.1006/jcom.1997.0463
Search in Google Scholar Back to article
[16] SLOAN, I. H.—WANG, X.—WOŹNIAKOWSKI, H.: Finite-order weights imply tractability of multivariate integration, Journal of Complexity, 20 (2004), 46–74.10.1016/j.jco.2003.11.003
Search in Google Scholar Back to article
[17] SOBOL’, I. M.: The distribution of points in a cube and the approximate evaluation of integrals, USSR Computational Mathematics and Mathematical Physics, 7 (1967), 86–112.10.1016/0041-5553(67)90144-9
Search in Google Scholar Back to article
[18] TEZUKA, S.: Uniform Random Numbers: Theory and Practice, The Kluwer International Series in Engineering and Computer Science Vol. 315. Kluwer Academic Publishers, Dordrecht, 1995.
Search in Google Scholar Back to article
[19] _____ Financial applications of Monte Carlo and quasi-Monte Carlo methods, (P. Hellekalek and G. Larcher, eds.) In: Random and Quasi-Random Point Sets. Lecture Notes in Statistics, 138, Springer, (1998), 303–332.10.1007/978-1-4612-1702-2_7
Search in Google Scholar Back to article
[20] _____ On the discrepancy of generalized Niederreiter sequences, Journal of Complexity, 29 (2013), 240–247.10.1016/j.jco.2013.02.001
Search in Google Scholar Back to article
[21] _____ (t, e, s)-sequences in multiple bases, In: The 4-th International Conference on Uniform Distribution Theory, Ostravice, (June, 2014).
Search in Google Scholar Back to article
[22] _____ Improvement on the discrepancy of (t,e, s)-sequences, Tatra Mountains Mathematical Publications, 59 (2014), 27–38.10.2478/tmmp-2014-0016
Search in Google Scholar Back to article
[23] TRAUB, J. F.—WERSCHULZ, A. G.: Complexity and Information, (Lezioni Lincee). Cambridge University Press, 1998.
Search in Google Scholar Back to article
[24] TRAUB, J. F.—WOŹNIAKOWSKI, H.: Breaking intractability, Scientific American, (January 1994), 102–107.10.1038/scientificamerican0194-102
Search in Google Scholar Back to article
[25] WANG, X.: A constructive approach to strong tractability using quasi-Monte Carlo algorithms, Journal of Complexity, 18 (2002), 683–701.10.1006/jcom.2002.0641
Search in Google Scholar Back to article
[26] _____ Strong tractability of multivariate integration using quasi-Monte Carlo algorithms, Mathematics of Computation, 72 (2003), 823–838.10.1090/S0025-5718-02-01440-0
Search in Google Scholar Back to article
[27] WOŹNIAKOWSKI, H.: Average case complexity of multivariate integration, Bulletin of the American Mathematical Society, 24 (1991), 185–194.10.1090/S0273-0979-1991-15985-9
Search in Google Scholar Back to article
[28] _____ Tractability of multivariate problems, Foundations of Computational Mathematics, Hong Kong 2008, London Math. Soc. Lecture Note Ser. Vol. 363, Cambridge University Press, Cambridge 2009, 236–276.10.1017/CBO9781139107068.009
Search in Google Scholar Back to article
[29] XING, C.—NIEDERREITER, H.: A construction of low-discrepancy sequences using global function fields, Acta Arithmetica, 73 (1995), 87–102.10.4064/aa-73-1-87-102
Search in Google Scholar Back to article

Tractability of Multivariate Integration Using Low-Discrepancy Sequences

Abstract

Paradigm

My account