This article is cited in 4 papers

Information Theory and Coding Theory

On Nonstochastic Objects

V. V. V'yugin


Abstract: According to Kolmogorov, a finite object $x$ is called $(\alpha,\beta)$-stochastic, i.e., it satisfies stochastic dependences, if there exists a finite set $S$ such that $x\in A$, $K(A)\leq\alpha$ and $K(x)\geq\log_2|A|-\beta$, where $K$ is the ordinary Kolmogorov entropy (complexity), and $|A|$ is the number of elements of a set $A$. To define the concept of quasi-Kolmogorov stochasticity, the author examines the problem of the proportion of sequences that are not $(\alpha,\beta)$-stochastic. The principal results are as follows: Upper and lower bounds are obtained for the a priori countable measure of all sequences of length $n(\geq n)$ that are not $(\alpha,\beta)$-stochastic.

UDC: 621.391.1

Received: 18.07.1983

 English version: Problems of Information Transmission, 1985, 21:2, 77–83

Bibliographic databases:

• 
•