PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii
Andrei Nikolaevich Kolmogorov
p. 1
Kolmogorov $\varepsilon$-Entropy
in the Problems on Global Attractors for Evolution Equations of Mathematical Physics
M. I. Vishik and V. V. Chepyzhov
pp. 220
AbstractWe study the Kolmogorov $\varepsilon$-entropy and the fractal dimension of global attractors for autonomous and nonautonomous equations of mathematical physics. We prove upper estimates for the $\varepsilon$-entropy and fractal dimension of the global attractors of nonlinear dissipative wave equations.
Kolmogorov’s Contributions to the
Foundations of Probability
V. G. Vovk and G. R. Shafer
pp. 2131
AbstractAndrei Nikolaevich Kolmogorov was the foremost contributor to the mathematical and philosophical foundations of probability in the twentieth century, and his thinking on the topic is still potent today. In this article we first review the three stages of Kolmogorov’s work on the foundations of probability: (1) his formulation of measure-theoretic probability, 1933; (2) his frequentist theory of probability, 1963; and (3) his algorithmic theory of randomness, 19651987. We also discuss another approach to the foundations of probability, based on martingales, which Kolmogorov did not consider.
Problems of Robustness for Universal
Coding Schemes
V. V. V'yugin
pp. 3246
AbstractThe LempelZiv universal coding scheme is asymptotically optimal for the class of all stationary ergodic sources. A problem of robustness of this property under small violations of ergodicity is studied. The notion of deficiency of algorithmic randomness is used as a measure of disagreement between data sequence and probability measure. We prove that universal compression schemes from a large class are nonrobust in the following sense: If the randomness deficiency grows arbitrarily slowly on initial fragments of an infinite sequence, then the property of asymptotic optimality of any universal compression algorithm can be violated. LempelZiv compression algorithms are robust on infinite sequences generated by ergodic Markov chains when the randomness deficiency of their initial fragments of length $n$ grows as $o(n)$.
Existence and Uniqueness of Solutions of a
Quasilinear Approximation of the 3D NavierStokes System
E. I. Dinaburg and Ya. G. Sinai
pp. 4750
AbstractFor the quasilinear approximation of the 3D NavierStokes system proposed earlier by the authors in [Moscow Math. J., 2001, vol. 1, no. 3, pp. 381388], some conditions of solution regularity are considered and the theorem on existence and uniqueness of the Cauchy problem for some class of initial data is proved.
An Estimation Problem for Quasilinear
Stochastic Partial Differential Equations
I. A. Ibragimov
pp. 5177
AbstractA problem of estimating a functional parameter $\theta (x)$ and functionals $\Phi (\theta)$ based on observation of a solution $u_{\varepsilon} (t,x)$ of the stochastic partial differential equation $$ du_{\varepsilon} (t)=\sum\limits_{|k|\leq 2p} a_k D_x^k u_{\varepsilon}\,dt+\theta (x)g(u_{\varepsilon},t,x)+\varepsilon\,dw(t) $$ is considered. The asymptotic problem setting, as the noise intensity $\varepsilon\to 0$, is investigated.
Zeros and Local Extrema of Trigonometric Sums
A. A. Karatsuba
pp. 7891
AbstractTheorems on the number of zeros and number of local extrema of trigonometric sums, in particular, Gauss and Weyl sums, are proved.
The Tale of One-Way Functions
L. A. Levin
pp. 92103
AbstractThe existence of one-way functions (owf) is arguably the most important problem in computer theory. The article discusses and refines a number of concepts relevant to this problem. For instance, it gives the first combinatorial complete owf, i.e., a function which is one-way if any function is. There are surprisingly many subtleties in basic definitions. Some of these subtleties are discussed or hinted at in the literature and some are overlooked. Here, a unified approach is attempted.
Indefinite Knowledge about an Object and
Accuracy of Its Recovery Methods
G. G. Magaril-Il'yaev, K. Yu. Osipenko, and V. M. Tikhomirov
pp. 104118
AbstractAn approach to the problem of optimal recovery of functionals and operators on classes of functions under the conditions of infinite knowledge of functions themselves is discussed. The capabilities of this approach are demonstrated in a number of examples. In the end of the paper, a general result about optimal recovery of linear functionals is given.
On the Role of the Law of Large Numbers
in the Theory of Randomness
An. A. Muchnik and A. L. Semenov
pp. 119147
AbstractIn the first part of the article, we answer Kolmogorov’s question (stated in 1963 in [Sankhyā, Indian J. Statist., Ser. A, 1963, vol. 25, no. 4, pp. 369376]) about exact conditions for the existence of random generators. Kolmogorov theory of complexity allowed for a precise definition of the notion of randomness for an individual sequence of zeros and ones. 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 $\boldsymbol{t}$ by the extent to which the law of large numbers is satisfied in all subsequences of $\boldsymbol{t}$ obtained in an admissible way? The case of infinite sequences was studied in [Theor. Comp. Sci., 1998, vol. 207, no. 12, pp. 263317]. 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.
A Criterion for Extractability of Mutual
Information for a Triple of Strings
A. E. Romashchenko
pp. 148157
AbstractWe say that the mutual information of a triple of binary strings $a,b,c$ can be extracted if there exists a string $d$ such that $a$, $b$, and $c$ are independent given $d$, and $d$ is simple conditional to each of the strings $a$, $b$, and $c$. It is proved that the mutual information between $a$, $b$, and $c$ can be extracted if and only if the values of the conditional mutual informations $I(a:b\,|\,c)$, $I(a:c\,|\,b)$, and $I(b:c\,|\,a)$ are negligible. The proof employs a non-Shannon-type information inequality (a generalization of the recently discovered ZhangYeung inequality).