Search

KSG mutual information estimator, which is based on the distances of each sample to its $k$ -th nearest neighbor, is widely used to estimate mutual information between two continuous random variables. Existing work has analyzed the convergence rate of this estimator for random variables whose densities are bounded away from zero in its support. In practice, however, KSG estimator also performs well for a much broader class of distributions, including not only those with bounded support and densities bounded away from zero, but also those with bounded support but densities approaching zero, and those with unbounded support. In this paper, we analyze the convergence rate of the error of KSG estimator for smooth distributions, whose support of density can be both bounded and unbounded. As KSG mutual information estimator can be viewed as an adaptive recombination of KL entropy estimators, in our analysis, we also provide convergence analysis of KL entropy estimator for a broad class of distributions. [ABSTRACT FROM AUTHOR]

The problem of finding a vector $\boldsymbol {x}$ which obeys a set of quadratic equations $| \boldsymbol {a}_{\text {k}}^\top \boldsymbol {x} |^{2}=\text {y}_{\text {k}}$ , $\text {k}=1,\cdots,\text {m}$ , plays an important role in many applications. In this paper we consider the case when both $\boldsymbol {x}$ and $\boldsymbol {a}_{k}$ are real-valued vectors of length n. A new loss function is constructed for this problem, which combines the smooth quadratic loss function with an activation function. Under the Gaussian measurement model, we establish that with high probability the target solution $\boldsymbol {x}$ is the only minimizer (up to a global sign) of the new loss function provided $\text {m}\gtrsim \text {n}$. Moreover, the loss function always has a negative directional curvature around its saddle points. [ABSTRACT FROM AUTHOR]

This paper provides conditions on the observation probability distribution in Bayesian localization and optimal filtering so that the conditional mean estimate satisfies convex stochastic dominance. Convex dominance allows us to compare the unconditional mean square error between two optimal Bayesian state estimators over arbitrary time horizons instead of using brute force Monte-Carlo computations. The proof uses two key ideas from microeconomics, namely, integral precision dominance and aggregation of single crossing. The convex dominance result is then used to give sufficient conditions so that the optimal policy of a controlled sensing two-state partially observed Markov decision process (POMDP) is lower bounded by a myopic policy. Numerical examples are presented where the Shannon capacity of the observation distribution using one sensor dominates that of another, and convex dominance holds but Blackwell dominance does not hold. These illustrate the usefulness of the main result in localization, filtering and controlled sensing applications. [ABSTRACT FROM AUTHOR]

Genomic evolution can be viewed as string-editing processes driven by mutations. An understanding of the statistical properties resulting from these mutation processes is of value in a variety of tasks related to biological sequence data, e.g., estimation of model parameters and compression. At the same time, due to the complexity of these processes, designing tractable stochastic models and analyzing them are challenging. In this paper, we study two kinds of systems, each representing a set of mutations. In the first system, tandem duplications and substitution mutations are allowed and in the other, interspersed duplications. We provide stochastic models and, via stochastic approximation, study the evolution of substring frequencies for these two systems separately. Specifically, we show that $k$ -mer frequencies converge almost surely and determine the limit set. Furthermore, we present a method for finding upper bounds on entropy for such systems. [ABSTRACT FROM AUTHOR]

In this paper, we study tail inequalities of the largest eigenvalue of a matrix infinitely divisible (i.d.) series, which is a finite sum of fixed matrices weighted by i.d. random variables. We obtain several types of tail inequalities, including Bennett-type and Bernstein-type inequalities. This allows us to further bound the expectation of the spectral norm of a matrix i.d. series. Moreover, by developing a new lower-bound function for $Q(s)=(s+1)\log (s+1)-s$ that appears in the Bennett-type inequality, we derive a tighter tail inequality of the largest eigenvalue of the matrix i.d. series than the Bernstein-type inequality when the matrix dimension is high. The resulting lower-bound function is of independent interest and can improve any Bennett-type concentration inequality that involves the function $Q(s)$. The class of i.d. probability distributions is large and includes Gaussian and Poisson distributions, among many others. Therefore, our results encompass the existing work on matrix Gaussian series as a special case. Lastly, we show that the tail inequalities of a matrix i.d. series have applications in several optimization problems including the chance constrained optimization problem and the quadratic optimization problem with orthogonality constraints. In addition, we also use the resulting tail bounds to show that random matrices constructed from i.d. random variables satisfy the restricted isometry property (RIP) when it acts as a measurement matrix in compressed sensing. [ABSTRACT FROM AUTHOR]

It is well known that superposition coding, namely separately encoding the independent sources, is optimal for symmetric multilevel diversity coding (SMDC) (Yeung-Zhang 1999) for any $L\geq 2$ , where $L$ is the number of levels of the coding system. However, the characterization of the coding rate region therein involves uncountably many linear inequalities and the constant term (i.e., the lower bound) in each inequality is given in terms of the solution of a linear optimization problem. Thus this implicit characterization of the coding rate region does not enable the determination of the achievability of a given rate tuple. In principle, the achievability of a given rate tuple can be determined by direct computation, but the complexity is prohibitive even for $L=5$. In this paper, for any fixed $L$ , we obtain in closed form a finite set of linear inequalities for characterizing the coding rate region. We further show by the symmetry of the problem that only a much smaller subset of this finite set of inequalities needs to be verified in determining the achievability of a given rate tuple. Yet, the cardinality of this smaller set grows at least exponentially fast with $L$. We also present a subset entropy inequality, which together with our explicit characterization of the coding rate region, is sufficient for proving the optimality of superposition coding. [ABSTRACT FROM AUTHOR]

The entropy accumulation theorem states that the smooth min-entropy of an $n$ -partite system $A = (A_{1}, \ldots, A_{n})$ is lower-bounded by the sum of the von Neumann entropies of suitably chosen conditional states up to corrections that are sublinear in $n$. This theorem is particularly suited to proving the security of quantum cryptographic protocols, and in particular so-called device-independent protocols for randomness expansion and key distribution, where the devices can be built and preprogrammed by a malicious supplier. However, while the bounds provided by this theorem are optimal in the first order, the second-order term is bounded more crudely, in such a way that the bounds deteriorate significantly when the theorem is applied directly to protocols where parameter estimation is done by sampling a small fraction of the positions, as is done in most QKD protocols. The objective of this paper is to improve this second-order sublinear term and remedy this problem. On the way, we prove various bounds on the divergence variance, which might be of independent interest. [ABSTRACT FROM AUTHOR]

