1
$\begingroup$

Let $x_1,\dots,x_n\in X$ some Polish space $X$ and let $\Delta$ be the probability simplex in $\mathbb{R}^n$. Consider the map sending every $(w_1,\dots,w_n)\in\Delta$ to the finitely supported measure $\sum_{k=1}^n w_k\delta_{x_k}$. This map is clearly continuous with respect to the Wasserstein distance, but is it also Lipschitz?

$\endgroup$
1
$\begingroup$

$\newcommand\De\Delta\newcommand\de\delta$Yes, this map is Lipschitz. Indeed, the map is \begin{equation*} \De\ni w=(w_1,\dots,w_n)\mapsto\mu_w:=\sum_{k=1}^n w_k\de_{x_k}. \tag{1} \end{equation*} Let $d$ denote the metric on $X$, and then let \begin{equation*} D:=\max_{i,j\in[n]}d(x_i,x_j), \end{equation*} the diameter of the set $\{x_1,\dots,x_n\}$, where $[n]:=\{1,\dots,n\}$.

Take any $v=(v_1,\dots,v_n)$ and $w=(w_1,\dots,w_n)$ in $\De$ and let \begin{equation*} h:=\max_{j\in[n]}|v_j-w_j|. \end{equation*} Consider the following $(n-1)$-step transportation plan of transporting the probability measure $\mu_v$ to $\mu_w$ (or vice versa).

For the first step of the plan, transport $\mu_v$ to $\mu_{v^{(1)}}$, where \begin{equation*} v^{(1)}:=\Big(w_1,v_2+\frac{v_1-w_1}{n-1},\dots,v_n+\frac{v_n-w_n}{n-1}\Big), \end{equation*} assuming without loss of generality that $v_1\ge w_1$. Then (i) the first coordinate of $v^{(1)}$ is the same as that of $w$, (ii) $v^{(1)}\in\De$, (iii) \begin{equation*} \max_{2\le j\le n}|v^{(1)}_j-w_j|\le\max_{2\le j\le n}|v_j-w_j|+\frac{v_1-w_1}{n-1}\le h+\frac h{n-1}=\frac n{n-1}\,h, \end{equation*} and (iv) \begin{equation*} W(\mu_v,\mu_{v^{(1)}})\le\sum_{j=2}^n \frac{v_1-w_1}{n-1}\,d(x_1,x_j) \le(v_1-w_1)D\le hD, \end{equation*} where $W$ denotes the Wasserstein distance.

In the remaining $n-2$ steps of the plan, similarly and consecutively equalizing the remaining $n-1$ coordinates of the initially given vectors $v=(v_1,\dots,v_n)$ and $w=(w_1,\dots,w_n)$, we see that \begin{equation*} W(\mu_v,\mu_w)\le hD+\frac n{n-1}\,hD+\frac n{n-2}\,hD+\cdots+\frac n1\,hD \le Lh, \end{equation*} where $L:=n(1+\ln n)D$. So, the map (1) is Lipschitz.

$\endgroup$
2
  • $\begingroup$ Thanks for the great explanation. May I ask, if you know of a reference for this which I could cite $\endgroup$ – Bernard_Karkanidis Feb 21 at 15:49
  • 2
    $\begingroup$ @Bernard_Karkanidis : I don't know a reference for this. However, MathOverflow answers can, and have been, cited by using the Cite button under the answer, which produces a BibTeX entry. $\endgroup$ – Iosif Pinelis Feb 21 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.