</script>">
Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 15 (2018) open journal systems 


Equidistribution, uniform distribution: a probabilist's perspective

Vlada Limic, IRMA
Nedzad Limic, University of Zagreb


Abstract

The theory of equidistribution is about hundred years old, and has been developed primarily by number theorists and theoretical computer scientists. A motivated uninitiated peer could encounter difficulties perusing the literature, due to various synonyms and polysemes used by different schools. One purpose of this note is to provide a short introduction for probabilists. We proceed by recalling a perspective originating in a work of the second author from 2002. Using it, various new examples of completely uniformly distributed \(\mathsf{mod}~1\) sequences, in the “metric” (meaning almost sure stochastic) sense, can be easily exhibited. In particular, we point out natural generalizations of the original \(p\)-multiply equidistributed sequence \(k^p\, t\ {\mathsf{mod}}~1\), \(k\geq1\) (where \(p\in\mathbb{N}\) and \(t\in[0,1]\)), due to Hermann Weyl in 1916. In passing, we also derive a Weyl-like criterion for weakly completely equidistributed (also known as WCUD) sequences, of substantial recent interest in MCMC simulations.

The translation from number theory to probability language brings into focus a version of the strong law of large numbers for weakly correlated complex-valued random variables, the study of which was initiated by Weyl in the aforementioned manuscript, followed up by Davenport, Erdős and LeVeque in 1963, and greatly extended by Russell Lyons in 1988. In this context, an application to \(\infty\)-distributed Koksma's numbers \(t^k\ {\mathsf{mod}}~1\), \(k\geq1\) (where \(t\in[1,a]\) for some \(a>1\)), and an important generalization by Niederreiter and Tichy from 1985 are discussed.

The paper contains negligible amount of new mathematics in the strict sense, but its perspective and open questions included in the end could be of considerable interest to probabilists and statisticians, as well as certain computer scientists and number theorists.



AMS 2000 subject classifications: Primary 60-01, 11-02; secondary 11K45, 65C10, 60F15.

Keywords: Equidistribution, completely equidistributed, completely uniformly distributed, ∞-distributed, metric theory, weakly completely uniformly distributed, pseudo-random numbers, Weyl criterion, strong law of large numbers, weakly correlated, dependent random variables.

Creative Common LOGO

Full Text: PDF
Limic, Vlada, Limic, Nedzad, Equidistribution, uniform distribution: a probabilist's perspective, Probability Surveys, 15, (2018), 131-155 (electronic). DOI: 10.1214/17-PS295.

References

[Ai]     C. Aistleitner, Quantitative uniform distribution results for geometric progressions. Israel J. Math., 204, 1: 155–197, 2014. MR3273455

[AB1]     C. Aistleitner and I. Berkes, On the central limit theorem for f(nkx). Probab. Theory Related Fields, 146, 1–2:267–289, 2010. MR2550364

[AB2]     C. Aistleitner and I. Berkes, Probability and metric discrepancy theory. Stoch. Dyn., 11, 183–207, 2011. MR2771348

[AB3]     C. Aistleitner and I. Berkes, Limit distributions in metric discrepancy theory. Monatsh. Math., 169, 3–4: 253—265, 2013. MR3019283

[ABT]     C. Aistleitner, I. Berkes, and R.F. Tichy, Lacunary sequences and permutations. Dependence in probability, analysis and number theory. A volume in memory of Walter Philipp, Kendrick Press. 35–49, 2010. MR2731043

[Bu1]     K. Burdzy, The Search for Certainty. World Scientific, 2009. MR2510150

[Bu2]     K. Burdzy, Resonance: From Probability to Epistemology and Back. Imperial College Press, 2016. MR3468703

[Du]     R. Durrett, Probability: theory and examples, 3rd edition. Duxbury advanced series, 2005. MR1609153

[CDO]     S. Chen, J. Dick, and A.B. Owen, Consistency of Markov chain quasi-Monte Carlo on continuous state spaces. Ann. Statist., 39, 2:673–701, 2011. MR2816335