In 1959, Rényi proposed the information dimension and the $d$ -dimensional entropy to measure the information content of general random variables. This paper proposes a generalization of information dimension to stochastic processes by defining the information dimension rate as the entropy rate of the uniformly quantized stochastic process divided by minus the logarithm of the quantizer step size $1/m$ in the limit as $m\to \infty $. It is demonstrated that the information dimension rate coincides with the rate-distortion dimension, defined as twice the rate-distortion function $R(D)$ of the stochastic process divided by $-\log (D)$ in the limit as $D\downarrow 0$. It is further shown that among all multivariate stationary processes with a given (matrix-valued) spectral distribution function (SDF), the Gaussian process has the largest information dimension rate and the information dimension rate of multivariate stationary Gaussian processes is given by the average rank of the derivative of the SDF. The presented results reveal that the fundamental limits of almost zero-distortion recovery via compressible signal pursuit and almost lossless analog compression are different in general. [ABSTRACT FROM AUTHOR]

In this paper, a free deterministic equivalent is proposed for the capacity analysis of the multi-input multi-output (MIMO) multiple access channel (MAC) with a more general channel model compared to previous works. In particular, a MIMO MAC with one base station (BS) equipped with several distributed antenna sets is considered. Each link between a user and a BS antenna set forms a jointly correlated Rician fading channel. The analysis is based on operator-valued free probability theory, which broadens the range of applicability of free probability techniques tremendously. By replacing independent Gaussian random matrices with operator-valued random variables satisfying certain operator-valued freeness relations, the free deterministic equivalent of the considered channel Gram matrix is obtained. The Shannon transform of the free deterministic equivalent is derived, which provides an approximate expression for the ergodic input-output mutual information of the channel. The sum-rate capacity achieving input covariance matrices are also derived based on the approximate ergodic input-output mutual information. The free deterministic equivalent results are easy to compute, and simulation results show that these approximations are numerically accurate and computationally efficient. [ABSTRACT FROM PUBLISHER]

We consider low-density parity-check (LDPC) code ensembles over non-binary Galois fields when used for transmission over arbitrary discrete memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter, we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles. [ABSTRACT FROM AUTHOR]

In this paper, we investigate problems of communication over physically degraded, state-dependent broadcast channels (BCs) with cooperating decoders. Two different setups are considered, and their capacity regions are characterized. First, we study a setting in which one decoder can use a finite capacity link to send the other decoder information regarding the messages or the channel states. In this scenario, we analyze two cases: one, where noncausal state information, is available to the encoder and the strong decoder, and the other, where state information, is available only to the encoder in a causal manner. Second, we examine a setting in which the cooperation between the decoders is limited to taking place before the outputs of the channel are given. In this case, one decoder, which is informed of the state sequence noncausally, can cooperate only to send the other decoder rate-limited information about the state sequence. The proofs of the capacity regions introduce a new idea of coding for channels with cooperation between different users, where we exploit the link between the decoders for multiple binnings. Finally, we discuss the optimality of using rate-splitting techniques when coding for cooperative BCs. In particular, we show that rate splitting is not necessarily optimal when coding for cooperative BCs by solving an example in which our method of coding outperforms rate splitting. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of generating arbitrary three-party correlations from a combination of public and secret correlations. Two parties—called Alice and Bob—share perfectly correlated bits that are secret from a collaborating third party, Charlie. At the same time, all three parties have access to a separate source of correlated bits, and their goal is to convert these two resources into multiple copies of some given tripartite distribution \mathbb P(XYZ) . We obtain a single-letter characterization of the tradeoff between public and private bits that are needed to achieve this task. The rate of private bits is shown to generalize Wyner’s classic notion of common information held between a pair of random variables. The problem we consider can be contrasted fruitfully with the task of secrecy formation, in which \mathbb P(XYZ) is generated using public communication and local randomness but with Charlie functioning as an adversary instead of a collaborator. We describe in detail the differences between the collaborative and adversarial scenarios. [ABSTRACT FROM AUTHOR]

Explicit characterization of the capacity region of communication networks is a long-standing problem. While it is known that network coding can outperform routing and replication, the set of feasible rates is not known in general. Characterizing the network coding capacity region requires the determination of the set of all entropic vectors. Furthermore, computing the explicitly known linear programming bound is infeasible in practice due to an exponential growth in complexity as a function of network size. This paper focuses on the fundamental problems of characterization and computation of outer bounds for multi-source multi-sink networks. Starting from the known local functional dependence induced by the communication network, we introduce the notion of irreducible sets, which characterize implied functional dependence. We provide recursions for the computation of all maximal irreducible sets. These sets act as information-theoretic bottlenecks, and provide an easily computable outer bound for networks with correlated sources. We extend the notion of irreducible sets (and resulting outer bound) for networks with independent sources. We compare our bounds with existing bounds in the literature. We find that our new bounds are the best among the known graph theoretic bounds for networks with correlated sources and for networks with independent sources. [ABSTRACT FROM AUTHOR]

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, and more capable). In particular, we introduce the notion of effectively less noisy broadcast channel and show that it implies less noisy but is not in general implied by more capable. For the rest of the channel parameter values, we show that there is a gap between Marton’s inner bound and the UV outer bound. [ABSTRACT FROM AUTHOR]

Wyner’s common information was originally defined for a pair of dependent discrete random variables. Its significance is largely reflected in, and also confined to, several existing interpretations in various source coding problems. This paper attempts to expand its practical significance by providing a new operational interpretation. In the context of the Gray–Wyner network, it is established that Wyner’s common information has a new lossy source coding interpretation. Specifically, it is established that, under suitable conditions, Wyner’s common information equals to the smallest common message rate when the total rate is arbitrarily close to the rate distortion function with joint decoding for the Gray–Wyner network. A surprising observation is that such equality holds independent of the values of distortion constraints as long as the distortions are within some distortion region. The new lossy source coding interpretation provides the first meaningful justification for defining Wyner’s common information for continuous random variables and the result can also be extended to that of multiple variables. Examples are given for characterizing the rate distortion region for the Gray–Wyner lossy source coding problem and for identifying conditions under which Wyner’s common information equals that of the smallest common rate. As a by-product, the explicit expression for the common information between a pair of Gaussian random variables is obtained. [ABSTRACT FROM AUTHOR]

Let X be an arbitrary continuous random variable and Z be an independent Gaussian random variable with zero mean and unit variance. For t>0 , Costa proved that is concave in t , where the proof hinged on the first and second order derivatives of h(X+\sqrt tZ) . In particular, these two derivatives are signed, i.e., ( \partial / \partial t)h(X+\sqrt tZ) \geq 0 and ( \partial ^2/ \partial t^2)h(X+\sqrt tZ) \leq 0 . In this paper, we show that the third order derivative of h(X+\sqrt tZ) is nonnegative, which implies that the Fisher information J(X+\sqrt tZ) is convex in t . We further show that the fourth order derivative of _{\vphantom {\{}} the first four derivatives, we make two conjectures on h(X+\sqrt tZ) : the first is that ({\partial ^{n}}/{\partial t^{n}}) h(X+\sqrt {t}Z)$ is nonnegative in t$ if n$ is odd, and nonpositive otherwise; the second is that is convex in t$ . The first conjecture can be rephrased in the context of completely monotone functions: t$ . The history of the first conjecture may date back to a problem in mathematical physics studied by McKean in 1966. Apart from these results, we provide a geometrical interpretation to the covariance-preserving transformation and study the concavity of , revealing its connection with Costa’s entropy power inequality. [ABSTRACT FROM PUBLISHER]

Mrs. Gerber’s Lemma lower bounds the entropy at the output of a binary symmetric channel in terms of the entropy of the input process. In this paper, we lower bound the output entropy via a different measure of input uncertainty, pertaining to the minimum mean squared error prediction cost of the input process. We show that in many cases our bound is tighter than the one obtained from Mrs. Gerber’s Lemma. As an application, we evaluate the bound for binary hidden Markov processes, and obtain new estimates for the entropy rate. [ABSTRACT FROM PUBLISHER]

Hilberg’s conjecture about natural language states that the mutual information between two adjacent long blocks of text grows like a power of the block length. The exponent in this statement can be upper bounded using the pointwise mutual information estimate computed for a carefully chosen code. The bound is the better, the lower the compression rate is, but there is a requirement that the code be universal. So as to improve a received upper bound for Hilberg’s exponent, in this paper, we introduce two novel universal codes, called the plain switch distribution and the preadapted switch distribution. Generally speaking, switch distributions are certain mixtures of adaptive Markov chains of varying orders with some additional communication to avoid the so-called catch-up phenomenon. The advantage of these distributions is that they both achieve a low compression rate and are guaranteed to be universal. Using the switch distributions, we obtain that a sample of a text in English is non-Markovian with Hilberg’s exponent being ≤0.83, which improves over the previous bound ≤0.94 obtained using the Lempel–Ziv code. [ABSTRACT FROM PUBLISHER]

In 1733, Georges-Louis Leclerc, Comte de Buffon in France, set the ground of geometric probability theory by defining an enlightening problem: what is the probability that a needle thrown randomly on a ground made of equispaced parallel strips lies on two of them? In this paper, we show that the solution to this problem, and its generalization to N dimensions, allows us to discover a quantized form of the Johnson-Lindenstrauss (JL) lemma, i.e., one that combines a linear dimensionality reduction procedure with a uniform quantization of precision \delta >0 . In particular, given a finite set \mathcal S \subset \mathbb R ^N of S points and a distortion level \epsilon >0 , as soon as M > M_{0} = O(\epsilon ^{-2} \log S) , we can (randomly) construct a mapping from ( \mathcal S, \ell _{2}) to ( \delta \mathbb Z^M, \ell 1) that approximately preserves the pairwise distances between the points of \mathcal S . Interestingly, compared with the common JL lemma, the mapping is quasi-isometric and we observe both an additive and a multiplicative distortions on the embedded distances. These two distortions, however, decay as O((\log S/M)^1/2) when M increases. Moreover, for coarse quantization, i.e., for high \delta compared with the set radius, the distortion is mainly additive, while for small \delta we tend to a Lipschitz isometric embedding. Finally, we prove the existence of a nearly quasi-isometric embedding of into ( \delta \mathbb Z^{M}, \ell _{2}) . This one involves a non-linear distortion of the \ell _{2}$ -distance in \mathcal S$ that vanishes for distant points in this set. Noticeably, the additive distortion in this case is slower, and decays as O((\log S/M)^{1/4}) . [ABSTRACT FROM PUBLISHER]

We consider the problem of channel state amplification in a Gaussian channel with additive Gaussian channel states, where the encoder observes noncausally a noisy version of these states. A complete characterization is provided for the minimum reconstruction distortion under a transmitter power constraint, and it is shown that a simple analog scheme with power control is optimal. More precisely, if the power available to the encoder is below certain threshold, the analog scheme using full power is optimal, however, when the power available to the encoder is above that threshold, analog transmission using only a fixed amount of the available power is optimal. Furthermore, the problem of simultaneous message transmission and Gaussian state amplification with noisy observations is studied, for which an inner bound and two nontrivial outer bounds to the optimal tradeoff between the transmission rate and the state reconstruction distortion are provided. The coding scheme underlying the inner bound combines analog signaling and Gelfand-Pinsker coding, where the latter deviates from the operating point of Costa’s dirty paper coding. The first outer bound is obtained by extending the channel decomposition technique, while the second outer bound requires a strategic analysis of the covariance matrix of the relevant random variables. [ABSTRACT FROM AUTHOR]

Non-locality is the phenomenon of observing strong correlations among the outcomes of local measurements of a multipartite physical system. No-signaling boxes are the abstract objects for studying non-locality, and wirings are local operations on the space of no-signaling boxes. This means that, no matter how non-local the nature is, the set of physical non-local correlations must be closed under wirings. Then, one approach to identify the non-locality of nature is to characterize the closed sets of non-local correlations. Although non-trivial examples of wirings of no-signaling boxes are known, there is no systematic way to study wirings. In particular, given a set of no-signaling boxes, we do not know a general method to prove that it is closed under wirings. In this paper, we propose the first general method to construct such closed sets of non-local correlations. We show that a well-known measure of correlation, called maximal correlation, when appropriately defined for non-local correlations, is monotonically decreasing under wirings. This establishes a conjecture about the impossibility of simulating isotropic boxes from each other, implying the existence of a continuum of closed sets of non-local boxes under wirings. To prove our main result, we introduce some mathematical tools that may be of independent interest: we define a notion of maximal correlation ribbon as a generalization of maximal correlation, and provide a connection between it and a known object called hypercontractivity ribbon; we show that these two ribbons are monotone under wirings too. [ABSTRACT FROM AUTHOR]

We consider two secret key generation problems under a pairwise independent network model, and propose low complexity key generation schemes in a framework that connects our problems to network flow problems in graphs. Our schemes have two components: 1) local key generation and 2) global key propagation. In the local key generation, we use point-to-point source coding with side information to establish pairwise keys, from which we construct a graph with the capacity of each edge being the key rate of the corresponding point-to-point local key. In the global key propagation, depending on the particular problem, secret keys are delivered to users in the network using various network flow algorithms. In particular, in the first problem in which one is required to generate a group key for a group of users in the network, we propose a network coding-based global key propagation approach. This approach has a low complexity and has a better performance than the existing approach. In the second problem, in which one is required to generate multiple keys simultaneously for different pairs of users, we propose a multicommodity flow-based global key propagation approach. We show that the proposed approach is optimal for the case of generating two keys. For the general case of generating more than two keys, we show that the sum rate of the proposed scheme is larger than an upper bound characterized in this paper divided by a constant. [ABSTRACT FROM AUTHOR]

