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

Use the Lipschitz constant convention $\Vert f{\Vert }_L={\sup }_{x\ne y}|f(x)-f(y)|/d(x,y)$ in the final quantity; it is a seminorm, with constants having value zero. Also interpret the coupling space as $\mathcal{P}(X\times X)$. The printed $\mathcal{P}(X,Y)$ has an undefined $Y$. The third quantity has a duplicated printed label; it is placed in part iii here, with the fourth in part iv.

First prove weak optimal transport duality. For any feasible continuous pair $f,g$ and any coupling of probability distributions $\pi$ with marginals $P,Q$,Taking the supremum over pairs and infimum over couplings gives $m_d(P,Q)\le W(P,Q)$. These quantities are finite: $P\otimes Q$ is a coupling and the continuous cost $d$ is bounded on the compact metric space $X\times X$. The zero pair is feasible, so $0\le m_d\le W\le \mathrm{diam}X$.

The reverse inequality is established in part ii by finite approximation and a proof of the required finite linear programming duality. Parts iii and iv then show that all the dual formulations agree.

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.

Since Lipschitz functions are continuous, the feasible class here is smaller, giving $m_L\le m_d$. To prove the reverse inequality, take any continuous feasible pair $f,g$ and perform Lipschitz regularization of transport potentials:The minimum exists by compactness. For every $x,x^{\prime }$ the triangle inequality gives $h(x)\le d(x,x^{\prime })+h(x^{\prime })$; interchanging $x,x^{\prime }$ proves $|h(x)-h(x^{\prime })|\le d(x,x^{\prime })$. Thus $h$ has Lipschitz constant at most $1$.

The original constraint yields $f(x)\le h(x)$, and evaluating the minimum at $y=x$ gives $h(x)\le -g(x)$. Moreover, $h(x)-h(y)\le d(x,y)$, so $(h,-h)$ is a feasible Lipschitz pair withTaking the supremum over the original continuous pairs proves $m_L(P,Q)=m_d(P,Q)=W(P,Q)$. Notice that this is an exact regularization, with no density or approximation assumption about the initial pair.

Every function $h$ with Lipschitz constant at most $1$ yields a feasible pair $(h,-h)$, and replacing $h$ by $-h$ reverses the objective. HenceConversely, the Lipschitz regularization of transport potentials in part iii dominates every feasible pair by $(h,-h)$ with $\Vert h{\Vert }_L\le 1$, so $m_L\le \gamma$. Together with the preceding parts this proves the Kantorovich–Rubinstein theorem here in all four requested forms:The seminorm convention is essential. If instead $\Vert h{\Vert }_L$ meant $\Vert h{\Vert }_{\infty }+\mathrm{Lip}(h)$, the equality would fail: on a two-point space at distance $2$, with point masses at the two different points, $W=2$ whereas the latter unit-ball supremum is $1$. Indeed, an oscillation $a$ needs supremum norm at least $a/2$ and Lipschitz constant $a/2$, so the sum norm bounds $a$ by $1$, attained by values $-1/2,1/2$. This distinguishes the Lipschitz seminorm used above from a full bounded-Lipschitz norm.