# ANNALES DE L'INSTITUT FOURIER

Block distribution in random strings
Annales de l'Institut Fourier, Volume 43 (1993) no. 2, pp. 539-549.

For almost all infinite binary sequences of Bernoulli trials $\left(p,q\right)$ the frequency of blocks of length $k\left(N\right)$ in the first $N$ terms tends asymptotically to the probability of the blocks, if $k\left(N\right)$ increases like ${\mathrm{log}}_{\frac{1}{p}}N-{\mathrm{log}}_{\frac{1}{p}}N-\psi \left(N\right)$ (for $p\le q$) where $\psi \left(N\right)$ 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}$.

Pour presque toute suite binaire infinie issue d’un tirage de Bernoulli $\left(p,q\right)$ la fréquence des blocs de longueur $k\left(N\right)$ dans les $N$ premiers termes tend asymptotiquement vers la probabilité naturelle du bloc, ceci lorsque $k\left(N\right)$ croît comme ${\mathrm{log}}_{\frac{1}{p}}N-{\mathrm{log}}_{\frac{1}{p}}N-\psi \left(N\right)$ (avec $p\le q$) où $\psi \left(N\right)$ 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}$.

@article{AIF_1993__43_2_539_0,
author = {Grabner, Peter J.},
title = {Block distribution in random strings},
journal = {Annales de l'Institut Fourier},
pages = {539--549},
publisher = {Imprimerie Louis-Jean},
volume = {43},
number = {2},
year = {1993},
doi = {10.5802/aif.1345},
zbl = {0778.60023},
mrnumber = {94d:60044},
language = {en},
url = {https://aif.centre-mersenne.org/articles/10.5802/aif.1345/}
}
TY  - JOUR
TI  - Block distribution in random strings
JO  - Annales de l'Institut Fourier
PY  - 1993
DA  - 1993///
SP  - 539
EP  - 549
VL  - 43
IS  - 2
PB  - Imprimerie Louis-Jean
PP  - Gap
UR  - https://aif.centre-mersenne.org/articles/10.5802/aif.1345/
UR  - https://zbmath.org/?q=an%3A0778.60023
UR  - https://www.ams.org/mathscinet-getitem?mr=94d:60044
UR  - https://doi.org/10.5802/aif.1345
DO  - 10.5802/aif.1345
LA  - en
ID  - AIF_1993__43_2_539_0
ER  - 
%0 Journal Article
%T Block distribution in random strings
%J Annales de l'Institut Fourier
%D 1993
%P 539-549
%V 43
%N 2
%I Imprimerie Louis-Jean
%C Gap
%U https://doi.org/10.5802/aif.1345
%R 10.5802/aif.1345
%G en
%F AIF_1993__43_2_539_0
Grabner, Peter J. Block distribution in random strings. Annales de l'Institut Fourier, Volume 43 (1993) no. 2, pp. 539-549. doi : 10.5802/aif.1345. https://aif.centre-mersenne.org/articles/10.5802/aif.1345/

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

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

[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

[Hl] E. Hlawka, Theorie der Gleichverteilung, Bibliographisches Institut, Mannheim, 1979. | MR | Zbl

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

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

Cited by Sources: