A complete classification of one-mode Gaussian channels is given up to canonical unitary equivalence. We also comment on the quantum capacity of these channels. A channel complementary to the quantum channel with additive classical Gaussian noise is described, providing an example of a one-mode Gaussian channel which is neither degradable nor antidegradable.

Convergence properties of Shannon entropy are studied. In the differential setting, it is known that weak convergence of probability measures (convergence in distribution) is not sufficient for convergence of the associated differential entropies. In that direction, an interesting example is introduced and discussed in light of new general results provided here for the desired differential entropy convergence, which take into account both compactly and uncompactly supported densities. Convergence of differential entropy is also characterized in terms of the Kullback-Liebler discriminant for densities with fairly general supports, and it is shown that convergence in variation of probability measures guarantees such convergence under an appropriate boundedness condition on the densities involved. Results for the discrete setting are also provided, allowing for infinitely supported probability measures, by taking advantage of the equivalence between weak convergence and convergence in variation in that setting.

The paper deals with the problem of constructing a code of the maximum possible cardinality consisting of binary vectors of length n and Hamming weight 3 and having the following property: any 3 × n matrix whose rows are cyclic shifts of three different code vectors contains a 3 × 3 permutation matrix as a submatrix. This property (in the special case w = 3) characterizes conflict-avoiding codes of length n for w active users, introduced in [1]. Using such codes in channels with asynchronous multiple access allows each of w active users to transmit a data packet successfully in one of w attempts during n time slots without collisions with other active users. An upper bound on the maximum cardinality of a conflict-avoiding code of length n with w = 3 is proved, and constructions of optimal codes achieving this bound are given. In particular, there are found conflict-avoiding codes for w = 3 which have much more vectors than codes of the same length obtained from cyclic Steiner triple systems by choosing a representative in each cyclic class.

In this paper, new completely regular q-ary codes are constructed from q-ary perfect codes. In particular, several new ternary completely regular codes are obtained from the ternary [11, 6, 5] Golay code. One of these codes with parameters [11, 5, 6] has covering radius ρ = 5 and intersection array (22, 20, 18, 2, 1; 1, 2, 9, 20, 22). This code is dual to the ternary perfect [11, 6, 5] Golay code. Another [10, 5, 5] code has covering radius ρ = 4 and intersection array (20, 18, 4, 1; 1, 2, 18, 20). This code is obtained by deleting one position of the former code. All together, the ternary Golay code results in eight completely regular codes, only four of which were previously known. Also, new infinite families of completely regular codes are constructed from q-ary Hamming codes.

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.

A model of random multi-access system with an ALOHA-type protocol is analyzed when the number N of users is large and the system is overloaded. In the limit as N → ∞, the behavior of the system is described by a nonrandom dynamical system. We give a condition for the dynamical system to have an attractive fixed point and outline cases of several fixed points. The presence of several fixed points indicates that the finite system may exhibit a metastability phenomenon.

We prove that for all n = 2k − 1, k ≥ 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.

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.

We continue studying the relationship between mutual information and variational distance started in Pinsker's paper [1], where an upper bound for the mutual information via variational distance was obtained. We present a simple lower bound, which in some cases is optimal or asymptotically optimal. A uniform upper bound for the mutual information via variational distance is also derived for random variables with a finite number of values. For such random variables, the asymptotic behaviour of the maximum of mutual information is also investigated in the cases where the variational distance tends either to zero or to its maximum value.

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.

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.

This paper is devoted to the mathematical study of some divergences based on mutual information which are well suited to categorical random vectors. These divergences are generalizations of the “entropy distance” and “information distance.” Their main characteristic is that they combine a complexity term and the mutual information. We then introduce the notion of (normalized) information-based divergence, propose several examples, and discuss their mathematical properties, in particular, in some prediction framework.

For any pair of integers r and m, 0 <= r <= m, we construct a class of quaternary linear codes whose binary images under the Gray map are codes with the parameters of the classical rth-order Reed-Muller code RM(r, m).

A Steiner triple system of order n (for short, STS(n)) is a system of three-element blocks (triples) of elements of an n-set such that each unordered pair of elements occurs in precisely one triple. Assign to each triple (i,j,k) ∊ STS(n) a topological triangle with vertices i, j, and k. Gluing together like sides of the triangles that correspond to a pair of disjoint STS(n) of a special form yields a black-and-white tiling of some closed surface. For each n ≡ 3 (mod 6) we prove that there exist nonisomorphic tilings of nonorientable surfaces by pairs of Steiner triple systems of order n. We also show that for half of the values n ≡ 1 (mod 6) there are nonisomorphic tilings of nonorientable closed surfaces.

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.

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.

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.

We consider the problem of efficient implementation of two-dimensional interpolation in the Guruswami-Sudan list decoding algorithm for Reed-Solomon codes. We show that it can be implemented by computing the product of ideals of interpolation polynomials constructed for subsets of interpolation points. A method for fast multiplication of coprime zero-dimensional ideals is proposed.

We prove results on exact asymptotics of the probabilities $$P\left\{ {\int\limits_0^1 {e^{\varepsilon \xi (t)} dt > b} } \right\},P\left\{ {\int\limits_0^1 {e^{\varepsilon |\xi (t)|} dt > b} } \right\},\varepsilon \to 0,$$ where b > 1, for two Gaussian processes ξ(t), namely, a Wiener process and a Brownian bridge. We use the Laplace method for Gaussian measures in Banach spaces. Evaluation of constants is reduced to solving an extreme value problem for the rate function and studying the spectrum of a second-order differential operator of the Sturm-Liouville type with the use of Legendre functions.

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.