Suppose $M$ records are replicated in $N$ servers (each storing all $M$ records), a user wants to privately retrieve one record by accessing the servers such that the identity of the retrieved record is secret against any up to $T$ servers. A scheme designed for this purpose is called a $T$ -private information retrieval (PIR) scheme. In practice, capacity-achieving and small sub-packetization are both desired for PIR schemes, because the former implies the highest download rate and the latter means simple realization. Meanwhile, sub-packetization is the key technique for achieving capacity. In this paper, we characterize the optimal sub-packetization for linear capacity-achieving $T$ -PIR schemes. First, a lower bound on the sub-packetization $L$ for linear capacity-achieving $T$ -PIR schemes is proved, i.e., $L\geq dn^{M-1}$ , where $d={\mathrm{ gcd}}(N,T)$ and $n=N/d$. Then, for general values of $M$ and $N>T\geq 1$ , a linear capacity-achieving $T$ -PIR scheme with sub-packetization $dn^{M-1}$ is designed. Comparing with the first capacity-achieving $T$ -PIR scheme given by Sun and Jafar in 2016, our scheme reduces the sub-packetization from $N^{M}$ to the optimal and further reduces the field size by a factor of $Nd^{M-2}$. [ABSTRACT FROM AUTHOR]

Fast polarization is crucial for the performance guarantees of polar codes. In the memoryless setting, the rate of polarization is known to be exponential in the square root of the block length. A complete characterization of the rate of polarization for models with memory has been missing. Namely, previous works have not addressed fast polarization of the high entropy set under memory. We consider polar codes for processes with memory that are characterized by an underlying ergodic finite-state Markov chain. We show that the rate of polarization for these processes is the same as in the memoryless setting, both for the high and for the low entropy sets. [ABSTRACT FROM AUTHOR]

A new finite blocklength converse for the Slepian–Wolf coding problem, which significantly improves on the best-known converse due to Miyake and Kanaya, is presented. To obtain this converse, an extension of the linear programming (LP)-based framework for finite blocklength point-to-point coding problems is employed. However, a direct application of this framework demands a complicated analysis for the Slepian–Wolf problem. An analytically simpler approach is presented, wherein LP-based finite blocklength converses for this problem are synthesized from point-to-point lossless source coding problems with perfect side-information at the decoder. New finite blocklength converses for these point-to-point problems are derived by employing the LP-based framework, and the new converse for Slepian–Wolf coding is obtained by an appropriate combination of these converses. [ABSTRACT FROM AUTHOR]

We investigate the problem of estimating a random variable $Y$ under a privacy constraint dictated by another correlated random variable $X$. When $X$ and $Y$ are discrete, we express the underlying privacy-utility tradeoff in terms of the privacy-constrained guessing probability ${\mathcal {h}}(P_{XY}, \varepsilon)$ , and the maximum probability $\mathsf {P}_{\mathsf {c}}(Y|Z)$ of correctly guessing $Y$ given an auxiliary random variable $Z$ , where the maximization is taken over all $P_{Z|Y}$ ensuring that $\mathsf {P}_{\mathsf {c}}(X|Z)\leq \varepsilon $ for a given privacy threshold $\varepsilon \geq 0$. We prove that ${\mathcal {h}}(P_{XY}, \cdot)$ is concave and piecewise linear, which allows us to derive its expression in closed form for any $\varepsilon $ when $X$ and $Y$ are binary. In the non-binary case, we derive ${\mathcal {h}}(P_{XY}, \varepsilon)$ in the high-utility regime (i.e., for sufficiently large, but nontrivial, values of $\varepsilon $) under the assumption that $Y$ and $Z$ have the same alphabets. We also analyze the privacy-constrained guessing probability for two scenarios in which $X$ , $Y$ , and $Z$ are binary vectors. When $X$ and $Y$ are continuous random variables, we formulate the corresponding privacy-utility tradeoff in terms of ${\mathsf {sENSR}}(P_{XY}, \varepsilon)$ , the smallest normalized minimum mean squared-error (mmse) incurred in estimating $Y$ from a Gaussian perturbation $Z$. Here, the minimization is taken over a family of Gaussian perturbations $Z$ for which the mmse of $f(X)$ given $Z$ is within a factor $1- \varepsilon $ from the variance of $f(X)$ for any non-constant real-valued function $f$. We derive tight upper and lower bounds for ${\mathsf {sENSR}}$ when $Y$ is Gaussian. For general absolutely continuous random variables, we obtain a tight lower bound for ${\mathsf {sENSR}}(P_{XY}, \varepsilon)$ in the high privacy regime, i.e., for small $\varepsilon $. [ABSTRACT FROM AUTHOR]

Let $X_{i}, i~\in V$ form a Markov random field (MRF) represented by an undirected graph $G = (V,E)$ , and $V'$ be a subset of $V$. We determine the smallest graph that can always represent the subfield $X_{i}, i~\in V'$ as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When $G$ is a path so that $X_{i}, i~\in V$ form a Markov chain, it is known that the $I$ -Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the $I$ -Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002). [ABSTRACT FROM AUTHOR]

