Bounds of random star discrepancy for HSFC-based sampling

Xiaoda Xu; Xiaoda Xu

doi:10.3934/math.2025255

AIMS Mathematics

2025, Volume 10, Issue 3: 5532-5551. doi: 10.3934/math.2025255

Previous Article Next Article

Research article

Bounds of random star discrepancy for HSFC-based sampling

Xiaoda Xu ^,

School of Mathematics and Science, Suqian University, Suqian 223800, China

Received: 12 October 2024 Revised: 09 February 2025 Accepted: 24 February 2025 Published: 12 March 2025
MSC : 11K38, 65C10, 65D30

This paper is dedicated to the estimation of the probabilistic upper bounds of star discrepancy for Hilbert's space filling curve (HSFC) sampling. The primary concept revolves around the stratified random sampling method, with the relaxation of the stringent requirement for a sampling number $ N = m^d $ in jittered sampling. We leverage the benefits of this sampling method to achieve superior results compared to Monte Carlo (MC) sampling. We also provide applications of the main result, which pertain to weighted star discrepancy, $ L_2 $-discrepancy, integration approximation in certain function spaces and examples in finance.
- star discrepancy,
- stratified sampling,
- $ \delta $-covers,
- HSFC sampling,
- integration approximation
Citation: Xiaoda Xu. Bounds of random star discrepancy for HSFC-based sampling[J]. AIMS Mathematics, 2025, 10(3): 5532-5551. doi: 10.3934/math.2025255

Related Papers:

Abstract

This paper is dedicated to the estimation of the probabilistic upper bounds of star discrepancy for Hilbert's space filling curve (HSFC) sampling. The primary concept revolves around the stratified random sampling method, with the relaxation of the stringent requirement for a sampling number $ N = m^d $ in jittered sampling. We leverage the benefits of this sampling method to achieve superior results compared to Monte Carlo (MC) sampling. We also provide applications of the main result, which pertain to weighted star discrepancy, $ L_2 $-discrepancy, integration approximation in certain function spaces and examples in finance.

References

