Block distribution in random strings

Peter J. Grabner

Annales de l'institut Fourier (1993)

  • Volume: 43, Issue: 2, page 539-549
  • ISSN: 0373-0956

Abstract

top
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 1 p N - log 1 p N - ψ ( N ) (for p ≤ q ) where ψ ( N ) tends to + ∞ . This generalizes a result due to P. Flajolet, P. Kirschenhofer and R.F. Tichy concerning the case p = q = 1 2 .

How to cite

top

Grabner, Peter J.. "Block distribution in random strings." Annales de l'institut Fourier 43.2 (1993): 539-549. <http://eudml.org/doc/75009>.

@article{Grabner1993,
abstract = {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 $\{\rm log\}_\{\{1\over p\}\} N - \{\rm log\}_\{\{1\over p\}\} N-\psi (N)$ (for $p\le q$) where $\psi (N)$ tends to $+\infty $. This generalizes a result due to P. Flajolet, P. Kirschenhofer and R.F. Tichy concerning the case $p=q=\{1\over 2\}$.},
author = {Grabner, Peter J.},
journal = {Annales de l'institut Fourier},
keywords = {coin tossing; uniform distribution; Kolmogoroff's 0-1-law; theory of correlation polynomials of strings},
language = {eng},
number = {2},
pages = {539-549},
publisher = {Association des Annales de l'Institut Fourier},
title = {Block distribution in random strings},
url = {http://eudml.org/doc/75009},
volume = {43},
year = {1993},
}

TY - JOUR
AU - Grabner, Peter J.
TI - Block distribution in random strings
JO - Annales de l'institut Fourier
PY - 1993
PB - Association des Annales de l'Institut Fourier
VL - 43
IS - 2
SP - 539
EP - 549
AB - 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 ${\rm log}_{{1\over p}} N - {\rm log}_{{1\over p}} N-\psi (N)$ (for $p\le q$) where $\psi (N)$ tends to $+\infty $. This generalizes a result due to P. Flajolet, P. Kirschenhofer and R.F. Tichy concerning the case $p=q={1\over 2}$.
LA - eng
KW - coin tossing; uniform distribution; Kolmogoroff's 0-1-law; theory of correlation polynomials of strings
UR - http://eudml.org/doc/75009
ER -

References

top
  1. [Fe] W. FELLER, An Introduction to Probability Theory and Its Applications, J. Wiley, New York, 1965. 
  2. [FKT] P. FLAJOLET, P. KIRSCHENHOFER and R.F. TICHY, Deviations from Uniformity in Random Strings, Probab. Th. Rel. Fields, vol 80 (1988), 139-150. Zbl0638.68058MR90a:11087
  3. [Gr] K. GRILL, A Note on Randomness, Stat. and Probab. Letters, to appear. Zbl0809.60038
  4. [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. Zbl0454.68109
  5. [Hl] E. HLAWKA, Theorie der Gleichverteilung, Bibliographisches Institut, Mannheim, 1979. Zbl0406.10001MR80j:10057
  6. [KN] L. KUIPERS and H. NIEDERREITER, Uniform Distribution of Sequences, J. Wiley, New York, 1974. Zbl0281.10001MR54 #7415
  7. [Od] A.M. ODLYZKO, Enumeration of Strings, in Combinatorial Algorithms on Words, A. Apostolico and Z. Galil eds., Springer, Berlin, Heidelberg New York, 1984. 
  8. [Wa] P. WALTERS, An Introduction to Ergodic Theory, Springer Verlag, New York, 1982. Zbl0475.28009MR84e:28017

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.