Approximate capacity regions are established for a class of interfering multiple access channels consisting of two multiple-access channels (MACs), each with an arbitrary number of transmitters, with one transmitter in each MAC causing interference to the receiver of the other MAC, a channel we refer to henceforth as the MAC-IC-MAC. For the discrete memory-less (DM) MAC-IC-MAC, two inner bounds are obtained that are generalizations of prior inner bounds for the two-user DM interference channel (IC) due to Chong et al. For the semi-deterministic MAC-IC-MAC, it is shown that single-user coding at the non-interfering transmitters and superposition coding at the interfering transmitter of each MAC achieves a rate region that is within a quantifiable gap of the capacity region, thereby extending such a result for the two-user semi-deterministic IC by Telatar and Tse. For the Gaussian MAC-IC-MAC, an approximate capacity region that is within a constant gap of the capacity region is obtained, generalizing such a result for the two-user Gaussian IC by Etkin et al. On contrary to the aforementioned approximate capacity results for the two-user IC, whose achievability requires the union of all admissible input distributions, our gap results on the semi-deterministic and the Gaussian MAC-IC-MAC are achievable by only a subset and one of all admissible coding distributions, respectively. The symmetric generalized degrees of freedom (GDoFs) of the symmetric Gaussian MAC-IC-MAC with more than one user per cell, which is a function of the interference strength (the ratio of INR to SNR at high SNR, both expressed in dB) and the numbers of users in each cell, are V-shaped with flat shoulders. An analysis based on signal-level partitions shows that the non-interfering transmitters utilize the signal-level partitions at the receiver where they are intended that cannot be accessed by the interfering transmitters (due to the restriction of superposition coding), thereby improving the sum symmetric GDoF of up to one degree of freedom per cell under a range of SINR exponent levels, which in turn becomes wider as the number of transmitters in each cell increases. Consequently, time-sharing between interfering and non-interfering transmitters is GDoF-suboptimal in general, as is time-sharing between the two embedded MAC-Z-MACs. [ABSTRACT FROM AUTHOR]

Two widely studied models of multiple-node repair in distributed storage systems are centralized repair and cooperative repair. The centralized model assumes that all the failed nodes are recreated in one location, while the cooperative one stipulates that the failed nodes may communicate but are distinct, and the amount of data exchanged between them is included in the repair bandwidth. As our first result, we prove a lower bound on the minimum bandwidth of cooperative repair. We also show that the cooperative model is stronger than the centralized one, in the sense that any maximum distance separable (MDS) code with optimal repair bandwidth under the former model also has optimal bandwidth under the latter one. These results were previously known under the additional “uniform download” assumption, which is removed in our proofs. As our main result, we give explicit constructions of MDS codes with optimal cooperative repair for all possible parameters. More precisely, given any $n,k,h,d$ such that $2\le h \le n-d\le n-k$ we construct $(n,k)$ MDS codes over the field $F$ of size $|F|\ge (d+1-k)n$ that can optimally repair any $h$ erasures from any $d$ helper nodes. The repair scheme of our codes involves two rounds of communication. In the first round, each failed node downloads information from the helper nodes, and in the second one, each failed node downloads additional information from the other failed nodes. This implies that our codes achieve the optimal repair bandwidth using the smallest possible number of rounds. [ABSTRACT FROM AUTHOR]

This paper shows that the Maddah-Ali–Tse (MAT) scheme, which achieves the symmetric capacity of two example broadcast channels with strictly causal state information at the transmitter, is a simple special case of the Shayevitz–Wigger (SW) scheme for the broadcast channel with generalized feedback, which involves block Markov coding, Gray–Wyner compression, superposition coding, and Marton coding. Focusing on the class of symmetric broadcast channels with state, we derive an expression for the maximum achievable symmetric rate using the SW scheme. We show that the MAT results for the two-receiver case can be recovered by evaluating this expression for the special case in which superposition coding and Marton coding are not used. We then introduce a new broadcast channel example that shares many features of the MAT examples. We show that another special case of our maximum symmetric rate expression in which superposition coding is also used attains a higher symmetric rate than the MAT scheme. The symmetric capacity of this new example is not known, however. [ABSTRACT FROM PUBLISHER]

The $H$ -transforms are integral transforms that involve Fox’s $H$ -functions as kernels. A large variety of integral transforms can be put into particular forms of the $H$ -transform since $H$ -functions subsume most of the known special functions including Meijer’s $G$ -functions. In this paper, we embody the $H$ -transform theory into a unifying framework for modeling and analysis in wireless communication. First, we systematize the use of elementary identities and properties of the $H$ -transform by introducing operations on parameter sequences of $H$ -functions. We then put forth $H$ -fading and degree-2 irregular $H$ -fading to model radio propagation under composite, specular, and/or inhomogeneous conditions. The $H$ -fading describes composite effects of multipath fading and shadowing as a single $H$ -variate, including most of typical models such as Rayleigh, Nakagami- $m$ , Weibull, $ \alpha - \mu $ , $N\ast $ Nakagami- $m$ , (generalized) $K$ -fading, and Weibull/gamma fading as its special cases. As a new class of $H$ -variates (called the degree- $ \zeta $ irregular $H$ -variate), the degree-2 irregular $H$ -fading characterizes specular and/or inhomogeneous radio propagation in which the multipath component consists of a strong specularly reflected or line-of-sight (LOS) wave as well as unequal-power or correlated in-phase and quadrature scattered waves. This fading includes a variety of typical models such as Rician, Nakagami- $q$ , $ \kappa - \mu $ , $ \eta - \mu $ , Rician/LOS gamma, and $ \kappa - \mu $ /LOS gamma fading as its special cases. Finally, we develop a unifying $H$ -transform analysis for the amount of fading, error probability, channel capacity, and error exponent in wireless communication using the new systematic language of transcendental $H$ -functions. By virtue of two essential operations—called Mellin and convolution operations—involved in the Mellin transform and Mellin convolution of two $H$ -functions, the $H$ -transforms for these performance measures culminate in $H$ -functions. Using the algebraic asymptotic expansions of the $H$ -transform, we further analyze the error probability and capacity at high and low signal-to-noise ratios in a unified fashion. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the fluctuation of mutual information statistics of a multiple input multiple output channel communication systems without assuming that the entries of the channel matrix have zero pseudovariance. To this end, we also establish a central limit theorem of the linear spectral statistics for sample covariance matrices under general moment conditions by removing the restrictions imposed on the second moment and fourth moment on the matrix entries in Bai and Silverstein (2004). [ABSTRACT FROM AUTHOR]

