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

On Dropping the First Sobol’ Point

verfasst von : Art B. Owen

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

Quasi-Monte Carlo (QMC) points are a substitute for plain Monte Carlo (MC) points that greatly improve integration accuracy under mild assumptions on the problem. Because QMC can give errors that are o(1/n) as \(n\rightarrow \infty \), and randomized versions can attain root mean squared errors that are o(1/n), changing even one point can change the estimate by an amount much larger than the error would have been and worsen the convergence rate. As a result, certain practices that fit quite naturally and intuitively with MC points can be very detrimental to QMC performance. These include thinning, burn-in, and taking sample sizes such as powers of 10, when the QMC points were designed for different sample sizes. This article looks at the effects of a common practice in which one skips the first point of a Sobol’ sequence. The retained points ordinarily fail to be a digital net and when scrambling is applied, skipping over the first point can increase the numerical error by a factor proportional to \(\sqrt{n}\) where n is the number of function evaluations used.

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 A Tool for Custom Construction of QMC and RQMC Point Sets
Nächstes Kapitel On the Distribution of Scrambled Nets Over Unanchored Boxes
Literatur
1.
Balandat, M., Karrer, B., Jiang, D.R., Daulton, S., Letham, B., Wilson, A.G., Bakshy, E.: BoTorch: Bayesian optimization in PyTorch. Technical report (2019). arXiv:​1910.​06403, Facebook Research
2.
Bratley, P., Fox, B.L.: Algorithm 659: implementing Sobol’s quasirandom sequence generator. ACM Trans. Math. Softw. 14(1), 88–100 (1988)
3.
Caflisch, R.E., Morokoff, W., Owen, A.B.: Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension. J. Comput. Financ. 1(1), 27–46 (1997)
4.
Caflisch, R.E., Moskowitz, B.: Modified Monte Carlo methods using quasi-random sequences. In: Niederreiter, H., Shiue, P.J.S. (eds.) Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, pp. 1–16. Springer, New York (1995)
5.
6.
Choi, S.C.T., Hickernell, F.J., Jagadeeswaran, R., McCourt, M.J., Sorokin, A.G.: Quasi-Monte Carlo software. In: Keller, A. (ed.) Monte Carlo and Quasi-Monte Carlo Methods, MCQMC 2020, Springer Proceedings in Mathematics & Statistics. Springer (2022)
7.
van der Corput, J.G.: Verteilungsfunktionen I. Nederl. Akad. Wetensch. Proc. 38, 813–821 (1935)
8.
Davis, P.J., Rabinowitz, P.: Methods of Numerical Integration, 2nd edn. Academic Press, San Diego (1984)
9.
Dick, J.: Walsh spaces containing smooth functions and Quasi-Monte Carlo rules of arbitrarily high order. SIAM J. Numer. Anal. 46(3), 1519–1553 (2008)
10.
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)
11.
Dick, J., Pillichshammer, F.: Digital Sequences, Discrepancy and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge (2010)
12.
Faure, H.: Discrépance de suites associées à un système de numération (en dimension \(s\)). Acta Arithmetica 41, 337–351 (1982)
13.
14.
Halton, J.H.: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numerische Mathematik 2(1), 84–90 (1960)
15.
Hickernell, F.J.: Koksma-Hlawka Inequality. Statistics Reference Online, Wiley StatsRef (2014)
16.
Hickernell, F.J., Lemieux, C., Owen, A.B.: Control variates for Quasi-Monte Carlo (with discussion). Stat. Sci. 20(1), 1–31 (2005)
17.
Hoeffding, W.: A class of statistics with asymptotically normal distribution. Ann. Math. Stat. 19(3), 293–325 (1948)
18.
Joe, S., Kuo, F.Y.: Constructing Sobol’ sequences with better two-dimensional projections. SIAM J. Sci. Comput. 30(5), 2635–2654 (2008)
19.
Kass, R.E., Carlin, B.P., Gelman, A., Neal, R.M.: Markov chain Monte Carlo in practice: a roundtable discussion. Am. Stat. 52(2), 93–100 (1998)
20.
Keller, A., Grünschloß, L.: Parallel Quasi-Monte Carlo integration by partitioning low discrepancy sequences. In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, pp. 487–498. Springer (2012). http://​gruenschloss.​org/​parqmc/​parqmc.​pdf
21.
22.
Kuo, F.Y., Nuyens, D.: Application of Quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation. Found. Comput. Math. 16(6), 1631–1696 (2016)
23.
L’Ecuyer, P.: Quasi-Monte Carlo methods with applications in finance. Financ. Stoch. 13(3), 307–349 (2009)
24.
L’Ecuyer, P., Lemieux, C.: Variance reduction via lattice rules. Manag. Sci. 46(9), 1214–1235 (2000)
25.
Loh, W.L.: On the asymptotic distribution of scrambled net quadrature. Ann. Stat. 31(4), 1282–1324 (2003)
26.
Matoušek, J.: On the L\(^2\)-discrepancy for anchored boxes. J. Complex. 14(4), 527–556 (1998)
27.
Niederreiter, H.: Point sets and sequences with small discrepancy. Monatshefte für Mathematik 104(4), 273–337 (1987)
28.
Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia, PA (1992)
29.
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 (1995)
30.
Owen, A.B.: Monte Carlo variance of scrambled net quadrature. SIAM J. Numer. Anal. 34(5), 1884–1910 (1997)
31.
Owen, A.B.: Scrambled net variance for integrals of smooth functions. Ann. Stat. 25(4), 1541–1562 (1997)
32.
Owen, A.B.: Scrambling Sobol’ and Niederreiter-Xing points. J. Complex. 14(4), 466–489 (1998)
33.
Owen, A.B.: Local antithetic sampling with scrambled nets. Ann. Stat. 36(5), 2319–2343 (2008)
34.
Owen, A.B.: A constraint on extensible quadrature rules. Numerische Mathematik 1–8 (2015)
35.
Owen, A.B.: Statistically efficient thinning of a Markov chain sampler. J. Comput. Graph. Stat. 26(3), 738–744 (2017)
36.
37.
Owen, A.B., Rudolf, D.: A strong law of large numbers for scrambled net integration. SIAM Rev. (2020). To appear
38.
Pan, Z., Owen, A.B.: The nonzero gain coefficients of Sobol’s sequences are always powers of two. Technical report. Stanford University (2021). arXiv:​2106.​10534
39.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., Chintala, S.: PyTorch: An imperative style, high-performance deep learning library. Adv. Neural Inf. Process. Syst. 32, 8026–8037 (2019)
40.
Schürer, R., Schmid, W.C.: MinT-new features and new results. In: L’Ecuyer, P., Owen, A.B. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2008, pp. 501–512. Springer, Berlin (2009)
41.
Sloan, I.H., Joe, S.: Lattice Methods for Multiple Integration. Oxford Science Publications, Oxford (1994)
42.
Sobol’, I.M.: The distribution of points in a cube and the accurate evaluation of integrals. USSR Comput. Math. Math. Phys. 7(4), 86–112 (1967)
43.
Sobol’, I.M.: Multidimensional Quadrature Formulas and Haar Functions. Nauka, Moscow (1969). (In Russian)
44.
Sobol’, I.M.: Asymmetric convergence of approximations of the Monte Carlo method. Comput. Math. Math. Phys. 33(10), 1391–1396 (1993)
45.
Sobol’, I.M., Asotsky, D., Kreinin, A., Kucherenko, S.: Construction and comparison of high-dimensional Sobol’ generators. Wilmott Mag. 2011(56), 64–79 (2011)
46.
47.
Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S.J., Brett, M., Wilson, J., Millman, K.J., Mayorov, N., Nelson, A.R.J., Jones, E., Kern, R., Larson, E., Carey, C.J., Polat, İ., Feng, Y., Moore, E.W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E.A., Harris, C.R., Archibald, A.M., Ribeiro, A.H., Pedregosa, F., van Mulbregt, P., Vijaykumar, A., Bardelli, A.P., Rothberg, A., Hilboll, A., Kloeckner, A., Scopatz, A., Lee, A., Rokem, A., Woods, C.N., Fulton, C., Masson, C., Häggström, C., Fitzgerald, C., Nicholson, D.A., Hagen, D.R., Pasechnik, D.V., Olivetti, E., Martin, E., Wieser, E., Silva, F., Lenders, F., Wilhelm, F., Young, G., Price, G.A., Ingold, G.L., Allen, G.E., Lee, G.R., Audren, H., Probst, I., Dietrich, J.P., Silterra, J., Webber, J.T., Slavič, J., Nothman, J., Buchner, J., Kulick, J., Schönberger, J.L., de Miranda Cardoso, J., Reimer, J., Harrington, J., Rodríguez, J.L.C., Nunez-Iglesias, J., Kuczynski, J., Tritz, K., Thoma, M., Newville, M., Kümmerer, M., Bolingbroke, M., Tartre, M., Pak, M., Smith, N.J., Nowaczyk, N., Shebanov, N., Pavlyk, O., Brodtkorb, P.A., Lee, P., McGibbon, R.T., Feldbauer, R., Lewis, S., Tygier, S., Sievert, S., Vigna, S., Peterson, S., More, S., Pudlik, T., Oshima, T., Pingel, T.J., Robitaille, T.P., Spura, T., Jones, T.R., Cera, T., Leslie, T., Zito, T., Krauss, T., Upadhyay, U., Halchenko, Y.O., Vázquez-Baeza, Y.: SciPy 1.0: fundamental algorithms for scientific computing in Python. Nat. Methods 17(3), 261–272 (2020)
48.
Yue, R.X., Mao, S.S.: On the variance of quadrature over scrambled nets and sequences. Stat. Probab. Lett. 44(3), 267–280 (1999)
Metadaten
Titel
On Dropping the First Sobol’ Point
verfasst von
Art B. Owen
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_4

Premium Partner

    Bildnachweise