Block distribution in random strings

Grabner, Peter J. 

Annales de l'Institut Fourier, Tome 43 (1993) no. 2, pp. 539-549

Abstract (VO)

For almost all infinite binary sequences of Bernoulli trials $(p,q)$ 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 ${\log }_{\frac{1}{p}}N-{\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}$.

Résumé

Pour presque toute suite binaire infinie issue d’un tirage de Bernoulli $(p,q)$ 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 ${\log }_{\frac{1}{p}}N-{\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}$.

Détail

DOI : 10.5802/aif.1345