×

The generalized and modified Halton sequences in Cantor bases. (English) Zbl 1426.11074

A standard problem in numerical analysis is estimating the integral of a function, through a knowledge of its value at a finite number of points of the sequence. These points usually are chosen as the first \(N\) elements of stochastic or deterministic low-discrepancy sequences.
In the present paper the authors consider two variants of modification of the classical Halton sequence.
The first modification is the construction of the Halton sequence in a generalized number system, called also the Cantor expansion, with respect to arbitrary sequences of permutations of the Cantor bases.
The second modification is that certain conditions on the sequences of permutations of the Cantor bases which are analogous to the modified Halton sequence introduced by E. I. Atanassov [Math. Balk., New Ser. 18, No. 1–2, 15–32 (2004; Zbl 1088.11058)] are imposed. It is shown that this modified Halton sequence in Cantor bases attains a better estimate of the star discrepancy bound than the generalized Halton sequence in Cantor bases.
In the Introduction of the paper the constructive principles of the original van der Corput sequence and its generalizations in a fixed and variable bases are presented. Some results, related with estimations of the star discrepancy are reminded.
In Section 2, the concept of a generalized number system, called also the Cantor expansion is introduced. Then, generalized Halton sequences induced by this generalized system are defined. In Theorem 1, an estimation of the star discrepancy of the generalized Halton sequences in bounded Cantor bases is given. This estimation gives the order \(\mathcal{O}\left( \frac{(\log N)^s}{N}\right)\) of the star discrepancy of the generalized Halton sequences.
In Section 3, a special class of generalized Halton sequences in Cantor bases that involves deep periodicity properties is introduced. This can be considered as a generalization of Atanassov’s modified Halton sequences. The notion of the so-called admissible sequences of integers is introduced. The constructive principle of the so-called modified Halton sequences in Cantor bases is given. In Theorem 2, the order \(\mathcal{O}\left( \frac{(\log N)^s}{N}\right)\) of the star discrepancy of the modified Halton sequence in Cantor bases \(p_1, p_2, \dots, p_s\) is obtained. Theorem 2 gives a lower constant \(c = c(p_1, p_2, \dots, p_s)\) than the constant \(c = c(b_1, b_2, \dots, bs)\) provided in Theorem 1. Although the modified Halton sequence in Cantor bases do not attain a lower estimate of the discrepancy bound than Atanassov’s modified Halton sequences. The developed method of estimation of the discrepancy gives more variety of sequences with similar estimated bound.
In Section 4, five lemmas are presented and Theorem 1 is proved.
In Section 5, new five lemmas are presented and Theorem 2 is proved.
In Section 6, the original concept of Hammersley which uses a \((s-1)\)-dimensional Halton sequence to construct \(s\)-dimensional finite point set is extended to the concept of the generalized Hammersley point set in Cantor bases. In Theorem 3, an estimation and an order \(\mathcal{O}\left( \frac{(\log N)^{s-1}}{N}\right)\) of the star discrepancy of the generalized Hammersley point set in Cantor bases are obtained.

MSC:

11K31 Special sequences
11J71 Distribution modulo one
11K38 Irregularities of distribution, discrepancy
11K36 Well-distributed sequences and other variations
11K45 Pseudo-random numbers; Monte Carlo methods
65C05 Monte Carlo methods
65C10 Random number generation in numerical analysis

Citations:

