PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

On the Maximum Values of $f$-Divergence and Rényi Divergence under a Given Variational Distance
V. V. Prelov
pp. 1–12

Abstract—We consider the problem of finding maximum values of $f$-divergences $D_f(P\,\|\,Q)$ of discrete probability distributions $P$ and $Q$ with values on a finite set under the condition that the variation distance $V(P,Q)$ between them and one of the distributions $P$ or $Q$ are given. We obtain exact expressions for such maxima of $f$-divergences, which in a number of cases allow to obtain both explicit formulas and upper bounds for them. As a consequence, we obtain explicit expressions for the maxima of $f$-divergences $D_f(P\,\|\,Q)$ given that, besides $V(P,Q)$, we only know the value of the maximum component of either $P$ or $Q$. Analogous results are also obtained for the Rényi divergence.

Entropy and Compression: A Simple Proof of an Inequality of Khinchin–Ornstein–Shields
R. Aragona, F. Marzi, F. Mignosi, and M. Spezialetti
pp. 13–22

Abstract—This paper concerns the folklore statement that “entropy is a lower bound for compression.” More precisely, we derive from the entropy theorem a simple proof of a pointwise inequality first stated by Ornstein and Shields and which is the almost-sure version of an average inequality first stated by Khinchin in 1953. We further give an elementary proof of the original Khinchin inequality, which can be used as an exercise for information theory students, and we conclude by giving historical and technical notes of such inequality.

Steiner Triple Systems of Order 21 with a Transversal Subdesign $\operatorname{TD}(3,6)$
Y. Guan, M. J. Shi, and D. S. Krotov
pp. 23–32

Abstract—A Steiner triple system (STS) contains a transversal subdesign $\operatorname{TD}(3,w)$ if its point set has three pairwise disjoint subsets $A$, $B$, $C$ of size $w$ and $w^2$ blocks of the STS intersect with each of $A$, $B$, $C$ (those $w^2$ blocks form a $\operatorname{TD}(3,w)$). We prove several structural properties of Steiner triple systems of order $3w+3$ that contain one or more transversal subdesigns $\operatorname{TD}(3,w)$. Using exhaustive search, we find that there are $2\,004\,720$ isomorphism classes of $\operatorname{STS}(21)$ containing a subdesign $\operatorname{TD}(3,6)$ (or, equivalently, a $6\times 6$ Latin square).

On $q$-ary Codes with Two Distances $d$ and $d+1$
P. Boyvalenkov, K. Delchev, D. V. Zinoviev, and V. A. Zinoviev
pp. 33–44

Abstract—We consider $q$-ary block codes with exactly two distances: $d$ and $d+1$. Several constructions of such codes are given. In the linear case, we show that all codes can be obtained by a simple modification of linear equidistant codes. Upper bounds for the maximum cardinality of such codes are derived. Tables of lower and upper bounds for small $q$ and $n$ are presented.

On Distance Distributions of Orthogonal Arrays
N. L. Manev
pp. 45–55

Abstract—Orthogonal arrays play an important role in statistics and experimental design. Like other combinatorial constructions, the most important and studied problems are questions about their existence and classification. An essential step to solving such problems is determination of Hamming distance distributions of an orthogonal array with given parameters. In this paper we propose an algorithm for computing possible distance distributions of an orthogonal array with arbitrary parameters with respect to any vector of the space. The possible distance distributions are all nonnegative integer solutions of special linear systems with integer coefficients. The proposed algorithm reduces the problem to checking signs of only $t+1$ coordinates of vectors of a subset of integer solutions of the system.

Extended Large Deviation Principle for Trajectories of Processes with Independent and Stationary Increments on the Half-line
F. C. Klebaner, A. V. Logachov, and A. A. Mogulskii
pp. 56–72

Abstract—We establish an extended large deviation principle for processes with independent and stationary increments on the half-line under the Cramèr moment condition in the space of functions of bounded variation without discontinuities of the second kind equipped with the Borovkov metric.

Bivariate Distributions of Maximum Remaining Service Times in Fork-Join Infinite-Server Queues
A. V. Gorbunova and A. V. Lebedev
pp. 73–90

Abstract—We study the maximum remaining service time in $M^{(2)}|G_2|\infty$ fork-join queueing systems where an incoming task forks on arrival for service into two subtasks, each of them being served in one of two infinite-sever subsystems. The following cases for the arrival rate are considered: (1) time-independent, (2) given by a function of time, (3) given by a stochastic process. As examples of service time distributions, we consider exponential, hyperexponential, Pareto, and uniform distributions. In a number of cases we find copula functions and the Blomqvist coefficient. We prove asymptotic independence of maximum remaining service times under high load conditions.

Piecewise Polynomial Sequences over the Galois Ring
A. R. Vasin
pp. 91–102

Abstract—We describe the construction of a piecewise polynomial generator over a Galois ring and prove a transitivity criterion for it. We give an estimate for the discrepancy of the output sequences of such a generator. We show that the obtained estimate is asymptotically equivalent to known estimates for special cases of a piecewise polynomial generator, and in some cases it is asymptotically sharper.