# How to Find a Joint Probability Distribution of Minimum Entropy (almost) given the Marginals

arXiv: https://arxiv.org/abs/1701.05243 · HTML: https://mlsanity.com/paper/1701.05243/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jan 2017.

## Built on by (most cited first, 6 of 6)

- [Multimodal Learning Without Labeled Multimodal Data: Guarantees and Applications](https://mlsanity.com/paper/2306.04539/) (2023)
- [Entropic Causal Inference: Identifiability and Finite Sample Results](https://mlsanity.com/paper/2101.03501/) (2021)
- [Minimum Entropy Coupling with Bottleneck](https://mlsanity.com/paper/2410.21666/) (2024)
- [Entropic Causal Inference: Graph Identifiability](https://mlsanity.com/paper/2509.16463/) (2025)
- [Learning to Match Unpaired Data with Minimum Entropy Coupling](https://mlsanity.com/paper/2503.08501/) (2025)
- [Learning from Totally Unpaired Data via Minimum Conditional Entropy Coupling](https://mlsanity.com/paper/2605.16229/) (2026)

## Abstract (arXiv)

Given two discrete random variables X and Y, with probability distributions bf p =(p1, ldots , pn) and bf q=(q1, ldots , qm), respectively, denote by cal C(bf p, bf q) the set of all couplings of bf p and bf q, that is, the set of all bivariate probability distributions that have bf p and bf q as marginals. In this paper, we study the problem of finding the joint probability distribution in cal C(bf p, bf q) of minimum entropy (equivalently, the joint probability distribution that maximizes the mutual information between X and Y), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in cal C(bf p, bf q) with entropy exceeding the minimum possible by at most 1, thus providing an approximation algorithm with additive approximation factor of 1. Leveraging on this algorithm, we extend our result to the problem of finding a minimum--entropy joint distribution of arbitrary k≥ 2 discrete random variables X1, ldots , Xk, consistent with the known k marginal distributions of X1, ldots , Xk. In this case, our approximation algorithm has an additive approximation factor of log k. We also discuss some related applications of our findings.