An instability property of the Birkhoff's ergodic theorem and related asymptotic laws with respect to small violations of algorithmic randomness is studied. The Shannon-McMillan-Breiman theorem and all universal compression schemes are also among them.

This paper is a survey of concepts and results related to simple Kolmogorov complexity, prefix complexity and resource-bounded complexity. We also consider a new type of complexity—statistical complexity closely related to mathematical statistics. Unlike other discoverers of algorithmic complexity, A. N. Kolmogorov's leading motive was developing on its basis a mathematical theory more adequately substantiating applications of probability theory, mathematical statistics and information theory. Kolmogorov wanted to deduce properties of a random object from its complexity characteristics without use of the notion of probability. In the first part of this paper we present several results in this direction. Though the subsequent development of algorithmic complexity and randomness was different, algorithmic complexity has successful applications in a traditional probabilistic framework. In the second part of the paper we consider applications to the estimation of parameters and the definition of Bernoulli sequences. All considerations have finite combinatorial character.