[CMNO]     S. Chen, M. Matsumoto, T. Nishimura, and A.B. Owen, New inputs and methods for Markov chain quasi-Monte Carlo. In Monte Carlo and quasi-Monte Carlo methods 2010. Springer Proc. Math. Stat.  23, 313–327, Springer, 2012. MR3173841

[DELV]     H. Davenport, P. Erdʺo s, and W.J. LeVeque, On Weyl’s criterion for uniform distribution. Michigan Math. J., 10, 3:311–314, 1963. MR0153656

[DT]     M. Drmota and R.F. Tichy, Sequences, Discrepancies, and Applications. Lecture Notes in Mathematics 1651, Springer, Berlin, 1997. MR1470456

[DTW]     M. Drmota, R.F Tichy, and R. Winkler, Completely uniformly distributed sequences of matrices. In: Number-Theoretic Analysis. Lecture Notes in Math. 1452, pp. 43–57, Springer, 1990. MR1084637

[EK]     P. Erdʺo s and M. Kac, The Gaussian law of errors in the theory of additive number theoretic functions. Amer. J. Math., 62, 1:738–742, 1940. MR0002374

[Fr]     J.N. Franklin, Deterministic simulation of random processes, Math. Comp., 17, 28–59, 1963. MR0149640

[Go]     M. Goldstern, Eine Klasse volständig gleichverteiler Folgen. In Zahlentheoretishe Analysis, II Lecture Notes in Math. 1262, pp. 37–45, Springer, 1987. MR1012958

[Ho1]     P.J. Holewijn, Note on Weyl’s criterion and the uniform distribution of independent random variables. Ann. Math. Stat. 40, 1124–1125, 1969. MR0240855

[Ho2]     P.J. Holewijn, On the Uniform Distribution of Sequences of Random Variables. Z. Wahrscheinlichkeitstheorie verw. Geb., 14, 89–92, 1969. MR0264735

[Ka1]     M. Kac, Statistical Independence in Probability, Analysis and Number Theory. Mathematical Association of America, 1959. MR0110114

[Ka2]     M. Kac, Probability methods in some problems of analysis and number theory. Bull. Amer. Math. Soc., 55, 641–665, 1949. MR0031504

[Kem]     J.H.B. Kemperman, Probability methods in the theory of distributions modulo one. Compositio Mathematica, 16 106–137, 1964. MR0173281

[Ke1]     H. Kesten, Uniform Distribution mod 1. Ann. Math.,71, 2:445–471, 1960. MR0113864

[Ke2]     H. Kesten, Uniform Distribution mod 1 (II). Acta Arith., 7, 4:355–380, 1962. MR0142532

[Kh]     D. Khoshnevisan, Normal numbers are normal. Clay Mathematics Institute Annual Report, 15, continued pp. 27—31, 2006.

[Kn1]     D.E. Knuth, Construction of a random sequence. BIT Numerical Mathematics, 5, 4:246–250, 1965. MR0197434

[Kn2]     D.E. Knuth, The Art of Computer Programming, volume 2/Seminumerical Algorithms, 3rd edition. Addison-Wesley, 1997. MR3077152

[Kol1]     A.N. Kolmogorov, Grundbegriffe der Wahrscheinlichkeitsrechnung, Ergebnisse der Mathematik und ihrer Grenzgebeite. J. Springer, 1933. MR0362415

[Kol2]     A.N. Kolmogorov, Tri podhoda k opredeleniju ponjatija “količevstvo informacii” (Three approaches to the definition of the concept “quantity of information”.). Problemy peredači informacii 1, 3–11, 1965.

[Kok]     J.F. Koksma, Ein mengentheoretischer Satz über die Gleichverteilung modulo Eins. Compositio Math., 2, 250–258, 1935. MR1556918

[Kr1]     N.M. Korobov, On functions with uniformly distributed fractional parts (Russian). Doklady Akad. Nauk SSSR (N.S.), 62, 21–22, 1948. MR0027012

