Finite-metric transport duality — Examples

If $a\ge b$, all entries of the displayed matrix are nonnegative, its row sums are $b+(a-b)=a$ and $1-a$, and its column sums are $b$ and $(a-b)+(1-a)=1-b$. Its cost is $\delta (a-b)$. If $b>a$, the second displayed matrix has nonnegative entries, row sums $a$ and $(b-a)+(1-b)=1-a$, column sums $a+(b-a)=b$ and $1-b$, and cost $\delta (b-a)$. Thus in either case it is a feasible coupling of cost $\delta \mathrm{\mid }a-b\mathrm{\mid }$.

If $a\ge b$, the vector $(0,-\delta )$ is normalized and satisfies the Lipschitz constraint with equality; its objective is $(b-a)(-\delta )=\delta (a-b)$. If $b>a$, the vector $(0,\delta )$ is normalized and feasible, and its objective is $(b-a)\delta =\delta (b-a)$. Thus the displayed potential has value $\delta \mathrm{\mid }a-b\mathrm{\mid }$ in either case.

By [F2], the optimal primal and dual values coincide. The feasible plan in step 1.1 gives an optimal primal value at most $\delta \mathrm{\mid }a-b\mathrm{\mid }$, while the feasible potential in step 1.2 gives an optimal dual value at least that number. Equality of the optima forces both displayed values to be optimal and gives $W_1(p,q)=\delta \mathrm{\mid }a-b\mathrm{\mid }$.

Write $r_i=p_i-q_i$ for $0\le i\le n$, set $R_{-1}=0$ and $R_n=0$, and use ${\sum }_i{r}_i=0$ from [F3]. Then $r_i=R_i-R_{i-1}$ for every $i$, and expanding the finite sums gives ${\sum }_{i=0}^n{r}_i{f}_i={\sum }_{k=0}^{n-1}{R}_k(f_k-f_{k+1})$. For any feasible 1-Lipschitz vector, $\mathrm{\mid }{f}_k-f_{k+1}\mathrm{\mid }\le 1$, so each term is at most $\mathrm{\mid }{R}_k\mathrm{\mid }$ and the dual objective is at most ${\sum }_{k=0}^{n-1}\mathrm{\mid }{R}_k\mathrm{\mid }$.

The recursively defined potential has $\mathrm{\mid }{f}_{k+1}-f_k\mathrm{\mid }=\mathrm{\mid }\mathrm{sgn}(R_k)\mathrm{\mid }\le 1$ on each adjacent pair. For $i<j$, the triangle inequality on real absolute values gives $\mathrm{\mid }{f}_i-f_j\mathrm{\mid }\le {\sum }_{k=i}^{j-1}\mathrm{\mid }{f}_{k+1}-f_k\mathrm{\mid }\le j-i=d(x_i,x_j)$; also $f_0=0$. Thus it is feasible. Its objective, by step 1.1, is ${\sum }_{k=0}^{n-1}{R}_k\mathrm{sgn}(R_k)={\sum }_{k=0}^{n-1}\mathrm{\mid }{R}_k\mathrm{\mid }$, so it attains the dual maximum.

The dual maximum is therefore ${\sum }_{k=0}^{n-1}\mathrm{\mid }{R}_k\mathrm{\mid }$ by steps 1.1–2.1. Applying [F2] identifies this value with $W_1(p,q)$ and proves the formula and the asserted attaining potential.

The specified distances are symmetric, vanish exactly on equal points, and are positive for distinct points. For the three distinct points, the triangle inequalities are $2\le 1+1$, $1\le 2+1$, and $1\le 1+2$; when a point repeats, each inequality is $0\le d+d$ or $d\le d+0$. Thus this is a metric. The displayed matrix is nonnegative, has row sums $(1\mathrm{/}2,0,1\mathrm{/}2)$ and column sums $(0,1,0)$, and has cost $(1\mathrm{/}2)\cdot 1+(1\mathrm{/}2)\cdot 1=1$.

The vector $f=(0,-1,0)$ has $f_1=0$. Its pairwise differences have magnitudes $1,1,0$, bounded respectively by distances $1,1,2$. Its objective is $(1\mathrm{/}2)\cdot 0-1\cdot (-1)+(1\mathrm{/}2)\cdot 0=1$.

The feasible plan and potential in steps 1.1 and 1.2 have the same value. By [F1], the primal optimum is at most the plan cost, the dual optimum is at least the potential value, and the two optima are equal; hence both are attained with value $1$. The positive entries are ${\pi }_{12}={\pi }_{32}=1\mathrm{/}2$, and they satisfy $f_1-f_2=d(x_1,x_2)=1$ and $f_3-f_2=d(x_3,x_2)=1$, as complementary slackness requires.