Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Density Estimation by Monte Carlo and Quasi-Monte Carlo Kapitel lesen Erstes Kapitel lesen

2022 | OriginalPaper | Buchkapitel

Lower Bounds for the Number of Random Bits in Monte Carlo Algorithms

verfasst von : Stefan Heinrich

Erschienen in: Monte Carlo and Quasi-Monte Carlo Methods

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We continue the study of restricted Monte Carlo algorithms in a general setting. Here we show a lower bound for minimal errors in the setting with finite restriction in terms of deterministic minimal errors. This generalizes a result of Heinrich, Novak, and Pfeiffer (in: Monte Carlo and Quasi-Monte Carlo Methods 2002, H. Niederreiter, ed., Springer-Verlag, Berlin, 2004, pp. 27–49) to the adaptive setting. As a consequence, the lower bounds on the number of random bits from that paper also hold in this setting. We also derive a lower bound on the number of needed bits for integration of Lipschitz functions over the Wiener space, complementing a result of Giles, Hefter, Mayer, and Ritter (J. Complexity 54 (2019), 101395).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel On the Distribution of Scrambled Nets Over Unanchored Boxes
Nächstes Kapitel Massively Parallel Path Space Filtering
Literatur
1.
Adams, R.A.: Sobolev Spaces. Academic, New York (1975)
2.
Creutzig, J., Dereich, S., Müller-Gronbach, Th., Ritter, K.: Infinite-dimensional quadrature and approximation of distributions. Found. Comput. Math. 9(4), 391–429 (2009)
3.
Gao, W., Ye, P., Wang, H.: Optimal error bound of restricted Monte Carlo integration on anisotropic Sobolev classes. Progr. Natur. Sci. (English Ed.) 16, 588–593 (2006)
4.
Giles, M.B., Hefter, M., Mayer, L., Ritter, K.: Random bit quadrature and approximation of distributions on Hilbert spaces. Found. Comput. Math. 19, 205–238 (2019)
5.
Giles, M.B., Hefter, M., Mayer, L., Ritter, K.: Random bit multilevel algorithms for stochastic differential equations. J. Complex. 54, 101395 (2019)
6.
Giles, M.B., Hefter, M., Mayer, L., Ritter, K.: An Adaptive Random Bit Multilevel Algorithm for SDEs. In: Hickernell, F., Kritzer, P. (eds.) Multivariate Algorithms and Information-Based Complexity, pp. 15–32. De Gruyter, Berlin/Boston (2020)
7.
Heinrich, S.: Monte Carlo approximation of weakly singular integral operators. J. Complex. 22, 192–219 (2006)
8.
Heinrich, S.: The randomized information complexity of elliptic PDE. J. Complex. 22, 220–249 (2006)
9.
S. Heinrich, Stochastic approximation and applications, In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, pp. 95–131. Springer, Berlin (2012)
10.
Heinrich, S.: On the power of restricted Monte Carlo algorithms. Matrix Ann. 2018, 45–59 (2020). Springer
11.
Heinrich, S., Novak, E., Pfeiffer, H.: How many random bits do we need for Monte Carlo integration? In: Niederreiter, H. (ed.) Monte Carlo and Quasi-Monte Carlo Methods 2002, pp. 27–49. Springer, Berlin (2004)
12.
Novak, E.: Monte Carlo-Verfahren zur numerischen Integration. In: Grossmann, W. et al. (eds.) Proceedings of 4th Pannonian Symposium on Mathematical Statistics, pp. 269–282. Bad Tatzmannsdorf, Austria 1983, Reidel (1985)
13.
Novak, E.: Deterministic and Stochastic Error Bounds in Numerical Analysis, Lecture Notes in Mathematics, vol. 1349. Springer, Berlin (1988)
14.
Novak, E., Pfeiffer, H.: Coin tossing algorithms for integral equations and tractability. Monte Carlo Methods Appl. 10, 491–498 (2004)
15.
Traub, J.F., Wasilkowski, G.W., Woźniakowski, H.: Information-Based Complexity. Academic (1988)
16.
Traub, J.F., Woźniakowski, H.: The Monte Carlo algorithm with a pseudorandom generator. Math. Comput. 58, 323–339 (1992)
17.
Ye, P., Hu, X.: Optimal integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms. J. Approx. Theory 150, 24–47 (2008)
Metadaten
Titel
Lower Bounds for the Number of Random Bits in Monte Carlo Algorithms
verfasst von
Stefan Heinrich
Copyright-Jahr
2022
Buch
Monte Carlo and Quasi-Monte Carlo Methods

Print ISBN: 978-3-030-98318-5

Electronic ISBN: 978-3-030-98319-2

Copyright-Jahr: 2022

DOI
https://doi.org/10.1007/978-3-030-98319-2_6

Premium Partner

    Bildnachweise