Extreme point representations are utilized together with facet membership to gain insights about the relationship between various bounds on the set of normalized entropic vectors in 4 random variables. Echoing prior results from Matúš (1995), we begin by showing that the 206 extreme points of the Shannon outer bound comprise 33 forms where 16 of these forms are entropic and achievable with binary random variables (one bit), 16 of the forms are entropic and achievable using two bits, and the remaining single form of six extreme points is not entropic, not achievable with two bits, and is the only violator of the Ingleton inequality. Thus, the Ingleton inner bound is matched to the Shannon outer bound in that it contains all entropic Shannon extreme points. Further novel investigation of the structure of the Ingleton and Shannon polytopes reveal that every facet of the Shannon outer bound requires two bits per variable and can be improved upon. The inner bound formed from the convex hull of the set of binary entropic vectors is shown to neither contain nor be contained in the Ingleton inner bound, and is shown to not be a polytope. The addition of the non-Shannon-type inequality due to Zhang and Yueng plus the six non-Shannon-type inequalities due to Dougherty, Freiling, and Zeger yield a polytopic outer bound where none of the non-Shannon extreme points obey Ingleton or are binary achievable. Worst case distance gaps between the various bounds are calculated.
Extreme point representations are utilized together with facet membership to gain insights about the relationship between various bounds on the set of normalized entropic vectors in 4 random variables. Echoing prior results from Matúš (1995), we begin by showing that the 206 extreme points of the Shannon outer bound comprise 33 forms where 16 of these forms are entropic and achievable with binary random variables (one bit), 16 of the forms are entropic and achievable using two bits, and the remaining single form of six extreme points is not entropic, not achievable with two bits, and is the only violator of the Ingleton inequality. Thus, the Ingleton inner bound is matched to the Shannon outer bound in that it contains all entropic Shannon extreme points. Further novel investigation of the structure of the Ingleton and Shannon polytopes reveal that every facet of the Shannon outer bound requires two bits per variable and can be improved upon. The inner bound formed from the convex hull of the set of binary entropic vectors is shown to neither contain nor be contained in the Ingleton inner bound, and is shown to not be a polytope. The addition of the non-Shannon-type inequality due to Zhang and Yueng plus the six non-Shannon-type inequalities due to Dougherty, Freiling, and Zeger yield a polytopic outer bound where none of the non-Shannon extreme points obey Ingleton or are binary achievable. Worst case distance gaps between the various bounds are calculated.
This paper suggests that information geometry may form a natural framework to deal with the unknown part of the boundary of entropic region. An application of information geometry shows that distributions associated with Shannon facets can be associated, in the right coordinates, with affine collections of distributions. This observation allows an information geometric reinterpretation of the Shannon-type inequalities as arising from a Pythagorean style relationship. The set of distributions which violate Ingleton's inequality, and hence are linked with the part of the entropic region which is yet undetermined, is shown also to have a surprising affine information geometric structure in a special case involving four random variables and a certain support. These facts provide strong evidence for the link between information geometry and characterizing the boundary of the entropic region.
For four finite discrete random variables, we prove that the negative of the Ingleton expression, divided by the joint entropy, is at most 19/124≈0.15323, improving the previously reported upper bound 3/19 by 11/2356. The proof uses a copy program with four copy steps and six auxiliary variables, certified by exact rational linear-programming certificates. We also show that two published information inequalities, due to Dougherty-Freiling-Zeger and Csirmaz, imply the bound 5/32 by an explicit nonnegative combination with Shannon inequalities, and that 5/32 is the exact optimum both of the union of the three published inequality catalogues considered here and of the full copy-lemma extensions of all 213 distinct copy programs occurring in them. The new program is not among these programs, and the bound 19/124 remains optimal when all of them and all catalogue inequalities are added. Ancillary files provide the parsed catalogues, exact primal and dual certificates, exact extension certificates, and verifiers that use only the Python standard library.
The entropic region is formed by the collection of the Shannon entropies of all subvectors of finitely many jointly distributed discrete random variables. For four or more variables, the structure of the entropic region is mostly unknown. We utilize a variant of the Maximum Entropy Method to obtain five-variable non-Shannon entropy inequalities, which delimit the five-variable entropy region. This method adds copies of some of the random variables in generations. A significant reduction in computational complexity, achieved through theoretical considerations and by harnessing the inherent symmetries, allowed us to calculate all five-variable non-Shannon inequalities provided by the first nine generations. Based on the results, we define two infinite collections of such inequalities and prove them to be entropy inequalities. We investigate downward-closed subsets of non-negative lattice points that parameterize these collections, and based on this, we develop an algorithm to enumerate all extremal inequalities. The discovered set of entropy inequalities is conjectured to characterize the applied method completely.
Given n (discrete or continuous) random variables Xi, the (2n- 1)-dimensional vector obtained by evaluating the joint entropy of all non-empty subsets of {X1,hellip, Xn} is called an entropic vector. Determining the region of entropic vectors is an important open problem in information theory. Recently, Chan has shown that the entropy regions for discrete and continuous random variables, though different, can be determined from one another. An important class of continuous random variables are those that are vector-valued and jointly Gaussian. It is known that Gaussian random variables violate the Ingleton bound, which many random variables such as those obtained from linear codes over finite fields do satisfy, and they also achieve certain non-Shannon inequalities. In this paper we give a full characterization of the entropy region for three jointly-Gaussian vector-valued random variables and, rather surprisingly, show that the region is strictly smaller than the entropy region for three arbitrary random variables. However, we also show the following result. For any given entropic vector h isin R7, there exists a thetas* > 0, such that for all thetas ges thetas*, the vector 1/thetas h can be generated by three vector-valued jointly Gaussian random variables. This implies that for three random variables the region of entropic vectors can be obtained by considering the cone generated by the space of Gaussian entropic vectors. It also suggests that studying Gaussian random variables for n ges 4 may be a fruitful approach to studying the space of entropic vectors for arbitrary n.
A marginal problem asks whether a given family of marginal distributions for some set of random variables arises from some joint distribution of these variables. Here, we point out that the existence of such a joint distribution imposes nontrivial conditions already on the level of Shannon entropies of the given marginals. These entropic inequalities are necessary (but not sufficient) criteria for the existence of a joint distribution. For every marginal problem, a list of such Shannon-type entropic inequalities can be calculated by Fourier-Motzkin elimination, and we offer a software interface to a Fourier-Motzkin solver for doing so. For the case that the hypergraph of given marginals is a cycle graph, we provide a complete analytic solution to the problem of classifying all relevant entropic inequalities, and use this result to bound the decay of correlations in stochastic processes. Furthermore, we show that Shannon-type inequalities for differential entropies are not relevant for continuous-variable marginal problems; non-Shannon-type inequalities are both in the discrete and in the continuous case. In contrast to other approaches, our general framework easily adapts to situations where one has additional (conditional) independence requirements on the joint distribution, as in the case of graphical models. We end with a list of open problems. A complementary article discusses applications to quantum nonlocality and contextuality.
A causal structure is a relationship between observed variables that in general restricts the possible correlations between them. This relationship can be mediated by unobserved systems, modelled by random variables in the classical case or joint quantum systems in the quantum case. One way to differentiate between the correlations realisable by two different causal structures is to use entropy vectors, i.e., vectors whose components correspond to the entropies of each subset of the observed variables. To date, the starting point for deriving entropic constraints within causal structures are the so-called Shannon inequalities (positivity of entropy, conditional entropy and conditional mutual information). In the present work we investigate what happens when non-Shannon entropic inequalities are included as well. We show that in general these lead to tighter outer approximations of the set of realisable entropy vectors and hence enable a sharper distinction of different causal structures. Since non-Shannon inequalities can only be applied amongst classical variables, it might be expected that their use enables an entropic distinction between classical and quantum causal structures. However, this remains an open question. We also introduce techniques for deriving inner approximations to the allowed sets of entropy vectors for a given causal structure. These are useful for proving tightness of outer approximations or for finding interesting regions of entropy space. We illustrate these techniques in several scenarios, including the triangle causal structure.