Proof of The Wasserstein Distance between Two Probability Measures Carried by a Finite Set is Bounded by the Squared Diameter Times the Total Variation of the Masses

Each result cited is universally quantified over the data in its own statement. Throughout, $d=n$ in the results on couplings, which is allowed since $1\le n$; sums $\sum_{i}$ run over $i\in[M]$, and $M\ge1$, so the index $1$ exists.

Step 1 (the masses). For $i\in[M]$ the singleton $\{z_{i}\}$ is Borel by Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §finite-sets. Put $a_{i}=\rho(\{z_{i}\})$ and $b_{i}=\rho'(\{z_{i}\})$; these are real numbers with $0\le a_{i}\le1$ and $0\le b_{i}\le1$, since a measure takes values in $[0,\infty]$ (Measure, Measure Space, and Probability Measure) and $\rho(\{z_{i}\})\le\rho(\mathbb{R}^{n})=1$ by claim 2 of Basic Properties of a Measure, likewise for $\rho'$. By Convex Combinations of Probability Measures on Euclidean Space, and Finitely Supported Probability Measures as Combinations of Dirac Measures §finite-support,

the two representations being the convex combinations of Convex Combinations of Probability Measures on Euclidean Space, and Finitely Supported Probability Measures as Combinations of Dirac Measures §combination. For each $i$, claim 9 of Elementary Order Arithmetic in an Ordered Field gives $m_{i}\in\mathbb{R}$ with $m_{i}\le a_{i}$, $m_{i}\le b_{i}$ and $m_{i}\in\{a_{i},b_{i}\}$; in particular $0\le m_{i}$. Put $u_{i}=a_{i}-m_{i}$ and $v_{i}=b_{i}-m_{i}$, which are nonnegative by claim 3 of Elementary Arithmetic in an Ordered Field, and note $a_{i}-b_{i}=u_{i}-v_{i}$. If $m_{i}=a_{i}$ then $u_{i}=0$ and $a_{i}-b_{i}=-v_{i}$, so $|a_{i}-b_{i}|=|v_{i}|=v_{i}$ by claim 2 of Properties of the Absolute Value in an Ordered Field and the definition of the absolute value (as $0\le v_{i}$); if $m_{i}=b_{i}$ then $v_{i}=0$ and $|a_{i}-b_{i}|=|u_{i}|=u_{i}$. In both cases

Put $s=\sum_{i}m_{i}$, $t=\sum_{i}u_{i}$ and $t'=\sum_{i}v_{i}$, all nonnegative by claim 5 of Properties of Finite Sums. Since $a_{i}=m_{i}+u_{i}$ and $b_{i}=m_{i}+v_{i}$, additivity (claim 2 of Properties of Finite Sums) gives $1=s+t$ and $1=s+t'$, hence $t'=t$, and then (1) and additivity give

Step 2 (finite second moments). The map $y\mapsto\lVert y\rVert^{2}$ is a nonnegative Borel function on $\mathbb{R}^{n}$ by Probability Measures on Euclidean Space and Random Vectors: Standing Notation §pairs, and its integral against $\delta_{z_{i}}$ is the real number $\lVert z_{i}\rVert^{2}$ by Dirac Measures on Euclidean Space: Probability Measure, Integrals, Push-Forwards and the Coupling of Two Dirac Measures §integral. By the integral identity of Convex Combinations of Probability Measures on Euclidean Space, and Finitely Supported Probability Measures as Combinations of Dirac Measures §combination applied to the representation of $\rho$ in Step 1, the second moment is $M_{2}(\rho)=\int_{\mathbb{R}^{n}}\lVert y\rVert^{2}\,\rho(dy)=\sum_{i}a_{i}\lVert z_{i}\rVert^{2}$, a real number; so $\rho\in\mathcal{P}_{2}(\mathbb{R}^{n})$ by The Second Moment of a Probability Measure on Euclidean Space and the Probability Measures with Finite Second Moment §space. The same argument with the $b_{i}$ gives $\rho'\in\mathcal{P}_{2}(\mathbb{R}^{n})$. This is the first assertion.

