I am looking for the largest Wasserstein distance to the uniform distribution among all probability distributions with uniform marginals.
More specifically, let $\Xi=\{1,2,\ldots,N\}^2$, and let $\nu$ be a uniform distribution on $\Xi$, namely, $\nu_{ij}:=\nu(\{(i,j)\})=\frac{1}{N^2}$, for all $1\leq i,j\leq N$.
Consider the problem
\begin{equation}
\max_{\mu\geq0} \bigg \{ W(\mu,\nu):\ \sum_{i}\mu_{ij} = \frac{1}{N}, \forall j,\ \sum_{j} \mu_{ij}=\frac{1}{N}, \forall i \bigg\}, \tag{1}
\end{equation}
where $W_1(\mu,\nu)$ is the Wasserstein distance between probability distribution $\mu:=\{\mu_{ij}\}_{1\leq i,j\leq N}$ and $\nu$, defined as
$$
W_1(\mu,\nu) :=
\min_{\pi\geq0} \bigg\{\sum_{1\leq i,j,i',j' \leq N} ||(i,j)-(i',j')||_1 \pi_{(i,j),(i',j')}:\ \sum_{i,j} \pi_{(i,j),(i',j')} = \nu_{i'j'},\forall i',j',\ \sum_{i',j'} \pi_{(i,j),(i',j')} = \mu_{ij},\ \forall i,j\bigg\}.
$$
My conjecture is that the maximizer of problem $(1)$ is given by $\mu_{ij}=\frac{1}{N}{1}_{\{i=j\}}$, or $\mu_{ij}=\frac{1}{N}{1}_{\{i+j=N+1\}}$, namely, the comonotonic/countermonotonic distribution. But how to prove/disprove it? Also, if it is true, could the result be extended to the multivariate case, namely, $\Xi=\{1,2,\ldots,N\}^K$ for $K>2$, or be extended for norms other than $\ell_1$-norm, or other $W_p$ distance ($p>1$)?
Update: Steve provides an affirmative answer for $\ell_1$-norm with $W_1$ distance in the case of $K=2$, and I provide a proof for $\ell_2$ norm with $W_2$ distance for all $K\geq2$. I am wondering if we can get some other result, such as $\ell_1$-norm with $K>2$, or $\ell_\infty$-norm.
Best Answer
I think I have an answer for the case p = 1, K = 2. I write "I think" because my computation does not coincide with the example values for $N=4$ posted earlier by OP in a comment, but I really cannot find any error in my proof, so I wanted to share it.
As already mentioned, we only need to consider permutation measures of the form $\mu = \sum_{i=1}^N \frac{1}{N} \delta_{i,\sigma(i)}$, since these are the extremal points of the set we optimize over.
For any such $\mu$, we can define a coupling $\pi$ by $\pi_{(i,\sigma(i)),(i,j)} = 1/N^2$ for $i,j \in \{1,...,N\}$ and $\pi_{(i,j),(i',j')} = 0$, if $i,j,i',j'$ are not of the form as before. That this is an admissible coupling in the definition of $W_1$ is trivial. The corresponding "value" is $$ \sum_{1\leq i,j,i',j' \leq N} ||(i,j)-(i',j')||_1 \pi_{(i,j),(i',j')} = \sum_{1 \leq i,j' \leq N} |\sigma(i) - j'| \frac{1}{N^2}. $$ We further show that this value is minimal if $\mu$ is the monotonic or comonotonic measure, which will yield the claim. I only show this for the monotonic case, $\mu = \frac{1}{N}\sum_{i=1}^N \delta_{i,i}$. Then for any admissible coupling $\hat{\pi}$, by the constraints in the calculation of the Wasserstein distances, we see \begin{align*} \sum_{1\leq i,j,i',j' \leq N} ||(i,j)-(i',j')||_1 \hat{\pi}_{(i,j),(i',j')} =& \sum_{1\leq i',j' \leq N} \sum_{1 \leq i \leq N} ||(i,i)-(i',j')||_1 \hat{\pi}_{(i,i),(i',j')} \\ \geq& \sum_{1\leq i',j' \leq N} \sum_{1 \leq i \leq N} ||(i',i')-(i',j')||_1 \hat{\pi}_{(i,i),(i',j')}\\ =&\sum_{1\leq i',j' \leq N} |i'-j'| \frac{1}{N^2}, \end{align*} where the inequality is elementwise and the last term corresponds to the value for the coupling $\pi$.
Note that this only shows that monotonic/comonotonic measures are maximizers, but not that these are the only maximizers.