×

Expected integration approximation under general equal measure partition. (English) Zbl 1535.65011

Summary: In this paper, we first use an \(L_2\)-discrepancy bound to give the expected uniform integration approximation for functions in the Sobolev space \(\mathcal{H}^{\mathbf{1}} (K)\) equipped with a reproducing kernel. The concept of stratified sampling under general equal measure partition is introduced into the research. For different sampling modes, we obtain a better convergence order \(O(N^{-1-\frac{1}{d}})\) for the stratified sampling set than for the Monte Carlo sampling method and the Latin hypercube sampling method. Second, we give several expected uniform integration approximation bounds for functions equipped with boundary conditions in the general Sobolev space \(F_{d, q}^{\ast}\), where \(\frac{1}{p}+\frac{1}{q}=1\). Probabilistic \(L_p\)-discrepancy bound under general equal measure partition, including the case of Hilbert space-filling curve-based sampling are employed. All of these give better general results than simple random sampling, and in particular, Hilbert space-filling curve-based sampling gives better results than simple random sampling for the appropriate sample size.

MSC:

65C05 Monte Carlo methods
11K38 Irregularities of distribution, discrepancy
65D32 Numerical quadrature and cubature formulas

References:

[1] Gao, W. W.; Sun, X. P.; Wu, Z. M.; Zhou, X., Multivariate Monte Carlo approximation based on scattered data, SIAM J Sci Comput, 42, 2262-2280, 2020 · Zbl 1489.65020
[2] Dick, J.; Kuo, F.; Sloan, I., High-dimensional integration: The quasi-Monte Carlo way, Acta Numer, 22, 133-288, 2013 · Zbl 1296.65004
[3] Aistleitner, C., Covering numbers, dyadic chaining and discrepancy, J Complexity, 27, 531-540, 2011 · Zbl 1263.11072
[4] Aistleitner, C.; Hofer, M., Probabilistic discrepancy bound for Monte Carlo point sets, Math Comp, 83, 1373-1381, 2014 · Zbl 1285.65002
[5] Halton, J. H., On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer Math, 2, 84-90, 1960 · Zbl 0090.34505
[6] Hammersley, J. M., Monte Carlo methods for solving multivariable problems, Ann New York Acad Sci, 86, 844-874, 1960 · Zbl 0111.12405
[7] Niederreiter, H., Low-discrepancy and low-dispersion sequences, J Number Theory, 30, 51-70, 1988 · Zbl 0651.10034
[8] Brandolini, L.; Colzani, L.; Gigante, G.; Travaglini, G., On the Koksma-Hlawka inequality, J Complexity, 29, 158-172, 2013 · Zbl 1280.26032
[9] Ahmed, A. G.M.; Perrier, H.; Coeurjolly, D., Low-discrepancy blue noise sampling, ACM Trans Graph, 35, 1-13, 2016
[10] Cervellera, C.; Muselli, M., Deterministic design for neural network learning: An approach based on discrepancy, IEEE Trans Neural Netw, 15, 533-544, 2004
[11] Lai, Y., Monte carlo and quasi-monte carlo methods and their applications, 1998, Department of Mathematics, Claremont Graduate University: Department of Mathematics, Claremont Graduate University California, USA, [Ph.D. Dissertation]
[12] Lai, Y., Intermediate rank lattice rules and applications to finance, Appl Numer Math, 59, 1-20, 2009 · Zbl 1161.65003
[13] Niederreiter, H., Random number generation and quasi-monte carlo methods, 1992, SIAM: SIAM Philadelphia · Zbl 0761.65002
[14] Roth, K. F., On irregularities of distribution, Mathematika, 1, 73-79, 1954 · Zbl 0057.28604
[15] Schmidt, W. M., Irregularities of distribution X, (Number theory and algebra, 1977, Academic Press: Academic Press New York), 311-329 · Zbl 0373.10020
[16] Chen, W. W.L.; Skriganov, M. M., Explicit constructions in the classical mean squares problem in irregularities of point distribution, J Reine Angew Math, 545, 67-95, 2002 · Zbl 1083.11049
[17] Skriganov, M. M., Harmonic analysis on totally disconnected groups and irregularities of point distributions, J Reine Angew Math, 600, 25-49, 2006 · Zbl 1115.11047
[18] Fang, K. T.; Ma, C. X.; Winker, P., Centered \(L_2\)-discrepancy of random sampling and latin hypercube design, and construction of uniform designs, Math Comp, 71, 275-296, 2002 · Zbl 0977.68091
[19] Glasserman, P., Monte Carlo methods in financial engineering, (Applications of mathematics (New york) stochastic modelling and applied probability, 2004, Springer-Verlag: Springer-Verlag New York) · Zbl 1038.91045
[20] Pausinger, F.; Steinerberger, S., On the discrepancy of jittered sampling, J Complexity, 33, 199-216, 2016 · Zbl 1330.05022
[21] Zhu, H.; Dick, J., Discrepancy estimates for acceptance-rejection samplers using stratified inputs, (Cools, R.; Nuyens, D., Monte carlo and quasi-monte carlo methods. Monte carlo and quasi-monte carlo methods, Springer proceedings in mathematics and statistics, vol.163, 2016, Springer: Springer Cham) · Zbl 1356.65014
[22] Owen, A. B.; Rudolf, D., A strong law of large numbers for scrambled net integration, SIAM Rev, 63, 360-372, 2021 · Zbl 1509.65022
[23] Kiderlen, M.; Pausinger, F., Discrepancy of stratified samples from partitions of the unit cube, Monatsh Math, 195, 267-306, 2021 · Zbl 1481.11077
[24] Kiderlen, M.; Pausinger, F., On a partition with a lower expected \(L_2\)-discrepancy than classical jittered sampling, J Complexity, 70, Article 101616 pp., 2022 · Zbl 1497.11183
[25] Brauchart, J. S.; Saff, E. B.; Sloan, I. H.; Womersley, R. S., QMC designs: Optimal order quasi Monte Carlo integration schemes on the sphere, Math Comp, 83, 2821-2851, 2014 · Zbl 1315.65003
[26] Novak, E.; Woźniakowski, H., Tractability of multivariate problems, (Volume II: standard information for functionals, 2010, European Mathematical Society) · Zbl 1241.65025
[27] Cucker, F.; Zhou, D. X., Learning theory: an approximation theory viewpoint, 2007, Cambridge University Press · Zbl 1274.41001
[28] Beck, J., Some upper bounds in the theory of irregularities of distribution, Acta Arith, 43, 115-130, 1984 · Zbl 0536.10041
[29] Owen AB. Monte Carlo theory, methods and examples, http://statweb.stanford.edu/owen/mc. · Zbl 0942.65024
[30] He, Z.; Owen, A. B., Extensible grids: Uniform sampling on a space filling curve, J R Stat Soc Ser B, 78, 917-931, 2016 · Zbl 1414.62082
[31] He, Z.; Zhu, L., Asymptotic normality of extensible grid sampling, Stat Comput, 29, 53-65, 2019 · Zbl 1430.62052
[32] Dick, J.; Pillichshammer, F., Discrepancy theory and Quasi-Monte Carlo integration, (A panorama of discrepancy theory, 2014, Springer: Springer Cham), 539-619 · Zbl 1358.11086
[33] McKay, M. D.; Conover, W. J.; Beckman, R. J., A comparison of three methods for selecting values of input variables in the analysis of output from a computer code, Technometrics, 21, 239-245, 1979 · Zbl 0415.62011
[34] Owen, A. B., A central limit theorem for Latin Hypercube sampling, J R Stat Soc Ser B-Stat Methodol, 54, 541-551, 1992 · Zbl 0776.62041
[35] Owen, A. B., Controlling correlations in Latin Hypercube samples, J Amer Statist Assoc, 89, 1517-1522, 1994 · Zbl 0813.65060
[36] Owen, A. B., Monte Carlo variance of scrambled net quadrature, SIAM J Numer Anal, 34, 1884-1910, 1997 · Zbl 0890.65023
[37] Steinerberger, S., The asymptotic behavior of the average \(L_p\)-discrepancies and a randomized discrepancy, Electron J Combin, 17, 18, 2010, Research Paper 106 · Zbl 1217.11072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.