Some distribution properties of 0,1-sequences (Q1080465)

Let \(A=(a_ 1,a_ 2,...,a_ k)\) be a finite set, and \(\mu\) a probability measure on A with \(\mu (a_ i)>0\) for \(i=1,2,...,k\). Then for any finite sequence \(w=(x_ 1,x_ 2,...,x_ N)\) in A, the discrepancy of w is given by \[ D(w)=\max_{1\leq i\leq k}| (1/N)\sum^{N}_{j=1}\delta_{a_ ix_ j}-\mu (a_ i)|, \] where \(\delta\) is the Kronecker symbol. In previous joint papers [see J. Number Theory 21, 156-175 (1985; Zbl 0569.10029)] the authors introduced generalizations of this discrepancy, which are useful in applications in the study of mathematical linguistics, and the randomness of sequences. Let u be a sequence of length s in A. Let [w;u] be the number of occurrences of u, as consecutive digits, in w, and let (w;u) be the number of occurrences of u in w not necessarily as consecutive digits. Then \[ D^{[s]}(w)=\max_{u\in A^ s}| \frac{[w;u]}{N-s+1}-\mu (u)|, \] \[ and\quad D^{(s)}(w)=\max_{u\in A^ s}| \frac{(w;u)}{\left( \begin{matrix} N\\ s\end{matrix} \right)}\quad =\mu (u)|, \] where \(\mu (u)=\prod^{s}_{j=1}\mu (u_ j)\) for \(u=(u_ 1,...,u_ s)\). If \(w=\{x_ i\}\) is a sequence in A, and \(w_ N=(x_ 1,...,x_ N)\), then w is [s]-uniformly distributed (sub-block u.d.) if \(\lim_{N\to \infty}D^{[s]}(w_ N)=0\), and, similarly, w is (s)- uniformly distributed (sub-word u.d.) if \(\lim_{N\to \infty}D^{(s)}(w_ N)=0\). The concept of [\(\infty]\)-u.d., i.e. [s]- u.d. for \(s=1,2,...\), arises in the study of normal numbers. In the present paper the authors restrict their attention to 0-1 sequences with \(\mu (0)=\mu (1)=1/2\). Sub-block and sub-word u.d. requiring certain minimal rates of convergence to 0 of the discrepancies involved are investigated. These ideas were suggested by definitions in \textit{D. E. Knuth} [The art of computer programming, Vol. 2: Seminumerical algorithms (1969; Zbl 0191.180); 2nd ed. (1981; Zbl 0477.65002)], in the study of the randomness of sequences. The authors prove several theorems, some of which can be extended to general finite alphabets \((a_ 1,...a_ k)\) with \(\mu (a_ i)=1/h\), \(i=1,2,...k\).