This paper shows the strong converse and the dispersion of memoryless channels with cost constraints and performs a refined analysis of the third-order term in the asymptotic expansion of the maximum achievable channel coding rate, showing that it is equal to (1/ 2)((\log n)/n) in most cases of interest. The analysis is based on a nonasymptotic converse bound expressed in terms of the distribution of a random variable termed the $\mathsf b$ -tilted information density, which plays a role similar to that of the $\mathsf d$ -tilted information in lossy source coding. We also analyze the fundamental limits of lossy joint-source-channel coding over channels with cost constraints. [ABSTRACT FROM AUTHOR]

This paper considers relay assisted transmission for multiuser networks when the relay has no access to the codebooks used by the transmitters. The relay is called oblivious for this reason. Of particular interest is the generalized compress-and-forward (GCF) strategy, where the destinations jointly decode the compression indices and the transmitted messages, and their optimality in this setting. The relay-to-destination links are assumed to be out-of-band with finite capacity. Two models are investigated: 1) the multiple access relay channel (MARC) and 2) the interference relay channel (IFRC). For the MARC with an oblivious relay, a new outerbound is derived and it is shown to be tight by means of achievability of the capacity region using GCF scheme. For the IFRC with an oblivious relay, a new strong interference condition is established, under which the capacity region is found by deriving a new outerbound and showing that it is achievable using GCF scheme. The result is further extended to establish the capacity region of M-user MARC with an oblivious relay, and multicast networks containing $M$ sources and $K$ destinations with an oblivious relay. [ABSTRACT FROM PUBLISHER]

This paper presents polar coding schemes for the two-user discrete memoryless broadcast channel (DM-BC) which achieve Marton’s region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of two-user DM-BCs whose capacity regions are known. To accomplish this task, we first construct polar codes for both the superposition as well as binning strategy. By combining these two schemes, we obtain Marton’s region with private messages only. Finally, we show how to handle the case of common information. The proposed coding schemes possess the usual advantages of polar codes, i.e., they have low encoding and decoding complexity and a superpolynomial decay rate of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who recently introduced polar codes emulating the superposition and binning schemes. To align the polar indices, for both schemes, their solution involves some degradedness constraints that are assumed to hold between the auxiliary random variables and channel outputs. To remove these constraints, we consider the transmission of $k$ blocks and employ a chaining construction that guarantees the proper alignment of the polarized indices. The techniques described in this paper are quite general, and they can be adopted to many other multiterminal scenarios whenever there polar indices need to be aligned. [ABSTRACT FROM AUTHOR]

Information theory provides principled ways to analyze different inference and learning problems, such as hypothesis testing, clustering, dimensionality reduction, classification, and so forth. However, the use of information theoretic quantities as test statistics, that is, as quantities obtained from empirical data, poses a challenging estimation problem that often leads to strong simplifications, such as Gaussian models, or the use of plug in density estimators that are restricted to certain representation of the data. In this paper, a framework to nonparametrically obtain measures of entropy directly from data using operators in reproducing kernel Hilbert spaces defined by infinitely divisible kernels is presented. The entropy functionals, which bear resemblance with quantum entropies, are defined on positive definite matrices and satisfy similar axioms to those of Renyi’s definition of entropy. Convergence of the proposed estimators follows from concentration results on the difference between the ordered spectrum of the Gram matrices and the integral operators associated to the population quantities. In this way, capitalizing on both the axiomatic definition of entropy and on the representation power of positive definite kernels, the proposed measure of entropy avoids the estimation of the probability distribution underlying the data. Moreover, estimators of kernel-based conditional entropy and mutual information are also defined. Numerical experiments on independence tests compare favorably with state-of-the-art. [ABSTRACT FROM PUBLISHER]

Information theoretical inequalities have strong ties with polymatroids and their representability. A polymatroid is entropic if its rank function is given by the Shannon entropy of the subsets of some discrete random variables. The book is a special iterated adhesive extension of a polymatroid with the property that entropic polymatroids have \(n\) -page book extensions over an arbitrary spine. We prove that every polymatroid has an \(n\) -page book extension over a single element and over an all-but-one-element spine. Consequently, for polymatroids on four elements, only book extensions over a two-element spine should be considered. Matúš proved that the Zhang–Yeung inequalities characterize polymatroids on four elements which have such a two-page book extension. The \(n\) -page book inequalities, defined in this paper, are conjectured to characterize polymatroids on four elements which have \(n\) -page book extensions over a two-element spine. We prove that the condition is necessary; consequently, every book inequality is an information inequality on four random variables. Using computer-aided multiobjective optimization, the sufficiency of the condition is verified up to nine-page book extensions. [ABSTRACT FROM PUBLISHER]

We show how to efficiently simulate the sending of a single message \(M\) to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver. This is a generalization and strengthening of the Slepian–Wolf theorem, which shows how to carry out such a simulation with low amortized communication in the case that \(M\) is a deterministic function of \(X\) . A caveat is that our simulation is interactive. As a consequence, we prove that the internal information cost (namely the information revealed to the parties) involved in computing any relation or function using a two party interactive protocol is exactly equal to the amortized communication complexity of computing independent copies of the same relation or function. We also show that the only way to prove a strong direct sum theorem for randomized communication complexity is by solving a particular variant of the pointer jumping problem that we define. This paper implies that a strong direct sum theorem for communication complexity holds if and only if efficient compression of communication protocols is possible. In particular, together with our result, a recent result of Ganor, Kol, and Raz implies that the strongest version of direct sum for randomized communication complexity is false. [ABSTRACT FROM AUTHOR]

