Finite space Kantorovich problem with an MCMC of table moves (Q2044325)

The paper is concerned with the optimal transport problem in the formulation of Kantorovich for finite, discrete probability distributions. In this problem, a finite sample space \(X\) of size \(n\) and a cost function \({c: X \times X \to \mathbb{R}}\) are given. The task is to find for two given marginal distributions \(\mu\) and \(\nu\) on \(X\) a joint distribution \(\gamma\) on \(X \times X\) having these two prescribed marginals and minimal average cost with respect to~\(c\). Distributions \(\gamma\) with prescribed marginals are called \textit{couplings} or \textit{transport plans}. The set of all couplings of \(\mu\) and \(\nu\) is a polytope inside the set of \(n \times n\) matrices and the average cost is a linear functional, which ensures the existence of an optimal transport~plan. The coupling polytope is studied via the associated linear space of \textit{moves}: \(n \times n\) matrices which, when added to a coupling, produce another coupling. A basis of this vector space consisting of \textit{basic moves} is described. It is shown that positive linear combinations of basic moves connect any two couplings and an optimality criterion in terms of basic moves is derived. An extension to tri-variate distributions is briefly presented. Based on these results about moves between couplings, the authors develop a Markov Chain Monte Carlo algorithm which walks from the independent coupling \(\mu \otimes \nu\) as a universal starting point towards an optimal transport plan.