Non-Shannon Information Inequalities in Four Random Variables

Abstract

Any unconstrained information inequality in three or fewer random variables can be written as a linear combination of instances of Shannon's inequality I(A;B|C) >= 0 . Such inequalities are sometimes referred to as "Shannon" inequalities. In 1998, Zhang and Yeung gave the first example of a "non-Shannon" information inequality in four variables. Their technique was to add two auxiliary variables with special properties and then apply Shannon inequalities to the enlarged list. Here we will show that the Zhang-Yeung inequality can actually be derived from just one auxiliary variable. Then we use their same basic technique of adding auxiliary variables to give many other non-Shannon inequalities in four variables. Our list includes the inequalities found by Xu, Wang, and Sun, but it is by no means exhaustive. Furthermore, some of the inequalities obtained may be superseded by stronger inequalities that have yet to be found. Indeed, we show that the Zhang-Yeung inequality is one of those that is superseded. We also present several infinite families of inequalities. This list includes some, but not all of the infinite families found by Matus. Then we will give a description of what additional information these inequalities tell us about entropy space. This will include a conjecture on the maximum possible failure of Ingleton's inequality. Finally, we will present an application of non-Shannon inequalities to network coding. We will demonstrate how these inequalities are useful in finding bounds on the information that can flow through a particular network called the Vamos network.

40 pages

Cited by in corpus (16)

• Inequalities for the Ranks of Quantum States
• The Quantum Entropy Cone of Stabiliser States
• Index Coding Capacity: How far can one go with only Shannon Inequalities?
• Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication
• Explicit Polyhedral Bounds on Network Coding Rate Regions via Entropy Function Region: Algorithms, Symmetry, and Computation
• How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma
• Measurement entropy in Generalized Non-Signalling Theory cannot detect bipartite non-locality
• On the Storage Cost of Private Information Retrieval
• Graph Guessing Games and non-Shannon Information Inequalities
• Using multiobjective optimization to map the entropy region of four random variables
• Guessing Games on Triangle-free Graphs
• On the Ingleton-Violations in Finite Groups
• Self-adhesivity in lattices of abstract conditional independence models
• Tropical Limits of Probability Spaces, Part I: The Intrinsic Kolmogorov-Sinai Distance and the Asymptotic Equipartition Property for Configurations
• The almost-entropic regions are not semialgebraic
• Common Information, Matroid Representation, and Secret Sharing for Matroid Ports