On the limit distribution of the well-distribution measure of random binary sequences
Journal de théorie des nombres de Bordeaux, Volume 25 (2013) no. 2, p. 245-259

We prove the existence of a limit distribution of the normalized well-distribution measure W(E N )/N (as N) for random binary sequences E N , by this means solving a problem posed by Alon, Kohayakawa, Mauduit, Moreira and Rödl.

Nous prouvons l’existence d’une distribution limite de la mesure de bonne distribution normalisée W(E N )/N (quand N) pour des suites binaires aléatoires E N . Par ce moyen, nous résolvons un problème posé par Alon, Kohayakawa, Mauduit, Moreira et Rödl.

@article{JTNB_2013__25_2_245_0,
     author = {Aistleitner, Christoph},
     title = {On the limit distribution of the well-distribution measure of random binary sequences},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {25},
     number = {2},
     year = {2013},
     pages = {245-259},
     doi = {10.5802/jtnb.834},
     mrnumber = {3228306},
     zbl = {1282.11094},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2013__25_2_245_0}
}
Aistleitner, Christoph. On the limit distribution of the well-distribution measure of random binary sequences. Journal de théorie des nombres de Bordeaux, Volume 25 (2013) no. 2, pp. 245-259. doi : 10.5802/jtnb.834. http://www.numdam.org/item/JTNB_2013__25_2_245_0/

[1] N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, and V. Rödl, Measures of pseudorandomness for finite sequences: minimal values. Combin. Probab. Comput. 15(1-2) (2006), 1–29. | MR 2195573 | Zbl 1084.11043

[2] N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, and V. Rödl. Measures of pseudorandomness for finite sequences: typical values. Proc. Lond. Math. Soc. (3), 95(3) (2007), 778–812. | MR 2368283 | Zbl 1124.68084

[3] N. Alon, S. Litsyn, and A. Shpunt. Typical peak sidelobe level of binary sequences. IEEE Trans. Inform. Theory, 56(1) (2010), 545–554. | MR 2589463

[4] I. Berkes, W. Philipp, and R. F. Tichy. Empirical processes in probabilistic number theory: the LIL for the discrepancy of (n k ω)mod1. Illinois J. Math., 50(1-4) (2006), 107–145. | MR 2247826 | Zbl 1145.11058

[5] I. Berkes, W. Philipp, and R. F. Tichy. Pseudorandom numbers and entropy conditions. J. Complexity, 23(4-6) (2007), 516–527. | MR 2372011 | Zbl 1133.11045

[6] P. Billingsley. /it Convergence of probability measures. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons Inc., New York, second edition (1999). | MR 1700749 | Zbl 0172.21201

[7] J. Cassaigne, C. Mauduit, and A. Sárközy. On finite pseudorandom binary sequences. VII. The measures of pseudorandomness. Acta Arith., 103(2) (2002), 97–118. | MR 1904866 | Zbl 1126.11330

[8] W. Feller. The asymptotic distribution of the range of sums of independent random variables. Ann. Math. Statistics, 22 (1951), 427–432. | MR 42626 | Zbl 0043.34201

[9] P. Hubert, C. Mauduit, and A. Sárközy. On pseudorandom binary lattices. Acta Arith., 125(1) (2006), 51–62. | MR 2275217 | Zbl 1155.11044

[10] Y. Kohayakawa, C. Mauduit, C. G. Moreira, and V. Rödl. Measures of pseudorandomness for finite sequences: minimum and typical values. In Proceedings of WORDS’03, volume 27 of TUCS Gen. Publ., (2003), 159–169. Turku Cent. Comput. Sci., Turku. | MR 2081349 | Zbl 1183.11043

[11] C. Mauduit and A. Sárközy. On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol. Acta Arith., 82(4) (1997), 365–377. | MR 1483689 | Zbl 0886.11048

[12] A. W. van der Vaart and J. A. Wellner. Weak convergence and empirical processes. Springer Series in Statistics. Springer-Verlag, New York, (1996). | MR 1385671 | Zbl 0862.60002