Step 3 (three auxiliary probability measures). Each $\delta_{z_{i}}$ lies in $\mathcal{P}(\mathbb{R}^{n})$ by Dirac Measures on Euclidean Space: Probability Measure, Integrals, Push-Forwards and the Coupling of Two Dirac Measures §measure. If $0<s$, let $\theta=\sum_{i}(s^{-1}m_{i})\,\delta_{z_{i}}$: here $0<s^{-1}$ by claim 7 of Elementary Order Arithmetic in an Ordered Field, so each coefficient is nonnegative by claim 5 of Elementary Arithmetic in an Ordered Field, and the coefficients sum to $s^{-1}s=1$ by claim 3 of Properties of Finite Sums; hence $\theta\in\mathcal{P}(\mathbb{R}^{n})$ by Convex Combinations of Probability Measures on Euclidean Space, and Finitely Supported Probability Measures as Combinations of Dirac Measures §combination. If $s=0$, let $\theta=\rho$. In the same way, if $0<t$ let $\alpha_{1}=\sum_{i}(t^{-1}u_{i})\,\delta_{z_{i}}$ and $\alpha_{2}=\sum_{i}(t^{-1}v_{i})\,\delta_{z_{i}}$ (the coefficients of $\alpha_{2}$ sum to $t^{-1}t'=1$ as $t'=t$), and if $t=0$ let $\alpha_{1}=\rho$ and $\alpha_{2}=\rho'$; in every case $\theta,\alpha_{1},\alpha_{2}\in\mathcal{P}(\mathbb{R}^{n})$. We claim that for every $A\in\mathcal{B}(\mathbb{R}^{n})$

If $0<s$ the first identity is claim 3 of Properties of Finite Sums together with $s\,s^{-1}=1$. If $s=0$, then every $m_{i}$ is $0$ by the second part of claim 5 of Properties of Finite Sums, so both sides are $0$, by claim 1 of Zero Products and Elementary Identities in a Field and the second part of Finite Sums of Real Numbers: Nonnegativity, Domination by the Sum, and Limits §nonnegative. The other two identities follow in the same way from $t'=t$. Moreover

if $t=0$ this is the hypothesis on $\rho$ and $\rho'$; if $0<t$, then $z_{i}\in F$ gives $\delta_{z_{i}}(\mathbb{R}^{n}\setminus F)=0$ for every $i$, so $\alpha_{1}(\mathbb{R}^{n}\setminus F)$ and $\alpha_{2}(\mathbb{R}^{n}\setminus F)$ are sums of zeros, hence $0$ by claim 1 of Zero Products and Elementary Identities in a Field and Finite Sums of Real Numbers: Nonnegativity, Domination by the Sum, and Limits §nonnegative.

Step 4 (the coupling). Let $\pi_{0}=(\mathrm{id},\mathrm{id})_{\#}\theta$ and $\pi_{1}=\alpha_{1}\boxtimes\alpha_{2}$. By Couplings on Euclidean Space: Product Coupling, Swap, Finiteness of the Cost, Push-Forward Couplings, Modifying One Marginal, Quantisation, Gluing over a Finitely Supported Measure, and the Lipschitz Bound §pushforward, $\pi_{0}\in\Pi(\theta,\theta)$ and $I(\pi_{0})=0$; by Couplings on Euclidean Space: Product Coupling, Swap, Finiteness of the Cost, Push-Forward Couplings, Modifying One Marginal, Quantisation, Gluing over a Finitely Supported Measure, and the Lipschitz Bound §product, $\pi_{1}\in\Pi(\alpha_{1},\alpha_{2})$. Both are probability measures on $\mathbb{R}^{n+n}$. Apply Nonnegative Combinations of Two Finite Measures, and the Average of Two Couplings §combination to the measurable space $(\mathbb{R}^{n+n},\mathcal{B}(\mathbb{R}^{n+n}))$, its two finite measures $\pi_{0}$ and $\pi_{1}$, and the nonnegative coefficients $s$ and $t$: it yields a measure $\pi$ with $\pi(C)=s\,\pi_{0}(C)+t\,\pi_{1}(C)$ for every Borel $C$, and $\pi(\mathbb{R}^{n+n})=s+t=1$, so $\pi\in\mathcal{P}(\mathbb{R}^{n+n})$. For $A\in\mathcal{B}(\mathbb{R}^{n})$, the marginal conditions of Couplings of Two Probability Measures on Euclidean Space and Their Quadratic Cost §coupling for $\pi_{0}$ and $\pi_{1}$, then (3), additivity (claim 2 of Properties of Finite Sums) with distributivity in the field $\mathbb{R}$, and Step 1 give

and likewise $\pi(\mathrm{pr}_{2}^{-1}(A))=s\,\theta(A)+t\,\alpha_{2}(A)=\sum_{i}(m_{i}+v_{i})\,\delta_{z_{i}}(A)=\rho'(A)$. Hence $\pi\in\Pi(\rho,\rho')$ by Couplings of Two Probability Measures on Euclidean Space and Their Quadratic Cost §coupling.

