|
Problemy Peredachi Informatsii, 2003, Volume 39, Issue 1, Pages 134–165
(Mi ppi210)
|
|
|
|
This article is cited in 3 scientific papers (total in 4 papers)
On the Role of the Law of Large Numbers in the
Theory of Randomness
An. A. Muchnik, A. L. Semenov
Abstract:
In the first part of this article, we answer Kolmogorov's question (stated in 1963 in [1]) about exact conditions for the existence of random generators. Kolmogorov theory of complexity permits of a precise definition of the notion of randomness for an individual sequence. For infinite sequences, the property of randomness is a binary property, a sequence can be random or not. For finite sequences, we can solely speak about a continuous property, a measure of randomness. Is it possible to measure randomness of a sequence $t$ by the extent to which the law of large numbers is satisfied in all subsequences of $t$ obtained in an “admissible way”? The case of infinite sequences was studied in [2]. As a measure of randomness (or, more exactly, of nonrandomness) of a finite sequence, we consider the specific deficiency of randomness $\delta$ (Definition 5). In the second part of this paper, we prove that the function $\delta/\ln(1/\delta)$ characterizes the connections between randomness of a finite sequence and the extent to which the law of large numbers is satisfied.
Citation:
An. A. Muchnik, A. L. Semenov, “On the Role of the Law of Large Numbers in the
Theory of Randomness”, Probl. Peredachi Inf., 39:1 (2003), 134–165; Problems Inform. Transmission, 39:1 (2003), 119–147
Linking options:
https://www.mathnet.ru/eng/ppi210 https://www.mathnet.ru/eng/ppi/v39/i1/p134
|
Statistics & downloads: |
Abstract page: | 748 | Full-text PDF : | 363 | References: | 64 |
|