论文标题
有效的多个概率分布的最小熵耦合
Efficient Approximate Minimum Entropy Coupling of Multiple Probability Distributions
论文作者
论文摘要
给定概率分布的集合$ p_ {1}，\ ldots，p_ {m} $，最小熵耦合是耦合$ x_ {1}，\ ldots，x_ {m} $（$ x_ {$ x_ {i} $ h（x_ {1}，\ ldots，x_ {m}）$。虽然已知此问题是NP-HARD，但我们提出了一种有效的算法，用于计算与最佳值2位以内的熵耦合。更确切地说，我们从$ p_ {1}的最大下限的熵构建了一个与熵的耦合，\ ldots，p_ {m} $相对于大型化。当分布的收集是无限的，并且分布的支撑是无限的时，这种构建也是有效的。我们结果的潜在应用包括随机数生成，熵因果推断和随机变量的功能表示。
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.
