Efficient Approximate Minimum Entropy Coupling of Multiple Probability Distributions
Cheuk Ting Li · IEEE Transactions on Information Theory · 2021
Given a collection of probability distributions p1,⋯,pm, the minimum entropy coupling is the coupling X1,⋯,Xm( Xi~ pi) with the smallest entropy H(X1,⋯,Xm). 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 p1,⋯,pmwith 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.