The two-user compound Gaussian MIMO broadcast channel models the situation where each user has a finite set of possible realizations. The transmitter sends two messages, one for each user, such that each user must be able to decode its message regardless of the actual realization. This channel also models a broadcast channel (BC) with two groups of users and two messages, with one message intended for each group of users. Weingarten et al. established the capacity region for the degraded case where the realizations/users exhibit a degradedness order. The degradedness order is defined through an additional realization/user where the realizations/users from one set are degraded with respect to him and where he is degraded with respect to the realizations/users from the other set. To show that Gaussian inputs attain the capacity region, they proved a new extremal inequality and employed the use of the channel enhancement technique as well. In this paper, we extend the result to the \(N\) -user degraded compound Gaussian MIMO BC, where the \(N\) users exhibit a degradedness order similar to the two-user case. We first prove a generalization of the extremal inequality considered by Weingarten et al.; instead of considering the difference between the weighted sum of two sets of conditional differential entropies, we consider the summation of \(N-1\) sets of such differences, where the conditioning random variables of the \(N-1\) sets form a Markov chain. Our proof relies on the Gaussian perturbation approach, the necessary KKT conditions as well as a data processing inequality. Finally, we specialize the generalized extremal inequality to characterize the capacity region of the \(N\) -user degraded compound Gaussian MIMO BC. By making appropriate use of the necessary KKT conditions, we are able to do away with the use of the channel enhancement technique that was employed in the proof of the capacity region of the two-user case. [ABSTRACT FROM AUTHOR]

We study a two-transmitter two-receiver network where Receiver 1 can only hear the transmitted signal of Transmitter 1. Transmitter 1 has two messages, one of which is intended for Receiver 1 while both are intended for Receiver 2. Transmitter 2 has one message which is intended for Receiver 2. We call this channel model the Z channel with degraded message sets. For networks with the element of distributed encoding, it has been shown that when the multiple access link between the two encoders and the decoder satisfies the conditions proposed by Liu and Goldsmith, capacity results can be obtained for a variety of problems. In this paper, we generalize these conditions and show that for a larger class of multiple access links, the capacity region of the Z channel with degraded message sets can be characterized despite the presence of distributed encoding. [ABSTRACT FROM AUTHOR]

The problem of simultaneously generating a secret key (SK) and private key (PK) pair among three terminals via public discussion is investigated. In this problem, each terminal observes a component of correlated sources. All three terminals are required to generate the common SK to be concealed from an eavesdropper that has access to the public discussion, while two designated terminals are required to generate an extra PK to be concealed from both the eavesdropper and the remaining terminal. An outer bound on the SK-PK capacity region was established by Ye and Narayan, and was shown to be achievable for a special case. In this paper, the SK-PK capacity region is established in general by developing schemes to achieve the outer bound for the remaining two cases. The main technique lies in the novel design of a random binning-joint decoding scheme that achieves the existing outer bound. [ABSTRACT FROM AUTHOR]

In this paper, the discrete memoryless arbitrarily varying broadcast channel (AVBC) with receiver side information is studied and its random code and deterministic code capacity regions are derived for the average error criterion. In addition, it is analyzed for deterministic list codes and it is shown that the corresponding list capacity region displays a behavior, which is similar to Ahlswede’s famous dichotomy result for the single-user arbitrarily varying channel: it either equals the random code capacity region or otherwise has an empty interior. This is characterized in terms of list sizes at the receivers and an appropriate concept of symmetrizability for the AVBC with receiver side information. The scenario studied here is motivated by the broadcast phase of bidirectional relaying, where a half-duplex relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol. The relay decodes the messages both nodes have sent in the initial multiple access phase and broadcasts a re-encoded composition of them in the succeeding broadcast phase. Then, the broadcast phase corresponds to the AVBC with receiver side information, which differs from the classical broadcast channel, since both receivers can exploit their own messages from the previous phase as side information for decoding. [ABSTRACT FROM PUBLISHER]

The sumset and inverse sumset theories of Freiman, Plünnecke, and Ruzsa, give bounds connecting the cardinality of the sumset \(A+B=\{a+b;\;a\in A,\,b\in B\}\) of two discrete sets \(A,B\) , to the cardinalities (or the finer structure) of the original sets \(A,B\) . For example, the sum-difference bound of Ruzsa states that, \(|A+B|\,|A|\,|B|\leq |A-B|^3\) , where the difference set \(A-B= \{a-b;\;a\in A,\,b\in B\}\) . Interpreting the differential entropy \(h(X)\) of a continuous random variable \(X\) as (the logarithm of) the size of the effective support of \(X\) , the main contribution of this paper is a series of natural information-theoretic analogs for these results. For example, the Ruzsa sum–difference bound becomes the new inequality, \(h(X+Y)+h(X)+h(Y)\leq 3h(X-Y)\) , for any pair of independent continuous random variables \(X\) and \(Y\) . Our results include differential-entropy versions of Ruzsa’s triangle inequality, the Plünnecke–Ruzsa inequality, and the Balog–Szemerédi–Gowers lemma. In addition, we give a differential entropy version of a Freiman–type inverse-sumset theorem, which can be seen as a quantitative converse to the entropy power inequality. Versions of most of these results for the discrete entropy \(H(X)\) were recently proved by Tao, relying heavily on a strong, functional form of the submodularity property of \(H(X)\) . Since differential entropy is not functionally submodular, in the continuous case many of the corresponding discrete proofs fail, in many cases requiring substantially new proof strategies. We find that the basic property that naturally replaces the discrete functional submodularity, is the data processing property of mutual information. [ABSTRACT FROM PUBLISHER]

This paper studies the basic question of whether a given channel $V$ can be dominated (in the precise sense of being more noisy) by a $q$ -ary symmetric channel. The concept of less noisy relation between channels originated in network information theory (broadcast channels) and is defined in terms of mutual information or Kullback–Leibler divergence. We provide an equivalent characterization in terms of $\chi ^{2}$ -divergence. Furthermore, we develop a simple criterion for domination by a $q$ -ary symmetric channel in terms of the minimum entry of the stochastic matrix defining the channel $V$. The criterion is strengthened for the special case of additive noise channels over finite Abelian groups. Finally, it is shown that domination by a symmetric channel implies (via comparison of Dirichlet forms) a logarithmic Sobolev inequality for the original channel. [ABSTRACT FROM AUTHOR]

