On the limit distribution of the well-distribution measure of random binary sequences

Christoph Aistleitner

doi:10.5802/jtnb.834

Christoph Aistleitner ¹

¹ TU Graz, Department of Analysis and Computational Number Theory (Math A), Steyrergasse 30/II 8010 Graz, Austria

Journal de théorie des nombres de Bordeaux, Volume 25 (2013) no. 2, pp. 245-259.

Abstract
Résumé

We prove the existence of a limit distribution of the normalized well-distribution measure $W (E_{N}) / \sqrt{N}$ (as $N \to \infty$ ) 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}) / \sqrt{N}$ (quand $N \to \infty$ ) 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.

MR Zbl

DOI: 10.5802/jtnb.834

Author's affiliations:

Christoph Aistleitner ¹

¹ TU Graz, Department of Analysis and Computational Number Theory (Math A), Steyrergasse 30/II 8010 Graz, Austria

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

TY  - JOUR
AU  - Christoph Aistleitner
TI  - On the limit distribution of the well-distribution measure of random binary sequences
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2013
SP  - 245
EP  - 259
VL  - 25
IS  - 2
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.834/
DO  - 10.5802/jtnb.834
LA  - en
ID  - JTNB_2013__25_2_245_0
ER  -

%0 Journal Article
%A Christoph Aistleitner
%T On the limit distribution of the well-distribution measure of random binary sequences
%J Journal de théorie des nombres de Bordeaux
%D 2013
%P 245-259
%V 25
%N 2
%I Société Arithmétique de Bordeaux
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.834/
%R 10.5802/jtnb.834
%G en
%F JTNB_2013__25_2_245_0

Christoph Aistleitner. 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. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.834/

References
Cited by

[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 | Zbl

[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 | Zbl

[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

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

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

[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 | Zbl

[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. | EuDML | MR | Zbl

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

Cited by Sources: