zbMATH — the first resource for mathematics

Block-distribution in random strings. (English) Zbl 0778.60023
A notion of \(k\)-discrepancy for infinite sequences of independent random variables taking the values 0 and 1 with probabilities \(p\) and \(q\) is introduced: \[ D^ k_ N(x_ 1,\ldots,x_ N)=\max_{A\in\{0,1\}^ k}{1\over\sqrt{p^ k\mu_ k(A)}} \left|{\#\{1\leq n\leq N-k\mid x_ nx_{n+1}\cdots x_{n+k}=A\}\over N}-\mu_ k(A)\right|, \] where \(p\leq q\), \(A=a_ 1a_ 2\cdots a_ k\) and \(\mu_ k\) is the \(k\)-fold product measure generated by \(\mu(\{0\})=p\) and \(\mu(\{1\})=q\). For an increasing sequence of integers \(k(N)\) a sequence of 0’s and 1’s \(x_ 1,x_ 2,\ldots\) is called \(k(N)\)-uniformly distributed if \[ \lim_{N\to\infty}D^{k(N)}_ N(x_ 1,\ldots,x_ N)=0. \] It is proved that almost all sequences in \(\{0,1\}^{\mathbf N}\) are \(k(N)\)- uniformly distributed, if and only if \(\log_{1/p}n-\log_{1/p}\log n- k(n)\to\infty\). Otherwise the set of \(k(N)\)-uniformly distributed sequences has measure 0 which is an immediate consequence of Kolmogoroff’s 0-1-law. This generalizes a result due to P. Flajolet, P. Kirschenhofer and R. F. Tichy [Probab. Theory Relat. Fields 80, No. 1, 139-150 (1988; Zbl 0638.68058)], who considered the case \(p=q=1/2\) and proved that in this case almost all sequences are \(k(N)\)-uniformly distributed, if \(\log_ 2n-\log_ 2\log_ 2n- k(n)\to\infty\). K. Grill [A note on randomness, Stat. Probab. Lett. (to appear)] proved that almost no sequences are \(k(N)\)-uniformly distributed in the opposite case. M. Goldstern [J. Number Theory (to appear)] gave a general argument that almost all sequences are \(k(N)\)-uniformly distributed for all \(k(N)\) satisfying the above condition. The proof of the theorem uses a generalization of L. J. Guibas’ and A. M. Odlyzko’s theory of correlation polynomials of strings [J. Comb. Theory, Ser. A 30, 183-208 (1981; Zbl 0454.68109)].
Reviewer: P.J.Grabner (Graz)

60F15 Strong limit theorems
60G50 Sums of independent random variables; random walks
60F10 Large deviations
68R05 Combinatorics in computer science
Full Text: DOI Numdam EuDML
[1] W. FELLER, An introduction to probability theory and its applications, J. Wiley, New York, 1965. · Zbl 0158.34902
[2] P. FLAJOLET, P. KIRSCHENHOFER and R.F. TICHY, Deviations from uniformity in random strings, Probab. Th. Rel. Fields, vol 80 (1988), 139-150. · Zbl 0638.68058
[3] K. GRILL, A note on randomness, Stat. and Probab. Letters, to appear. · Zbl 0809.60038
[4] 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
[5] E. HLAWKA, Theorie der gleichverteilung, Bibliographisches Institut, Mannheim, 1979. · Zbl 0406.10001
[6] L. KUIPERS and H. NIEDERREITER, Uniform distribution of sequences, J. Wiley, New York, 1974. · Zbl 0281.10001
[7] A.M. ODLYZKO, Enumeration of strings, in Combinatorial Algorithms on Words, A. Apostolico and Z. Galil eds., Springer, Berlin, Heidelberg New York, 1984. · Zbl 0603.68074
[8] P. WALTERS, An introduction to ergodic theory, Springer Verlag, New York, 1982. · Zbl 0475.28009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.