Block-distribution in random strings (Q685893)

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 \textit{P. Flajolet}, \textit{P. Kirschenhofer} and \textit{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\). \textit{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. \textit{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 \textit{L. J. Guibas}' and \textit{A. M. Odlyzko}'s theory of correlation polynomials of strings [J. Comb. Theory, Ser. A 30, 183-208 (1981; Zbl 0454.68109)].