开放存取 开放存取  受限制的访问 ##reader.subscriptionAccessGranted##  受限制的访问 订阅存取

卷 53, 编号 4 (2017)

Coding Theory

Independence Numbers of Random Subgraphs of Some Distance Graph

Derevyanko N., Kiselev S.

摘要

The distance graph G(n, 2, 1) is a graph where vertices are identified with twoelement subsets of {1, 2,..., n}, and two vertices are connected by an edge whenever the corresponding subsets have exactly one common element. A random subgraph Gp(n, 2, 1) in the Erd˝os–Rényi model is obtained by selecting each edge of G(n, 2, 1) with probability p independently of other edges. We find a lower bound on the independence number of the random subgraph G1/2(n, 2, 1).

Problems of Information Transmission. 2017;53(4):307-318
pages 307-318 views

On the Number of Edges of a Uniform Hypergraph with a Range of Allowed Intersections

Bobu A., Kupriyanov A., Raigorodskii A.

摘要

We study the quantity p(n, k, t1, t2) equal to the maximum number of edges in a k-uniform hypergraph having the property that all cardinalities of pairwise intersections of edges lie in the interval [t1, t2]. We present previously known upper and lower bounds on this quantity and analyze their interrelations. We obtain new bounds on p(n, k, t1, t2) and consider their possible applications in combinatorial geometry problems. For some values of the parameters we explicitly evaluate the quantity in question. We also give a new bound on the size of a constant-weight error-correcting code.

Problems of Information Transmission. 2017;53(4):319-342
pages 319-342 views

On Spectra of Linear Codes

Leont’ev V.

摘要

We present new MacWilliams-type identities for spectra of linear codes.

Problems of Information Transmission. 2017;53(4):343-348
pages 343-348 views

Methods of Signal Processing

On Detection of Gaussian Stochastic Sequences

Burnashev M.

摘要

We consider the minimax detection problem for a Gaussian random signal vector in white Gaussian additive noise. It is assumed that an unknown vector σ of signal vector intensities belongs to a given set ε. We investigate when it is possible to replace the set ε with a smaller set ε0 without loss of quality (and, in particular, replace it with a single point σ0).

Problems of Information Transmission. 2017;53(4):349-367
pages 349-367 views

On One Problem in Multichannel Signal Detection

Burnaev E., Golubev G.

摘要

We consider a statistical problem of detecting a signal with unknown energy in a multichannel system, observed in a Gaussian noise. We assume that the signal can appear in the kth channel with a known small prior probability πk. Using noisy observations from all channels, we would like to detect whether the signal is presented in one of the channels or we observe pure noise. We describe and compare statistical properties of the maximum posterior probability test and optimal Bayes test. In particular, for these tests we obtain limiting distributions of test statistics and define sets of their undetectable signals.

Problems of Information Transmission. 2017;53(4):368-380
pages 368-380 views

Large Systems

Stochastic Operation Induced by Group Allocation of Particles and Generalized Branching Processes

Lebedev A.

摘要

We introduce a stochastic operation induced by group allocation of particles in cells, which belongs to the class of Archimedean operations. We analyze its properties and prove limit theorems. We also introduce and study branching processes with this operation, which can describe various phenomena in biological populations and computer networks, including virus propagation. In the limit, a nonlinear dynamical system occurs.

Problems of Information Transmission. 2017;53(4):381-390
pages 381-390 views

Quantifier Alternation in First-Order Formulas with Infinite Spectra

Zhukovskii M.

摘要

The spectrum of a first-order formula is the set of numbers α such that for a random graph in a binomial model where the edge probability is a power function of the number of graph vertices with exponent −α the truth probability of this formula does not tend to either zero or one. In 1990 J. Spenser proved that there exists a first-order formula with an infinite spectrum. We have proved that the minimum quantifier depth of a first-order formula with an infinite spectrum is either 4 or 5. In the present paper we find a wide class of first-order formulas of depth 4 with finite spectra and also prove that the minimum quantifier alternation number for a first-order formula with an infinite spectrum is 3.

Problems of Information Transmission. 2017;53(4):391-403
pages 391-403 views