Step 5 (the cost). Let $c(z)=\lVert\mathrm{pr}_{1}(z)-\mathrm{pr}_{2}(z)\rVert^{2}$, a nonnegative Borel function on $\mathbb{R}^{n+n}$ by Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §functions. By Couplings of Two Probability Measures on Euclidean Space and Their Quadratic Cost §cost and the integral identity of Nonnegative Combinations of Two Finite Measures, and the Average of Two Couplings §combination,

We show $J\le D^{2}$. First, $0\le\lVert z_{1}-z_{1}\rVert\le D$ by claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and the hypothesis on $D$, so $0\le D$ and, by claim 5 of Elementary Arithmetic in an Ordered Field with claim 1 of Zero Products and Elementary Identities in a Field, $0\le D^{2}$. For $j=1,2$ let $N_{j}=\mathrm{pr}_{j}^{-1}(\mathbb{R}^{n}\setminus F)$, a Borel set because $\mathbb{R}^{n}\setminus F$ is Borel (Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §finite-sets) and the projections are Borel (Pairs of Euclidean Points: Coordinate Projections, Pairings, the Product Measure on a Euclidean Space, Borel Norm Functions and Finite Sets §projections). By the marginal conditions for $\pi_{1}$ and (4), $\pi_{1}(N_{1})=\alpha_{1}(\mathbb{R}^{n}\setminus F)=0$ and $\pi_{1}(N_{2})=\alpha_{2}(\mathbb{R}^{n}\setminus F)=0$, so $N_{1}$ and $N_{2}$ are $\pi_{1}$-null by Null Set of a Measure, and $N_{1}\cup N_{2}$ is null by The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §null-union, applied to the sequence $N_{1},N_{2},\varnothing,\varnothing,\dots$ ($\varnothing$ is null as $\pi_{1}(\varnothing)=0$). If $z\notin N_{1}\cup N_{2}$, then $\mathrm{pr}_{1}(z),\mathrm{pr}_{2}(z)\in F$, so $\mathrm{pr}_{1}(z)=z_{i}$ and $\mathrm{pr}_{2}(z)=z_{j}$ for some $i,j\in[M]$; as $0\le\lVert z_{i}-z_{j}\rVert\le D$, claim 2 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field gives $c(z)=\lVert z_{i}-z_{j}\rVert^{2}\le D^{2}$. Thus the set of points where $c(z)\le D^{2}$ fails is a subset of $N_{1}\cup N_{2}$, hence null by The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §null-union, that is, $c\le D^{2}$ holds $\pi_{1}$-almost everywhere (A Property Holding Almost Everywhere). The constant $D^{2}$ is a nonnegative measurable function (claim 1 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions), equal to $D^{2}\mathbf{1}_{\mathbb{R}^{n+n}}$, so The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison, claim 1 of Linearity and Monotonicity of the Lebesgue Integral and The Integral of an Indicator Function is the Measure of the Set give

Hence $J$ is a real number in $[0,D^{2}]$, and $I(\pi)=tJ\le tD^{2}$ by claim 5 of Elementary Arithmetic in an Ordered Field, as $0\le t$.

Step 6 (conclusion). Since $\rho,\rho'\in\mathcal{P}_{2}(\mathbb{R}^{n})$ (Step 2) and $\pi\in\Pi(\rho,\rho')$ (Step 4), The Quadratic Wasserstein Distance on Euclidean Space §distance gives $W_{2}(\rho,\rho')^{2}\le I(\pi)\le tD^{2}$. As $0\le t$, we have $t\le t+t$ by claim 3 of Elementary Arithmetic in an Ordered Field, and since $0\le D^{2}$, claim 5 of that lemma and (2) give

By transitivity of the order, $W_{2}(\rho,\rho')^{2}\le D^{2}\sum_{i=1}^{M}|\rho(\{z_{i}\})-\rho'(\{z_{i}\})|$, which completes the proof.