
This article is cited in 2 scientific papers (total in 3 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.
Full text:
PDF file (3304 kB)
References:
PDF file
HTML file
English version:
Problems of Information Transmission, 2003, 39:1, 119–147
Bibliographic databases:
UDC:
621.391.1:519.2
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
Citation in format AMSBIB
\Bibitem{MucSem03}
\by An.~A.~Muchnik, A.~L.~Semenov
\paper On the Role of the Law of Large Numbers in the
Theory of Randomness
\jour Probl. Peredachi Inf.
\yr 2003
\vol 39
\issue 1
\pages 134165
\mathnet{http://mi.mathnet.ru/ppi210}
\mathscinet{http://www.ams.org/mathscinetgetitem?mr=2101670}
\zmath{https://zbmath.org/?q=an:1078.60005}
\transl
\jour Problems Inform. Transmission
\yr 2003
\vol 39
\issue 1
\pages 119147
\crossref{https://doi.org/10.1023/A:1023638717091}
Linking options:
http://mi.mathnet.ru/eng/ppi210 http://mi.mathnet.ru/eng/ppi/v39/i1/p134
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
This publication is cited in the following articles:

K. Yu. Gorbunov, “Estimation of the Number of Elements in a Covering of an Arbitrary
Randomness Test by Frequency Tests”, Problems Inform. Transmission, 43:1 (2007), 48–56

S. I. Adian, A. L. Semenov, V. A. Uspenskii, “Andrei Al'bertovich Muchnik (obituary)”, Russian Math. Surveys, 62:4 (2007), 775–779

Uspensky V.A., V'yugin V.V., “Development of the algorithmic information theory in Russia”, Journal of Communications Technology and Electronics, 56:6 (2011), 739–747

Number of views: 
This page:  491  Full text:  144  References:  39 
