Information Inequalities for Joint Distributions, With Interpretations and Applications
By Mokshay M. Madiman, Prasad Tetali. 2008
144 citations recorded by the source corpus.
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 determinantal inequalities in matrix theory. A general inequality for relative entropies is also developed. Finally, revealing connections of the results to literature in economics, computer science, and physics are explored.
Subfields: Computational Mechanics, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mechanics
In Discrete Mathematics and Combinatorics
In Electrical and Electronic Engineering
Citations in the corpus
- On the entropy of sums (2008, methodology): “Fujishige [3] proved that h(s) = H(X s ) is a submodular set function (analogous to the conjecture on the supermodularity of entropy power), and Madiman and Tetali [1] proved that s∈C β s H(X s”
- Three tutorial lectures on entropy and counting (2014, unknown): “ number of Hamilton cycles in an n-vertex graph with minimum degree at least n=2. Madiman & Tetali, Information Inequalities for Joint Distributions, with Interpretations and Applications (2010) [46]: Develops generalizations of subadditivity, and gives applications to counting graph homomorphis”