Block distribution in random strings

Grabner, Peter J.

Annales de l'Institut Fourier, Tome 43 (1993), p. 539-549 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé
Abstract

Pour presque toute suite binaire infinie issue d’un tirage de Bernoulli $(p, q)$ la fréquence des blocs de longueur $k (N)$ dans les $N$ premiers termes tend asymptotiquement vers la probabilité naturelle du bloc, ceci lorsque $k (N)$ croît comme $\log_{\frac{1}{p}} N - \log_{\frac{1}{p}} N - ψ (N)$ (avec $p \leq q$ ) où $ψ (N)$ tend vers $+ \infty$ . Ce résultat généralise celui de P. Flajolet, P. Kirschenhofer et R.F. Tichy concernant le cas uniforme $p = q = \frac{1}{2}$ .

For almost all infinite binary sequences of Bernoulli trials $(p, q)$ the frequency of blocks of length $k (N)$ in the first $N$ terms tends asymptotically to the probability of the blocks, if $k (N)$ increases like $\log_{\frac{1}{p}} N - \log_{\frac{1}{p}} N - ψ (N)$ (for $p \leq q$ ) where $ψ (N)$ tends to $+ \infty$ . This generalizes a result due to P. Flajolet, P. Kirschenhofer and R.F. Tichy concerning the case $p = q = \frac{1}{2}$ .

Publié le : 1993-01-01

MR 94d:60044 | Zbl 0778.60023

DOI : https://doi.org/10.5802/aif.1345

@article{AIF_1993__43_2_539_0,
     author = {Grabner, Peter J.},
     title = {Block distribution in random strings},
     journal = {Annales de l'Institut Fourier},
     volume = {43},
     year = {1993},
     pages = {539-549},
     doi = {10.5802/aif.1345},
     mrnumber = {94d:60044},
     zbl = {0778.60023},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_1993__43_2_539_0}
}

Grabner, Peter J. Block distribution in random strings. Annales de l'Institut Fourier, Tome 43 (1993) pp. 539-549. doi : 10.5802/aif.1345. http://gdmltest.u-ga.fr/item/AIF_1993__43_2_539_0/

Bibliographie

[Fe] W. Feller, An Introduction to Probability Theory and Its Applications, J. Wiley, New York, 1965.

[FKT] P. Flajolet, P. Kirschenhofer and R.F. Tichy, Deviations from Uniformity in Random Strings, Probab. Th. Rel. Fields, vol 80 (1988), 139-150. | MR 90a:11087 | Zbl 0638.68058

[Gr] K. Grill, A Note on Randomness, Stat. and Probab. Letters, to appear. | Zbl 0809.60038

[GO] L. Guibas and A.M. Odlyzko, String Overlaps, Pattern Matching and Non-transitive Games, J. Comb. Th., Ser A, vol 30 (1981), 183-208. | Zbl 0454.68109

[Hl] E. Hlawka, Theorie der Gleichverteilung, Bibliographisches Institut, Mannheim, 1979. | MR 80j:10057 | Zbl 0406.10001

[KN] L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, J. Wiley, New York, 1974. | MR 54 #7415 | Zbl 0281.10001

[Od] A.M. Odlyzko, Enumeration of Strings, in Combinatorial Algorithms on Words, A. Apostolico and Z. Galil eds., Springer, Berlin, Heidelberg New York, 1984.

[Wa] P. Walters, An Introduction to Ergodic Theory, Springer Verlag, New York, 1982. | MR 84e:28017 | Zbl 0475.28009