Efficient Approximate Minimum Entropy Coupling of Multiple Probability Distributions

DOI10.1109/TIT.2021.3076986zbMATH Open1486.94040arXiv2006.07955OpenAlexW3158549335MaRDI QIDQ4958225

Cheuk Ting Li

Publication date: 7 September 2021

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Given a collection of probability distributions $p_1,ldots,p_m$, the minimum entropy coupling is the coupling $X_1,ldots,X_m$ ($X_{i}sim{p}_i$) with the smallest entropy $H(X_1,ldots,X_m)$. While this problem is known to be NP-hard, we present an efficient algorithm for computing a coupling with entropy within 2 bits from the optimal value. More precisely, we construct a coupling with entropy within 2 bits from the entropy of the greatest lower bound of $p_1,ldots,p_m$ with respect to majorization. This construction is also valid when the collection of distributions is infinite, and when the supports of the distributions are infinite. Potential applications of our results include random number generation, entropic causal inference, and functional representation of random variables.

Full work available at URL: https://arxiv.org/abs/2006.07955

Mathematics Subject Classification ID

Measures of information, entropy (94A17)

Related Items (1)

Multilevel aggregation of central server models: a minimum relative entropy approach

This page was built for publication: Efficient Approximate Minimum Entropy Coupling of Multiple Probability Distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958225)