PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Sufficient Conditions for Monotonicity of the Undetected Error Probability for Large Channel Error Probabilities
R. Dodunekova and E. Nikolova
pp. 187–198

Abstract—The performance of a linear error-detecting code in a symmetric memoryless channel is characterized by its probability of undetected error, which is a function of the channel symbol error probability, involving basic parameters of a code and its weight distribution. However, the code weight distribution is known for relatively few codes since its computation is an NP-hard problem. It should therefore be useful to have criteria for properness and goodness in error detection that do not involve the code weight distribution. In this work we give two such criteria. We show that a binary linear code $C$ of length $n$ and its dual code $C^\perp$ of minimum code distance $d^\perp$ are proper for error detection whenever $d^\perp\ge \lfloor n/2 \rfloor+1$, and that $C$ is proper in the interval $[(n+1-2d^\perp)/(n-d^\perp), 1/2]$ whenever $\lceil n/3\rceil+1\le d^\perp\le \lfloor n/2\rfloor$. We also provide examples, mostly of Griesmer codes and their duals, that satisfy the above conditions.

A Note on the Uniqueness of $(w,r)$ Cover-Free Codes
V. S. Lebedev
pp. 199–203

Abstract—A binary code is called a $(w,r)$ cover-free code if it is the incidence matrix of a family of sets where the intersection of any $w$ sets is not covered by the union of any other $r$ sets. For certain $(w,r)$ cover-free codes with a simple structure, we obtain a new condition of optimality and uniqueness up to row and/or column permutations.

On the Construction of Transitive Codes
F. I. Solov'eva
pp. 204–211

Abstract—Application of some known methods of code construction (such as the Vasil'ev, Plotkin, and Mollard methods) to transitive codes satisfying certain auxiliary conditions yields infinite classes of large-length transitive codes, in particular, at least $\lfloor k/2\rfloor^2$ nonequivalent perfect transitive codes of length $n=2^k-1$, $k>4$. A similar result is valid for extended perfect transitive codes.

Tracking Volatility
L. Goldentayer, F. Klebaner, and R. Sh. Liptser
pp. 212–229

Abstract—We propose an adaptive algorithm for tracking historical volatility. The algorithm borrows ideas from nonparametric statistics. In particular, we assume that the volatility is a several times differentiable function with a bounded highest derivative. We propose an adaptive algorithm with a Kalman filter structure, which guarantees the same asymptotics (well known from statistical inference) with respect to the sample size $n$, $n\to\infty$. The tuning procedure for this filter is simpler than for a GARCH filter.

Poisson Hypothesis: Combinatorial Aspect
A. N. Rybko and S. B. Shlosman
pp. 230–236

Abstract—We describe our results concerning the proof of the Poisson hypothesis. We explain the probabilistic aspect of our results and present the main combinatorial step of our proof. That combinatorial statement deals with counting the number of rod placements on a line.

Nonreducible Descriptions for the Conditional Kolmogorov Complexity
M. A. Ustinov
pp. 237–242

Abstract—Assume that a program $p$ produces an output string $b$ for an input string $a$: $p(a)=b$. We look for a “reduction” (simplification) of $p$, i.e., a program $q$ such that $q(a)=b$ but $q$ has Kolmogorov complexity smaller than $p$ and contains no additional information as compared to $p$ (this means that the conditional complexity $\operatorname{K}(q\,|\, p)$ is negligible). We show that, for any two strings $a$ and $b$ (except for some degenerate cases), one can find a nonreducible program $p$ of any arbitrarily large complexity (any value larger than $\operatorname{K}(a)+\operatorname{K}(b\,|\, a)$ is possible).

Generalized Erlang Problem for Service Systems with Finite Total Capacity
O. M. Tikhonenko
pp. 243–253

Abstract—A multiserver on-demand system is considered in which each call has three interdependent random characteristics: the required number of servers, capacity, and service time. The total capacity of calls and the total number of servers in the system are limited. The type of a call is defined by the number of servers required for its service. We find a stationary distribution of the number of calls in the system, as well as the loss probability for a call of each type.

On the Stability of a Queueing System with Uncountably Branching Fluid Limits
A. P. Kovalevskii, V. A. Topchii, and S. G. Foss
pp. 254–279

Abstract—It is known that in many queueing systems fluid limits are deterministic functions. Models and conditions which lead to random fluid limits have not received much attention. This paper is devoted to a study of a queueing network whose fluid limits admit a random and uncountable branching at certain points. Stability conditions for this model are investigated by the use of recent results from the theory of branching processes.

Busy Periods in a System with Heterogeneous Servers or Channels
B. S. Tsybakov
pp. 280–295

Abstract—We consider a multiple communication channel system having channels with different transmission rates. We give a solution for the problem (of interest for such a system) of finding the probability densities and probability distribution functions of the $N$-busy period length. A solution in the case of identical channels (servers) was given in [Guillemin, F. and Pinchon, D., J. Appl. Probab., 1998, vol. 35, pp. 165–183].

Maxima of Waiting Times for the Random Order Service $M|M|1$ Queue
A. V. Lebedev
pp. 296–299

Abstract—A random order service $M|M|1$ queueing system is considered. A stochastic estimate for the asymptotic distribution of normalized maxima of waiting times and an estimate for the upper limit almost sure are obtained.