Optimal transport compares two distributions by placing them on a common probability space. Before a cost is minimized, one must understand the three operations that make this possible: moving a measure through a map, joining two measures by a coupling, and composing couplings through a common marginal.
Probability measures on Polish spaces
Throughout the note, \(X\) and \(Y\) are Polish spaces with their Borel \(\sigma\)-fields. This assumption is broad enough for Euclidean spaces, separable Banach spaces, manifolds, path spaces, and countable discrete spaces, while still providing tightness and regular conditional probabilities.
Definition. Write \(\mathcal P(X)\) for the Borel probability measures on \(X\). If \(d_X\) is a complete compatible metric and \(p\ge1\), define \[ \mathcal P_p(X)=\left\{\mu\in\mathcal P(X):\int_X d_X(x,x_0)^p\,\mathrm{d}\mu(x)<\infty\right\}. \] The definition does not depend on the base point \(x_0\), because \(d_X(x,x_1)^p\le 2^{p-1}\{d_X(x,x_0)^p+d_X(x_0,x_1)^p\}\).
Weak convergence \(\mu_n\Rightarrow\mu\) means \(\int f\,\mathrm{d}\mu_n\to\int f\,\mathrm{d}\mu\) for every bounded continuous \(f\). Moment conditions will later strengthen weak convergence into Wasserstein convergence.
Pushforward measures
Definition. If \(T:X\to Y\) is Borel measurable and \(\mu\in\mathcal P(X)\), the pushforward \(T_\#\mu\in\mathcal P(Y)\) is \[ (T_\#\mu)(B)=\mu(T^{-1}(B)),\qquad B\in\mathcal B(Y). \] Equivalently, \(T_\#\mu\) is the law of \(T(U)\) whenever \(U\sim\mu\).
Change-of-variables identity. For every nonnegative Borel function \(g:Y\to[0,\infty]\), and for every \(T_\#\mu\)-integrable \(g\), \[ \int_Y g(y)\,\mathrm{d}(T_\#\mu)(y)=\int_X g(T(x))\,\mathrm{d}\mu(x). \]
Proof. The identity follows from the definition when \(g=\mathbf 1_B\). Linearity gives it for nonnegative simple functions. If \(g_n\uparrow g\) are simple, the monotone convergence theorem on both sides gives the nonnegative case. Applying the result to the positive and negative parts gives the integrable case.
Example. If \(X=Y=\mathbb R^d\), \(T(x)=Ax+b\), and \(U\sim N(m,\Sigma)\), then \(T_\#N(m,\Sigma)=N(Am+b,A\Sigma A^{\mathsf T})\). If \(\mu\) has density \(f\) and \(T\) is a \(C^1\)-diffeomorphism, then \(T_\#\mu\) has density \(g(y)=f(T^{-1}y)|\det DT(T^{-1}y)|^{-1}\). The Monge--Ampère equation will arise by applying this formula to \(T=\nabla\varphi\).
Couplings and transport plans
Definition. A coupling of \(\mu\in\mathcal P(X)\) and \(\nu\in\mathcal P(Y)\) is a probability measure \(\pi\in\mathcal P(X\times Y)\) whose marginals are \(\mu\) and \(\nu\): \[ (\operatorname{pr}_X)_\#\pi=\mu, \qquad (\operatorname{pr}_Y)_\#\pi=\nu. \] The set of all such measures is denoted \(\Pi(\mu,\nu)\). In optimal transport, a coupling is also called a transport plan.
The set \(\Pi(\mu,\nu)\) is never empty because it contains the independent coupling \(\mu\otimes\nu\). A coupling records dependence while leaving the two marginal laws fixed. Thus choosing a transport plan is exactly choosing which source points are paired with which target points.
Proposition. If \(X,Y\) are Polish, then \(\Pi(\mu,\nu)\) is convex and tight. It is also closed under weak convergence; consequently it is weakly compact.
Proof. Convexity follows because the marginal maps are linear. Given \(\varepsilon>0\), tightness of \(\mu\) and \(\nu\) provides compact sets \(K_X,K_Y\) with \(\mu(K_X)\ge1-\varepsilon/2\) and \(\nu(K_Y)\ge1-\varepsilon/2\). Every \(\pi\in\Pi(\mu,\nu)\) then satisfies \[ \pi(K_X\times K_Y) \ge 1-\pi(K_X^c\times Y)-\pi(X\times K_Y^c) \ge1-\varepsilon. \] Hence the family is tight. If \(\pi_n\Rightarrow\pi\), continuity of the projections gives \((\operatorname{pr}_X)_\#\pi_n\Rightarrow(\operatorname{pr}_X)_\#\pi\), so the first marginal of \(\pi\) is \(\mu\); similarly the second is \(\nu\). Prokhorov's theorem now yields compactness.
Maps, kernels, and disintegration
A map sends all mass located at \(x\) to one point. A general plan may split that mass among several destinations. Disintegration makes this distinction exact.
Disintegration theorem. For every \(\pi\in\Pi(\mu,\nu)\), there exists a \(\mu\)-almost surely unique measurable probability kernel \(x\mapsto\pi_x\in\mathcal P(Y)\) such that \[ \pi(\mathrm{d}x,\mathrm{d}y)=\mu(\mathrm{d}x)\pi_x(\mathrm{d}y), \qquad \nu(B)=\int_X\pi_x(B)\,\mathrm{d}\mu(x). \] Moreover, \(\pi\) is induced by a measurable map \(T:X\to Y\), meaning \(\pi=(\operatorname{id},T)_\#\mu\), if and only if \(\pi_x=\delta_{T(x)}\) for \(\mu\)-almost every \(x\).
The kernel \(\pi_x\) is the conditional law of the destination given the source \(x\). Deterministic plans are therefore precisely the couplings whose conditional laws are Dirac masses.
Example. Let \(\mu=\delta_0\) and \(\nu=\tfrac12(\delta_{-1}+\delta_1)\). There is one coupling, \(\pi=\delta_0\otimes\nu\), and its conditional law at \(0\) is \(\nu\). No map \(T\) can satisfy \(T_\#\mu=\nu\), because the image of a Dirac mass under a map is another Dirac mass. This is the simplest reason the Kantorovich relaxation is needed.
The gluing lemma
The triangle inequality for Wasserstein distance and the composition of stochastic transports both rely on the following construction.
Gluing lemma. Let \(\pi_{12}\in\Pi(\mu_1,\mu_2)\) and \(\pi_{23}\in\Pi(\mu_2,\mu_3)\) on Polish spaces \(X_1,X_2,X_3\). There exists \(\gamma\in\mathcal P(X_1\times X_2\times X_3)\) whose \((1,2)\)-marginal is \(\pi_{12}\) and whose \((2,3)\)-marginal is \(\pi_{23}\).
Proof. Disintegrate the two plans over their common marginal: \[ \pi_{12}(\mathrm{d}x_1,\mathrm{d}x_2) =\mu_2(\mathrm{d}x_2)K_{21}(x_2,\mathrm{d}x_1), \quad \pi_{23}(\mathrm{d}x_2,\mathrm{d}x_3) =\mu_2(\mathrm{d}x_2)K_{23}(x_2,\mathrm{d}x_3). \] Define \[ \gamma(\mathrm{d}x_1,\mathrm{d}x_2,\mathrm{d}x_3) =\mu_2(\mathrm{d}x_2)K_{21}(x_2,\mathrm{d}x_1)K_{23}(x_2,\mathrm{d}x_3). \] Integrating out \(x_3\) gives \(\pi_{12}\), and integrating out \(x_1\) gives \(\pi_{23}\). Thus the two pairwise couplings can be realized simultaneously, conditionally independently given \(x_2\).
A finite coupling polytope
Example. If \(X=\{x_1,x_2\}\), \(Y=\{y_1,y_2\}\), \(\mu=(a,1-a)\), and \(\nu=(b,1-b)\), every coupling has matrix \[ P(t)= \begin{pmatrix} t & a-\ b-t & 1-a-b+t \end{pmatrix}, \qquad \max(0,a+b-1)\le t\le\min(a,b). \] The interval of admissible \(t\)'s is the two-by-two transport polytope. A linear transport cost selects one of its endpoints unless the cost is parallel to the interval. This finite picture already contains convexity, nonuniqueness, and the distinction between marginals and dependence.