We establish the rate region of an extended Gray–Wyner system (EGW) for 2-DMS $(X,Y)$ with two additional decoders having complementary causal side information. We show that the 5-D rate region of the EGW system is equivalent to the 3-D mutual information region consisting of the set of all triples of the form $(I(X;U),\,I(Y;U),\,I(X,Y;U))$ for some $p_{U|X,Y}$. This correspondence greatly simplifies the exploration of the the extreme points of the rate region. In addition to the operationally significant extreme points of the original Gray–Wyner rate region, which include Wyner’s common information, Gács-Körner common information, and the information bottleneck, the extreme points of the rate region for the EGW system also include the Körner graph entropy, the privacy funnel and excess functional information, as well as three new quantities of potential interest. We further show that projections of the mutual information region yield the rate regions for many settings involving a two discrete memoryless source (2-DMS), including lossless source coding with causal side information, distributed channel synthesis, and lossless source coding with a helper. To further motivate the mutual information region itself, we draw analogies between set operations and its extreme points. This allows us to find random variables that can be considered as intersection, difference, and symmetric difference of two random variables. Finally, we establish the rate regions for two related setups to the EGW system, namely, the noncausal EGW system and the lossy EGW system. [ABSTRACT FROM AUTHOR]

The sparsity and compressibility of finite-dimensional signals are of great interest in fields, such as compressed sensing. The notion of compressibility is also extended to infinite sequences of independent identically distributed or ergodic random variables based on the observed error in their nonlinear $k$ -term approximation. In this paper, we use the entropy measure to study the compressibility of continuous-domain innovation processes (alternatively known as white noise). Specifically, we define such a measure as the entropy limit of the doubly quantized (time and amplitude) process. This provides a tool to compare the compressibility of various innovation processes. It also allows us to identify an analogue of the concept of “entropy dimension” which was originally defined by Rényi for random variables. Particular attention is given to stable and impulsive Poisson innovation processes. Here, our results recognize Poisson innovations as the more compressible ones with an entropy measure far below that of stable innovations. While this result departs from the previous knowledge regarding the compressibility of impulsive Poisson laws compared with continuous fat-tailed distributions, our entropy measure ranks $\alpha$ -stable innovations according to their tail. [ABSTRACT FROM AUTHOR]

The problem of zero-rate multiterminal hypothesis testing is revisited from the perspective of information-spectrum approach and finite blocklength analysis. A Neyman–Pearson-like test is proposed and its non-asymptotic performance is clarified, for a short block length, it is numerically determined that the proposed test is superior to the previously reported Hoeffding-like test proposed by Han–Kobayashi. For a large deviation regime, it is shown that our proposed test achieves an optimal trade-off between the type I and type II exponents presented by Han–Kobayashi. Among the class of symmetric (type-based) testing schemes, when the type I error probability is non-vanishing, the proposed test is optimal up to the second-order term of the type II error exponent; the latter term is characterized in terms of the variance of the projected relative entropy density. The information geometry method plays an important role in the analysis as well as the construction of the test. [ABSTRACT FROM AUTHOR]

We consider a broadcast channel with three receivers and three-degraded message sets, i.e., the transmitter has a common message intended for all three receivers, a message intended for receivers 2 and 3, and a private message intended only for receiver 3. The messages are transmitted over a family of parallel degraded broadcast channels. In the most general case, the broadcast channel consists of the product of six parallel degraded broadcast channels, each with a different order of degradedness. We first consider an achievable rate region of Nair and El Gamal, by appropriately choosing independent input random variables and auxiliary random variables for each subchannel. We then show that the achievable rate region attains the capacity region for two different classes of such broadcast channels, one consisting of the product of five parallel degraded broadcast channels and another consisting of the product of three parallel degraded broadcast channels. To accomplish this, we make use of an information-theoretic inequality that may be proven using the Csiszár-sum identity. Next, we extend the result to the Gaussian case. We consider the aligned Gaussian MIMO broadcast channel consisting of the product of six parallel degraded Gaussian broadcast channels, where the Gaussian noise vectors for each of the users in each of the subchannels follow a degradedness order, i.e., the noise covariance matrices may be ordered in a positive semi-definite sense. We show that the Nair–El Gamal achievable rate region considered in this paper is maximized by Gaussian inputs. To prove that Gaussian inputs are optimal, we prove an extremal entropy inequality employing a new method recently introduced by Geng and Nair to prove the capacity region of the two-user Gaussian MIMO broadcast channel with common and private messages. [ABSTRACT FROM AUTHOR]

In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasi-cyclic (QC) LDPC codes. We prove that for a random bipartite graph, with a given (irregular) degree distribution, the distributions of cycles of different length tend to independent Poisson distributions, as the size of the graph tends to infinity. We derive asymptotic upper and lower bounds on the expected values of the Poisson distributions that are independent of the size of the graph, and only depend on the degree distribution and the cycle length. For a random lift of a bi-regular protograph, we prove that the asymptotic cycle distributions are essentially the same as those of random bipartite graphs as long as the degree distributions are identical. For random QC-LDPC codes, however, we show that the cycle distribution can be quite different from the other two categories. In particular, depending on the protograph and the value of $c$ , the expected number of cycles of length $c$ , in this case, can be either $\Theta (N)$ or $\Theta (1)$ , where $N$ is the lifting degree (code length). We also provide numerical results that match our theoretical derivations. Our results provide a theoretical foundation for emperical results that were reported in the literature but were not well-justified. They can also be used for the analysis and design of LDPC codes and associated algorithms that are based on cycles. [ABSTRACT FROM AUTHOR]

We show that the inequality H(A | B,X) + H(A | B,Y) \leqslant H(A | B) for jointly distributed random variables A,B,X,Y , which does not hold in general case, holds under some natural condition on the support of the probability distribution of A,B,X,Y . This result generalizes a version of the conditional Ingleton inequality: if for some distribution , then I(A \mskip 5mu {:} \mskip 5mu B) \leqslant I(A \mskip 5mu {:} \mskip 5mu B | X) + I(A \mskip 5mu {:} \mskip 5mu B | Y) + I(X \mskip 5mu {:} \mskip 5mu Y) . We present two applications of our result. The first one is the following easy-to-formulate theorem on edge colorings of bipartite graphs: assume that the edges of a bipartite graph are colored in K$ colors so that each two edges sharing a vertex have different colors and for each pair (left vertex $x$ , right vertex $y$ ) there is at most one color $a$ such both $x$ and $y$ are incident to edges with color $a$ ; assume further that the degree of each left vertex is at least $L$ and the degree of each right vertex is at least $R$ . Then $K \geqslant LR$ . The second application is a new method to prove lower bounds for biclique cover of bipartite graphs. [ABSTRACT FROM PUBLISHER]