[1]	M. Pharr, W. Jakob, G. Humphreys, Physically based rendering: from theory to implementation, Morgan Kaufmann Publishers Inc., 2016.
[2]	R. Ramamoorthi, J. Anderson, M. Meyer, D. Nowrouzezahrai, A theory of Monte Carlo visibility sampling, ACM Trans. Graph., 31 (2012), 1–16. https://doi.org/10.1145/2231816.223181 doi: 10.1145/2231816.223181
[3]	A. Pilleboue, G. Singh, D. Coeurjolly, M. Kazhdan, V. Ostromoukhov, Variance analysis for Monte Carlo integration, ACM Trans. Graph., 34 (2015), 1–14. https://doi.org/10.1145/2766930 doi: 10.1145/2766930
[4]	Y. Lai, Monte Carlo and quasi-Monte Carlo methods and their applications, Ph.D. Dissertation, Claremont Graduate University, 1999.
[5]	Y. Z. Lai, Intermediate rank lattice rules and applications to finance, Appl. Numer. Math., 59 (2009), 1–20. https://doi.org/10.1016/j.apnum.2007.11.024 doi: 10.1016/j.apnum.2007.11.024
[6]	J. Dick, F. Pillichshammer, Digital nets and sequences, Cambridge University Press, 2010.
[7]	C. Cervellera, M. Muselli, Deterministic design for neural network learning: an approach based on discrepancy, IEEE Trans. Neural Netw., 15 (2004), 533–544. https://doi.org/10.1109/TNN.2004.824413 doi: 10.1109/TNN.2004.824413
[8]	A. G. M. Ahmed, H. Perrier, D. Coeurjolly, V. Ostromoukhov, J. W. Guo, D. M. Yan, et al., Low-discrepancy blue noise sampling, ACM Trans. Graph., 35 (2016), 1–13. https://doi.org/10.1145/2980179.2980218 doi: 10.1145/2980179.2980218
[9]	S. Heinrich, E. Novak, G. W. Wasilkowski, H. Woźniakowski, The inverse of the star-discrepancy depends linearly on the dimension, Acta Arith., 96 (2001), 279–302.
[10]	C. Aistleitner, Covering numbers, dyadic chaining and discrepancy, J. Complexity, 27 (2011), 531–540. https://doi.org/10.1016/j.jco.2011.03.001 doi: 10.1016/j.jco.2011.03.001
[11]	M. Gnewuch, N. Hebbinghaus, Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples, Ann. Appl. Probab., 31 (2021), 1944–1965.
[12]	B. Doerr, A sharp discrepancy bound for jittered sampling, Math. Comp., 91 (2022), 1871–1892. https://doi.org/10.1090/mcom/3727 doi: 10.1090/mcom/3727
[13]	N. Chopin, H. J. Wang, M. Gerber, Adaptive stratified Monte Carlo using decision trees, 2025, arXiv: 2501.04842.
[14]	Z. J. He, A. B. Owen, Extensible grids: uniform sampling on a space filling curve, J. R. Stat. Soc. Ser. B, 78 (2016), 917–931. https://doi.org/10.1111/rssb.12132 doi: 10.1111/rssb.12132
[15]	Z. J. He, L. J. Zhu, Asymptotic normality of extensible grid sampling, Stat. Comput., 29 (2019), 53–65. https://doi.org/10.1007/s11222-017-9794-y doi: 10.1007/s11222-017-9794-y
[16]	J. Y. Tan, Z. J. He, X. Q. Wang, Extensible grid sampling for quantile estimation, Math. Comp., 94 (2025), 763–800.
[17]	L. Ambrosio, A. Colesanti, E. Villa, Outer Minkowski content for some classes of closed sets, Math. Ann., 342 (2008), 727–748. https://doi.org/10.1007/s00208-008-0254-z doi: 10.1007/s00208-008-0254-z
[18]	B. Doerr, M. Gnewuch, A. Srivastav, Bounds and constructions for the star-discrepancy via $\delta$-covers, J. Complexity, 21 (2005), 691–709. https://doi.org/10.1016/j.jco.2005.05.002 doi: 10.1016/j.jco.2005.05.002
[19]	M. Gnewuch, Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy, J. Complexity, 24 (2008), 154–172. https://doi.org/10.1016/j.jco.2007.08.003 doi: 10.1016/j.jco.2007.08.003
[20]	F. Cucker, D. X. Zhou, Learning theory: an approximation theory viewpoint, Cambridge University Press, 2007.
[21]	C. Aistleitner, M. Hofer, Probabilistic discrepancy bound for Monte Carlo point sets, Math. Comp., 83 (2014), 1373–1381. https://doi.org/10.1090/S0025-5718-2013-02773-1 doi: 10.1090/S0025-5718-2013-02773-1
[22]	F. Y. Kuo, I. H. Sloan, Lifting the curse of dimensionality, Not. AMS, 52 (2005), 1320–1328.
[23]	E. Novak, H. Woźniakowski, Tractability of multivariate problems, Volume II: Standard information for functionals, European Mathematical Society, 2010. https://doi.org/10.4171/084
[24]	L. Brandolini, L. Colzani, G. Gigante, G. Travaglini, On the Koksma-Hlawka inequality, J. Complexity, 29 (2013), 158–172. https://doi.org/10.1016/j.jco.2012.10.003 doi: 10.1016/j.jco.2012.10.003
[25]	J. Dick, F. Pillichshammer, Discrepancy theory and quasi-Monte Carlo integration, In: A panorama of discrepancy theory, Cham: Springer, 2014,539–619. https://doi.org/10.1007/978-3-319-04696-9_9
[26]	X. D. Xu, D. Q. Han, Z. Y. Li, X. Q. Lin, Z. D. Qi, L. Zhang, Expected integration approximation under general equal measure partition, Results Appl. Math., 21 (2024), 100419. https://doi.org/10.1016/j.rinam.2023.100419 doi: 10.1016/j.rinam.2023.100419

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)