PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On Error-free Filtering of Finite-State Singular Processes under Dependent Distortions
V. V. Prelov and E. C. van der Meulen
pp. 271–279

Abstract—We consider the problem of finding some sufficient conditions under which causal error-free filtering for a singular stationary stochastic process $X=\{X_n\}$ with a finite number of states from noisy observations is possible. For a rather general model of observations where the observable stationary process is absolutely regular with respect to the estimated process $X$, it is proved (using an information-theoretic approach) that under a natural additional condition, the causal error-free (with probability one) filtering is possible.

On the Construction of $q$-ary Equidistant Codes
G. T. Bogdanova, V. A. Zinoviev, and T. J. Todorov
pp. 280–302

Abstract—The problem of constructing equidistant codes over an alphabet of an arbitrary size $q$ is considered. Some combinatorial constructions and computer-based search methods are presented. All maximal equidistant codes with distances $3$ and $4$ are found.

On the Regularity of Perfect $2$-Colorings of the Johnson Graph
I. Yu. Mogil'nykh
pp. 303–309

Abstract—We study perfect colorings of the Johnson graph in two colors. We give sufficient conditions for a perfect coloring of the Johnson graph to be $k$-regular and present examples of perfect colorings. The proof of the theorem is in many respects similar to the proof of the result by Etzion and Schwartz [1] on $k$-regularity of perfect codes.

On Partitions of an $n$-Cube into Nonequivalent Perfect Codes
S. V. Avgustinovich, F. I. Solov'eva, and O. Heden
pp. 310–315

Abstract—We prove that for all $n=2^k-1$, $k\ge 5$, there exists a partition of the set of all binary vectors of length $n$ into pairwise nonequivalent perfect binary codes of length $n$ with distance $3$.

On Quasi-successful Couplings of Markov Processes
M. L. Blank and S. A. Pirogov
pp. 316–330

Abstract—The notion of a successful coupling of Markov processes, based on the idea that both components of a coupled system “intersect” in finite time with probability 1, is extended to cover situations where the coupling is not necessarily Markovian and its components only converge (in a certain sense) to each other with time. Under these assumptions the unique ergodicity of the original Markov process is proved. The price for this generalization is the weak convergence to the unique invariant measure instead of the strong convergence. Applying these ideas to infinite interacting particle systems, we consider even more involved situations where the unique ergodicity can be proved only for a restriction of the original system to a certain class of initial distributions (e.g., translation-invariant). Questions about the existence of invariant measures with a given particle density are also discussed.

Accumulation on the Boundary for a One-Dimensional Stochastic Particle System
A. A. Zamyatin and V. A. Malyshev
pp. 331–343

Abstract—We consider an infinite particle system on the positive half-line, with particles moving independently of each other. When a particle hits the boundary, it immediately disappears and the boundary moves to the right by some fixed quantity (the particle size). We study the speed of the boundary movement (growth). Possible applications are dynamics of traffic jam growth, growth of a thrombus in a vessel, and epitaxy. Nontrivial mathematics concerns the correlation between particle dynamics and boundary growth.

Interrelation of Characteristics of Blocked RMA Stack Algorithms
G. S. Evseev and A. M. Turlikov
pp. 344–352

Abstract—A method to analyze the duration of collision resolution for blocked RMA stack algorithms is proposed. Simple formulas are obtained that express the average length of a collision resolution interval for the modified (frugal) algorithm in a noisy and in a noiseless channel, as well as for the basic algorithm in a noisy channel, through the corresponding parameters for the basic algorithm in a noiseless channel. From estimates of the throughput of the basic algorithm in a noiseless channel, estimates for the throughput in the other three cases are directly constructed.

On the Exact Asymptotics for the Stationary Sojourn Time Distribution in a Tandem of Queues with Light-Tailed Service Times
S. G. Foss
pp. 353–366

Abstract—We study the asymptotics of the stationary sojourn time $Z$ of a “typical customer” in a tandem of single-server queues. It is shown that in a certain “intermediate” region of light-tailed service time distributions, $Z$ may take a large value mostly due to a large value of a single service time of one of the customers. Arguments used in the paper also allow us to obtain an elementary proof of the logarithmic asymptotics for the tail distribution of the stationary sojourn time in the whole class of light-tailed distributions.

Application of Data Compression Methods to Nonparametric Estimation of Characteristics of Discrete-Time Stochastic Processes
B. Ya. Ryabko
pp. 367–379

Abstract—Discrete-time stochastic processes generating elements of either a finite set (alphabet) or a real line interval are considered. Problems of estimating limiting (or stationary) probabilities and densities are considered, as well as classification and prediction problems. We show that universal coding (or data compression) methods can be used to solve these problems.

Some Mathematical Questions of Theory of Information Transmission
M. S. Pinsker
pp. 380–392

Abstract—A survey talk given by M.S. Pinsker at the Summer Seminar on Information Theory and Statistical Methods of Automatic Control, Prague, May 25 – June 4, 1965, was published in Kybernetika journal of the Czech Academy of Sciences (1966, vol. 2, no. 2, pp. 117–146). By the courtesy of the editors of Kybernetika, we are allowed to publish an abridged version of the talk, which concisely and clearly exposes final mathematical results that underlie Shannon’s information theory. The content of the talk is deeply intertwined with the author’s works. The talk is almost unknown to Russian readers, and with this publication we fill this gap, thereby paying tribute to our outstanding scientist and friend.

INDEX
pp. 393–396