An Explicit Description of Extreme Points of the Set of Couplings with Given Marginals: with Application to Minimum-Entropy Coupling Problems

Given probability distributions $\mathbf{p}=(p_1,p_2,\dots ,p_m)$ and $\mathbf{q}=(q_1,q_2,\dots ,q_n)$ with $m,n\ge 2$, denote by $\mathcal{C}(\mathbf{p},\mathbf{q})$ the set of all couplings of $\mathbf{p},\mathbf{q}$, a convex subset of ${\mathbb{R}}^{mn}$. Denote by ${\mathcal{C}}_e(\mathbf{p},\mathbf{q})$ the finite set of all extreme points of $\mathcal{C}(\mathbf{p},\mathbf{q})$. It is well known that, as a strictly concave function, the Shannan entropy $H$ on $\mathcal{C}(\mathbf{p},\mathbf{q})$ takes its minimal value in ${\mathcal{C}}_e(\mathbf{p},\mathbf{q})$. In this paper, first, the detailed structure of ${\mathcal{C}}_e(\mathbf{p},\mathbf{q})$ is well specified and all extreme points are enumerated by a special algorithm. As an application, the exact solution of the minimum-entropy coupling problem is obtained. Second, it is proved that for any strict Schur-concave function $\mathrm{\Psi }$ on $\mathcal{C}(\mathbf{p},\mathbf{q})$, $\mathrm{\Psi }$ also takes its minimal value on ${\mathcal{C}}_e(\mathbf{p},\mathbf{q})$. As an application, the exact solution of the minimum-entropy coupling problem is obtained for $(\mathrm{\Phi },\mathrm{\hslash })$-entropy, a large class of entropy including Shannon entropy, Rényi entropy and Tsallis entropy etc. Finally, all the above are generalized to multi-marginal case.