Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 9 / 5 / ii / Solution

Fix $\epsilon >0$ and a finite epsilon-net $x_1,\dots ,x_N$ in $X$. Choose a Borel map $r:X\to \{x_1,\dots ,x_N\}$ with $d(x,r(x))\le \epsilon$, for example the nearest point with ties broken by index. Its cells $A_i$ give discrete probability measures with masses $p_i=P(A_i)$ and $q_i=Q(A_i)$. LetThe feasible set is nonempty and compact, so the minimum exists. Pushing any coupling forward by $(r,r)$ changes its cost by at most $2\epsilon$, hence $W_{\epsilon }\le W+2\epsilon$. Conversely, lift a discrete coupling by the measureTerms with zero row or column masses vanish. This lift has marginals $P,Q$, and its cost differs by at most $2\epsilon$. Therefore

Here is the finite linear programming duality proof. Write $d_{ij}=d(x_i,x_j)$ and consider the convex coneIt is closed and finitely generated. One elementary justification of closedness is to reduce each nonnegative representation to linearly independent generators, eliminating a coefficient along any linear dependence; after choosing a subsequence using the same subset of generators, their independent coordinates have bounded, convergent coefficients whenever the represented vectors converge. For $\eta >0$, the point $(p,q,W_{\epsilon }-\eta )$ lies outside $C$. Separation from this closed convex cone gives coefficients $(a,b,\tau )$ withIf $\tau =0$, summing the middle inequalities against any feasible $\pi$ contradicts the last one. Thus $\tau >0$, and $f_i=-a_i/\tau$, $g_j=-b_j/\tau$ obey $f_i+g_j\le d_{ij}$ with dual objective greater than $W_{\epsilon }-\eta$. The weak inequality already proved gives the reverse bound. Letting $\eta \downarrow 0$ proves finite strong duality.

Reduce this discrete dual to a single Lipschitz function. For a feasible pair put ${\varphi }_i={\min }_j(d_{ij}-g_j)$. The triangle inequality gives $|{\varphi }_i-{\varphi }_l|\le d_{il}$, while $f_i\le {\varphi }_i$ and $g_i\le -{\varphi }_i$. ConsequentlyConversely, any $1$-Lipschitz vector $\varphi$ gives a feasible pair $(\varphi ,-\varphi )$. Adding a constant leaves its objective unchanged, so impose ${\varphi }_1=0$. The resulting feasible set is compact, and its maximum is $W_{\epsilon }$.

For a maximizing vector, the McShane extension theorem has the following explicit proof in this situation. DefineThe triangle inequality proves that this extension is $1$-Lipschitz, and the discrete Lipschitz condition makes $\varphi (x_i)={\varphi }_i$. Thus $(\varphi ,-\varphi )$ is a continuous feasible pair. Because $|\varphi (x)-\varphi (r(x))|\le \epsilon$,Letting $\epsilon \downarrow 0$, together with part i, proves $m_d(P,Q)=W(P,Q)$. The infimum defining $W$ is also attained: the set of couplings is a closed subset of the compact space of probability measures on $X\times X$, and integrating the continuous cost is continuous for the weak-star topology.