[Kr2]     N.M. Korobov, Some problems on the distribution of fractional parts (Russian). Uspehi Matem. Nauk SSSR (N.S.), 4, 1(29):189–190, 1949. MR0031948

[Kr3]     N.M. Korobov, Concerning some questions of uniform distribution (Russian). Izvestiya Akad. Nauk SSSR. Ser. Mat.  14, 215–238, 1950. MR0037876

[Kr4]     N.M. Korobov, Bounds of trigonometric sums involving completely uniformly distributed functions (Russian). Soviet Math. Dokl., 1, 923–926, 1960. MR0130527

[Kr5]     N.M. Korobov, Exponential Sums and their Applications. Mathematics and Its Applications, 80, Kluwer, 1992. MR1162539

[KN]     L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences. Wiley and Sons, 1974. MR0419394

[Lac]     M.B. Lacaze, Estimation de moyennes et fonctions de répartition de suites d’échantillonnage. Ann. Inst. Henri Poincaré Probab. Stat., 9, 2:145–165, 1973. MR0356199

[Lam]     M. van Lambalgen, Randomness and Foundations of Probability: von Mises’ axiomatisation of random sequences. Statistics, probability and game theory: Papers in honor of David Blackwell, 347–367, IMS, 1996. MR1481789

[Le1]     L. Levin, On the notion of a random sequence. Soviet Math. Dok. 14 1413–1416, 1973.

[Le2]     M.B. Levin, Discrepancy Estimates of Completely Uniformly Distributed and Pseudorandom Number Sequences. Internat. Math. Res. Notices 22, 1231–1251, 1999. MR1731474

[Li]     N. Limić, On completely equidistributed numbers. Math. Commun. 7, 103–111, 2002. MR1952752

[Lo]     R.M. Loynes, Some results in the probabilistic theory of asymptotic uniform distribution modulo 1. Z. Wahrscheinlichkeitstheorie verw. Geb. 26, 33–41, 1973. MR0329051

[Ly]     R. Lyons, Strong laws of large numbers for weakly correlated random variables. Michigan Math. J., 35, 3:353–359, 1988. MR0978305

[ML]     P. Martin-Löf, The definition of random sequences. Inform. Control 9, 602–619, 1966. MR0223179

[MF]     M. Mendès France, Nombres normaux. Applications aux fonctions pseudo-aléatoires. J. Anal. Math., 20, 1:1–56, 1967. MR0220683

[Ms]     R. von Mises, Probability, Statistics and Truth, 2nd revised English edn., Dover, New York, 1957. MR0090158

[NT1]     H. Niederreiter and R.F. Tichy, Solution of a problem of Knuth on complete uniform distribution of sequences. Mathematika, 32, 26–32, 1985. MR0817103

[NT2]     H. Niederreiter and R.F. Tichy, Metric theorems on uniform distribution and approximation theory. Journées arithmétiques de Besançon (Besançon, 1985). Astérisque 147–148, 319–323, 1987. MR0891439

[OT]     A.B. Owen and S.D. Tribble, A quasi-Monte Carlo Metropolis algorithm. Proc. Natl. Acad. Sci. USA, 102, 25:8844–8849, 2005. MR2168266

[SZ]     R. Salem and A. Zygmund, On Lacunary Trigonometric Series. Proc. Natl. Acad. Sci. USA, 33, 11:333–338, 1947. MR0022263

[SP]     O. Strauch and S. Porubský, Distribution of Sequences: A Sampler. Peter Lang, 2005. MR2290224

[Ti]     R.F. Tichy, Ein metrischer Satz über vollständig gleichverteile Folgen. Acta Arith. 48, 2:197–207, 1987. MR0895440

[TO]     S.D. Tribble and A.B. Owen, Construction of weakly CUD sequences for MCMC sampling. Electron. J. Stat., 2, 634–660, 2008. MR2426105

[We]     H. Weyl, Über die Gleichverteilung von Zahlen mod. Eins. Math. Ann., 77, 313–352, 1916. MR1511862
Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787