Zbl 1088.11058
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Atanassov, E., On the discrepancy of the Halton sequences, Math. Balk. New Ser., 18, 15-32, (2004) · Zbl 1088.11058
[2] Braaten, E.; Weller, G., An improved low-discrepancy sequence for multidimensional quasi-Monte Carlo integration, J. Comput. Phys., 33, 249-258, (1979) · Zbl 0426.65001 · doi:10.1016/0021-9991(79)90019-6
[3] Chaix, H.; Faure, H., Discrépance et diaphonie en dimension un, Acta Arith., 63, 103-141, (1993) · Zbl 0772.11022 · doi:10.4064/aa-63-2-103-141
[4] Corput, J., Verteilungsfunktionen, Proc. Ned. Akad. v. Wet., 38, 813-821, (1935) · JFM 61.0202.08
[5] Dick, J., Pillichshammer, F.: Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge (2010). https://doi.org/10.1017/CBO9780511761188 · Zbl 1282.65012 · doi:10.1017/CBO9780511761188
[6] Faure, H., Discrépance de suites associées à un système de numération, C. R. Acad. Sci. Paris Sér. A B, 286, a293-a296, (1978) · Zbl 0378.10032
[7] Faure, H.: Suites à faible discrépance dans \({\mathbb{T}}^s\). Publ. Dép. math., Université de Limoges, Limoges (1980)
[8] Faure, H., Discrépances de suites associées à un système de numération (en dimension un), Bull. Soc. Math. Fr., 109, 143-182, (1981) · Zbl 0488.10052 · doi:10.24033/bsmf.1935
[9] Faure, H., Discrépance de suites associées à un système de numération (en dimension \(s\)), Acta Arith., 41, 337-351, (1982) · Zbl 0442.10035 · doi:10.4064/aa-41-4-337-351
[10] Haddley, A.; Lertchoosakul, P.; Nair, R., The Halton sequence and its discrepancy in the Cantor expansion, Period. Math. Hung., 75, 128-141, (2017) · Zbl 1399.11125 · doi:10.1007/s10998-016-0169-5
[11] Halton, J., On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math., 2, 84-90, (1960) · Zbl 0090.34505 · doi:10.1007/BF01386213
[12] Hewitt, E., Ross, K.: Abstract Harmonic Analysis: Structure of Topological Groups, Integration Theory, Group Representations, vol. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 115. Springer, Berlin (1979)
[13] Hofer, M.; Iacò, M.; Tichy, R., Ergodic properties of \(\beta \)-adic Halton sequences, Ergod. Theory Dyn. Syst., 35, 895-909, (2015) · Zbl 1395.11106 · doi:10.1017/etds.2013.70
[14] Hofer, R.; Pillichshammer, F.; Pirsic, G., Distribution properties of sequences generated by \(Q\)-additive functions with respect to Cantor representation of integers, Acta Arith., 138, 179-200, (2009) · Zbl 1228.11114 · doi:10.4064/aa138-2-6
[15] Lemieux, C.: Monte Carlo and Quasi-Monte Carlo Sampling. Springer Series in Statistics. Springer, New York (2009) · Zbl 1269.65001
[16] Leobacher, G., Pillichshammer, F.: Introduction to Quasi-Monte Carlo Integration and Applications. Compact Textbook in Mathematics. Birkhäuser/Springer, Cham (2014). https://doi.org/10.1007/978-3-319-03425-6 · Zbl 1309.65006 · doi:10.1007/978-3-319-03425-6
[17] Lertchoosakul, P.; Nair, R., Distribution functions for subsequences of the van der Corput sequence, Indag. Math. (N.S.), 24, 593-601, (2013) · Zbl 1282.11091 · doi:10.1016/j.indag.2013.03.006
[18] Meijer, H., The discrepancy of a \(g\)-adic sequence, Nederl. Akad. Wetensch. Proc. Ser. A 71=Indag. Math., 30, 54-66, (1968) · Zbl 0155.37801 · doi:10.1016/S1385-7258(68)50007-6
[19] Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1992). https://doi.org/10.1137/1.9781611970081 · Zbl 0761.65002 · doi:10.1137/1.9781611970081
[20] Roth, K., On irregularities of distribution, Mathematika, 1, 73-79, (1954) · Zbl 0057.28604 · doi:10.1112/S0025579300000541
[21] Schmidt, W., Irregularities of distribution. VII, Acta Arith., 21, 45-50, (1972) · Zbl 0244.10035 · doi:10.4064/aa-21-1-45-50
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.