Information Inequalities for Joint Distributions, with Interpretations and Applications
arXiv:0901.0044 · doi:10.1109/TIT.2010.2046253
Abstract
Upper and lower bounds are obtained for the joint entropy of a collection of random variables in terms of an arbitrary collection of subset joint entropies. These inequalities generalize Shannon's chain rule for entropy as well as inequalities of Han, Fujishige and Shearer. A duality between the upper and lower bounds for joint entropy is developed. All of these results are shown to be special cases of general, new results for submodular functions-- thus, the inequalities presented constitute a richly structured class of Shannon-type inequalities. The new inequalities are applied to obtain new results in combinatorics, such as bounds on the number of independent sets in an arbitrary graph and the number of zero-error source-channel codes, as well as new determinantal inequalities in matrix theory. A new inequality for relative entropies is also developed, along with interpretations in terms of hypothesis testing. Finally, revealing connections of the results to literature in economics, computer science, and physics are explored.
15 pages, 1 figure. Originally submitted to the IEEE Transactions on Information Theory in May 2007, the current version incorporates reviewer comments including elimination of an error
References in corpus (2)
Cited by in corpus (38)
- Entropic Inequalities and Marginal Problems
- Common Information and Secret Key Capacity
- Entropy bounds on abelian groups and the Ruzsa divergence
- On the Public Communication Needed to Achieve SK Capacity in the Multiterminal Source Model
- Entropy and set cardinality inequalities for partition-determined functions
- Cores of Cooperative Games in Information Theory
- Three tutorial lectures on entropy and counting
- Symmetrical Multilevel Diversity Coding and Subset Entropy Inequalities
- Block factorization of the relative entropy via spatial mixing
- Combinatorial Entropy Power Inequalities: A Preliminary Study of the Stam region
- Majorization and Rényi Entropy Inequalities via Sperner Theory
- Information-Theoretic Perspectives on Brascamp-Lieb Inequality and Its Reverse
- The number of independent sets in an irregular graph
- Do Minkowski averages get progressively more convex?
- On the volume of the Minkowski sum of zonoids
- Tightening Fractional Covering Upper Bounds on the Partition Function for High-Order Region Graphs
- Information-theoretic inference of common ancestors
- Distributed Function Computation with Confidentiality
- Entropies of weighted sums in cyclic groups and an application to polar codes
- Volumes of subset Minkowski sums and the Lyusternik region
- Measuring Dependence with Matrix-based Entropy Functional
- Entropy production in nonlinear recombination models
- Information Inequalities via Submodularity and a Problem in Extremal Graph Theory
- An entropy inequality for symmetric random variables
- Counting colorings of a regular graph
- The communication complexity of achieving SK capacity in a class of PIN models
- Dual Loomis-Whitney inequalities via information theory
- Concentration of measure, classification of submeasures, and dynamics of
- On the Optimality of Secret Key Agreement via Omniscience
- Minimum Entropy Submodular Optimization (and Fairness in Cooperative Games)
- How Many Queries Will Resolve Common Randomness?
- On H-Intersecting Graph Families and Counting of Homomorphisms
- Blending Learning and Inference in Structured Prediction
- Matchings and Independent Sets of a Fixed Size in Regular Graphs
- Secret Key Capacity For Multipleaccess Channel With Public Feedback
- A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs
- Maximizing H-colorings of a regular graph
- Performance Bounds on a Wiretap Network with Arbitrary Wiretap Sets