# Minimum--Entropy Couplings and their Applications

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jan 2019.

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

- [Perfectly Secure Steganography Using Minimum Entropy Coupling](https://mlsanity.com/paper/2210.14889/) (2022)
- [Communicating via Markov Decision Processes](https://mlsanity.com/paper/2107.08295/) (2021)
- [Towards Semantic Communication Protocols for 6G: From Protocol Learning to Language-Oriented Approaches](https://mlsanity.com/paper/2310.09506/) (2023)
- [Minimum Entropy Coupling with Bottleneck](https://mlsanity.com/paper/2410.21666/) (2024)
- [Learning to Match Unpaired Data with Minimum Entropy Coupling](https://mlsanity.com/paper/2503.08501/) (2025)
- [Provable Secure Steganography Based on Adaptive Dynamic Sampling](https://mlsanity.com/paper/2504.12579/) (2025)
- [Cross-Domain Lossy Compression via Constrained Minimum Entropy Coupling](https://mlsanity.com/paper/2605.09833/) (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 a joint probability distribution in cal C(bf p, bf q) of minimum entropy (equivalently, a coupling 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 at most by 1 bit, thus providing an approximation algorithm with an additive gap of at most 1 bit. 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 the individual random variables X1, ldots , Xk. In this case, our algorithm has an  additive gap of at most log k from optimum. We also discuss several related applications of our findings and extensions of our results to entropies different from the Shannon entropy.