PROBLEMS OF INFORMATION TRANSMISSION

A translation of *Problemy Peredachi Informatsii*

Volume 39, Number 1, January–March, 2003

Back to contents page

** 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. 2–20

**Abstract**—We 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. 21–31

**Abstract**—Andrei 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, 1965–1987. 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. 32–46

**Abstract**—The Lempel–Ziv 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. Lempel–Ziv 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 Navier–Stokes System
**

E. I. Dinaburg and Ya. G. Sinai

pp. 47–50

**Abstract**—For the quasilinear approximation of the 3D
Navier–Stokes system proposed earlier by the authors in [*Moscow Math.
J.*, 2001, vol. 1, no. 3, pp. 381–388], 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. 51–77

**Abstract**—A 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. 78–91

**Abstract**—Theorems 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. 92–103

**Abstract**—The 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. 104–118

**Abstract**—An 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. 119–147

**Abstract**—In 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. 369–376]) 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. 1–2, pp. 263–317]. 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. 148–157

**Abstract**—We 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 Zhang–Yeung inequality).