Block-distribution in random strings
type: Item
instance of: scholarly article
title: Block-distribution in random strings
zbMATH Open document ID: 0778.60023
author: Peter J. Grabner
publication date: 1994-01-05T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/75009
review text: 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)].
Mathematics Subject Classification ID: 60F15
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 60F10
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 425544
zbMATH Keywords: coin tossing
zbMATH Keywords: uniform distribution
zbMATH Keywords: Kolmogoroff's 0-1-law
zbMATH Keywords: theory of correlation polynomials of strings
MaRDI profile type: Publication
OpenAlex ID: W2323580803
cites work: Q5541610
cites work: Deviations from uniformity in random strings
cites work: A note on randomness
cites work: String overlaps, pattern matching, and nontransitive games
cites work: Q4192121
cites work: Q4767350
cites work: Q3740259
cites work: Q3931654
DOI: 10.5802/AIF.1345
published in: Annales de l’institut Fourier
description: scientific article; zbMATH DE number 425544