Some distribution properties of 0,1-sequences (Q1080465): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a paper of Niven and Zuckerman / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4192121 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3929073 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Folgen auf kompakten Räumen. II / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3926068 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3948613 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On uniform distribution of double sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Zur Diskrepanz von 0,1-Folgen. (Discrepancy of 0,1-sequences) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5184980 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3935355 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4767350 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5650753 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5661587 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the definition of normal numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ein zentraler grenzwertsatz mit anwendungen auf die zahlentheorie / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a distribution problem in finite and countable sets / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 14:29, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some distribution properties of 0,1-sequences |
scientific article |
Statements
Some distribution properties of 0,1-sequences (English)
0 references
1985
0 references
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\).
0 references
distribution of 0,1-sequences
0 references
subblock uniform distribution
0 references
subword uniform distribution
0 references
discrepancy
0 references
finite alphabets
0 references