On the Entropy of Couplings

Abstract

In this paper, some general properties of Shannon information measures are investigated over sets of probability distributions with restricted marginals. Certain optimization problems associated with these functionals are shown to be NP-hard, and their special cases are found to be essentially information-theoretic restatements of well-known computational problems, such as the SUBSET SUM and the 3-PARTITION. The notion of minimum entropy coupling is introduced and its relevance is demonstrated in information-theoretic, computational, and statistical contexts. Finally, a family of pseudometrics (on the space of discrete probability distributions) defined by these couplings is studied, in particular their relation to the total variation distance, and a new characterization of the conditional entropy is given.

18 pages (single-column). Compared to v1, the material is reorganized, Section IV.C is removed (the results will possible appear elsewhere), Propositions 3.2 and 3.7 are added. Accepted for publication in Information and Computation

References in corpus (5)

• Entropy Bounds for Discrete Random Variables via Maximal Coupling
• On the Hardness of Entropy Minimization and Related Problems
• Finding the Maximizers of the Information Divergence from an Exponential Family
• Minimum Entropy Combinatorial Optimization Problems
• Some Properties of Rényi Entropy over Countably Infinite Alphabets

Cited by in corpus (7)

• A Novel Approach to the Partial Information Decomposition
• Efficient Approximate Minimum Entropy Coupling of Multiple Probability Distributions
• Entropy and Diversity: The Axiomatic Approach
• Hardness and Approximability of Dimension Reduction on the Probability Simplex
• Asymptotic Coupling and Its Applications in Information Theory
• Observational nonidentifiability, generalized likelihood and free energy
• Information-Geometric Equivalence of Transportation Polytopes