Top

Published in:

2024 | OriginalPaper | Chapter

A Randomised Lattice Rule Algorithm with Pre-determined Generating Vector and Random Number of Points for Korobov Spaces with \(0 < \alpha \le 1/2\)

Authors : Dirk Nuyens, Laurence Wilkes

Published in: Monte Carlo and Quasi-Monte Carlo Methods

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In previous work [12], we showed that a lattice rule with a pre-determined generating vector but random number of points can achieve the near optimal convergence of \(O(n^{-\alpha -1/2+\epsilon })\), \(\epsilon > 0\), for the worst case expected error, commonly referred to as the randomised error, for numerical integration of high-dimensional functions in the Korobov space with smoothness \(\alpha > 1/2\). Compared to the optimal deterministic rate of \(O(n^{-\alpha +\epsilon })\), \(\epsilon > 0\), such a randomised algorithm is capable of an extra half in the rate of convergence. In this paper, we show that a pre-determined generating vector also exists in the case of \(0 < \alpha \le 1/2\). Also here we obtain the near optimal convergence of \(O(n^{-\alpha -1/2+\epsilon })\), \(\epsilon > 0\); or in more detail, we obtain \(O(\sqrt{r} \, n^{-\alpha -1/2+1/(2r)+\epsilon '})\) which holds for any choices of \(\epsilon ' > 0\) and \(r \in {\mathbb {N}}\) with \(r > 1/(2\alpha )\).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter The Order Barrier for the -approximation of the Log-Heston SDE at a Single Point

next chapter Generator Matrices by Solving Integer Linear Programs

Bakhvalov, N.S.: An estimate of the mean remainder term in quadrature formulae. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 1, 64–77 (1961)

Berend, D., Tassa, T.: Improved bounds on Bell numbers and on moments of sums of random variables. Probab. Math. Stat. 30(2), 185–205 (2010)MathSciNet

de La Vallée Poussin, C.J.: Recherches analytiques sur la théorie des nombres premiers. Première partie. La fonction \(\zeta (s)\) de Riemann et les nombres premiers en général, suivi d’un appendice sur des réflexions applicables à une formule donnée par Riemann. Ann. Soc. Scient. Bruxelles, deuxième partie 20, 183–256 (1896)

de La Vallée Poussin, C.J.: Sur la fonction \(\zeta (s)\) de Riemann et le nombre des nombres premiers inférieurs à une limite donnée. Mémoires couronnés et autres Mémoires in-8 publiés par l’Académie royale de Belgique 49, 74 (1899)

Dick, J.: Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands. Ann. Stat. 39(3), 1372–1398 (2011)MathSciNetCrossRef

Dick, J., Goda, T., Suzuki, K.: Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate. Math. Comp. 91, 2771–2801 (2022)

Dick, J., Kritzer, P., Pillichshammer, F.: Lattice Rules: Numerical Integration, Approximation, and Discrepancy. Springer International Publishing (2022)

Frolov, K.K.: Upper error bounds for quadrature formulas on function classes. Dokl. Akad. Nauk SSSR 231(4), 818–821 (1976)MathSciNet

Goda, T., L’Ecuyer, P.: Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights. SIAM J. Sci. Comput. 44(4), A2765–A2788 (2022)MathSciNetCrossRef

10.

Krieg, D., Novak, E.: A universal algorithm for multivariate integration. Found. Comput. Math. 17, 895–916 (2017)MathSciNetCrossRef

11.

Kritzer, P., Kuo, F.Y., Nuyens, D., Ullrich, M.: Lattice rules with random \(n\) achieve nearly the optimal \({\cal{O}}(n^{-\alpha -1/2})\) error independently of the dimension. J. Approx. Theory 240, 96–113 (2019)

12.

Kuo, F.Y., D. Nuyens, and L. Wilkes. Random-prime-fixed-vector randomised lattice-based algorithm for high-dimensional integration. J. Complexity 79, 101785 (2023). https://doi.org/10.1016/j.jco.2023.101785. https://www.sciencedirect.com/science/article/abs/pii/S0885064X23000547

13.

Mariconda, C., Tonolo, A.: Discrete Calculus: Methods for Counting. Springer International Publishing (2016)

14.

Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics (1992)

15.

Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems: Volume I: Linear information. EMS Tracts in Mathematics. European Mathematical Society (2008)

16.

Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems: Volume II: Standard Information for Functionals. EMS Tracts in Mathematics. European Mathematical Society (2010)

17.

Nuyens, D.: The Construction of Good Lattice Rules and Polynomial Lattice Rules, pp. 223–256. De Gruyter, Berlin, Boston (2014)

18.

Nuyens, D., Suzuki, Y.: Scaled lattice rules for integration on \(\mathbb{R} ^d\) achieving higher-order convergence with error analysis in terms of orthogonal projections onto periodic spaces. Math. Comp. 92, 307–347 (2023)

19.

Owen, A.B.: Randomly permuted \((t,m,s)\)-nets and \((t, s)\)-sequences. In: Niederreiter, H., Shiue, P.J.S.: (eds.) Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, pp. 299–317. Springer, New York, NY (1995)

20.

Owen, A.B.: Monte Carlo variance of scrambled net quadrature. SIAM J. Numer. Anal. 34(5), 1884–1910 (1997)MathSciNetCrossRef

21.

Sloan, I.H., Joe, S.: Lattice Methods for Multiple Integration. Oxford University Press (1994)

22.

Sloan, I.H., Kuo, F.Y., Joe, S.: On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces. Math. Comp. 71, 1609–1640 (2002)

23.

Sloan, I.H., Woźniakowski, H.: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals? J. Complexity 14(1), 1–33 (1998)

24.

Sloan, I.H., Woźniakowski, H.: Tractability of multivariate integration for weighted Korobov classes. J. Complexity 17(4), 697–721 (2001)

25.

Ullrich, M.: A Monte Carlo method for integration of multivariate smooth functions. SIAM J. Numer. Anal. 55, 1188–1200 (2017)MathSciNetCrossRef

Title: A Randomised Lattice Rule Algorithm with Pre-determined Generating Vector and Random Number of Points for Korobov Spaces with
Authors: Dirk Nuyens
Laurence Wilkes
Publisher: Springer International Publishing
Book: Monte Carlo and Quasi-Monte Carlo Methods
Print ISBN: 978-3-031-59761-9

Electronic ISBN: 978-3-031-59762-6

Copyright Year: 2024
DOI: https://doi.org/10.1007/978-3-031-59762-6_25

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"