(Sub)Optimality of random transport

Question

Problem Setup: Consider the intervals $I_R = [a_R, b_R]$ and $I_B = [a_B,b_B]$. Let $F_R$ and $F_B$ denote the CDF of distributions with support on the intervals $I_R$ and $I_B$. I draw $k$ red and blue points from $F_R$ and $F_B$ respectively. Let $\mathscr{R}$ and $\mathscr{B}$ denote the set of these $k$ red and blue points respectively. I consider the following matching procedure: I randomly pick a blue point in the set $\mathscr{B}$ and match it to the closest red point in set $\mathscr{R}$ where the distance is measured using the function $c(r,b) = |r-b|^\alpha$ for $\alpha > 1$. After I match, I remove the blue point and its matched red point from set $\mathscr{B}$ and $\mathscr{R}$ respectively. I continue with this procedure till I have emptied the sets $\mathscr{R}$ and $\mathscr{B}$.

Let us denote the average matching cost (averaged across $k$ points) be to $\mathsf{RND}(k)$. In the case where $k \to \infty$, the optimal matching cost is the optimal transport value between $F_R$ and $F_B$ with the cost function $c(r,b)$. Let us denote that optimal transport value as $\mathsf{OPT}$.

If it helps, one may assume for simplicity that both $F_R$ and $F_B$ are continuous distributions on the interval $I_R$ and $I_B$ respectively with densities bounded above and below.

Questions: I want to know under what conditions does $\lim_{k \to \infty} |\mathsf{RND}(k) - \mathsf{OPT}| = 0$ and $\lim_{k \to \infty} |\mathsf{RND}(k) - \mathsf{OPT}| \neq 0$? More specifically, I am looking for conditions on $F_R$ and $F_B$.

1. I believe that if $F_R = F_B$, then it might be the case that $\lim_{k \to \infty} |\mathsf{RND}(k) - \mathsf{OPT}| = 0$? While I intuitively think that this is the case, I am unable to find a proof for this.
2. If the supports $I_R$ and $I_B$ are disjoint, then $\lim_{k \to \infty} |\mathsf{RND}(k) - \mathsf{OPT}| \neq 0$? I am unable to prove this for general $F_R$ and $F_B$, but my intuition comes from the case when $F_R = \text{Unif}(I_R)$ and $F_B = \text{Unif}(I_B)$. In this case I think it can be easily argued that $\lim_{k \to \infty} |\mathsf{RND}(k) - \mathsf{OPT}| \neq 0$?
3. Extrapolating the previous point further, can we show that $\lim_{k \to \infty} |\mathsf{RND}(k) - \mathsf{OPT}| \neq 0$ under the following condition: We have that $F_R(x) \geq F_B(x)$ for all $x \in (-\infty, \infty)$ and there exists an interval $I^\prime$ with positive measure such that $F_R(x) > F_B(x)$ for $x \in I^\prime$. I think this condition subsumes the case when the intervals $I_R$ and $I_B$ are disjoint.
4. (Perhaps Ill Defined) Is there a more general set of assumptions on $F_R$ and $F_B$ such as $F_R \neq F_B$ which are sufficient to show that $\lim_{k \to \infty} |\mathsf{RND}(k) - \mathsf{OPT}| \neq 0$?
5. Is there a good reference which shows that the optimal transport map (outside of a zero measure set) does an assortative match, i.e., point $r$ gets matched to $F_B^{-1}(F_R(r))$ ?

Any help or pointers with this or related questions/papers would be greatly appreciated. Thanks :)

Answer 1

The reference for the fact that $r$ gets matched to $F_B^{-1}(F_R(r))$ can be found in Theorem 2.9 of [1]. In one-dimensional optimal transport, this is known as the monotone map. I believe that the optimality of this map shows that the random transport cannot converge to the optimal map except in several very special circumstances.

For instance, your intuition about disjoint sets is correct. If $I_B$ is entirely to the left of $I_R$, then no matter which blue point you choose, you will take the left-most remaining red point. Therefore, in the large-$k$ limit, the random coupling will converge in a suitable sense to the product measure with CDF $F_R \times F_B$. On the other hand, for measures in one-dimension, the optimal transport between $F_R$ and $F_B$ is given by the monotone map. Unless one of the measure is supported at a single point, this is different from the product measure.

Using the monotone mapping, some more careful analysis shows that $\lim_{k \to \infty} |\mathsf{RND}(k) - \mathsf{OPT}| \neq 0$ unless the measures are chosen so that the red-point closest to the blue-point is the target of the monotone map for the associated measures. There are only two cases where I can see that this occurs.

1. If the two measures are the same.
2. If one of the measures is comprised of atoms and arranged as a one-dimensional Voronoi diagram of the other measure (with the appropriate weight on each atom).

It is possible to consider mixtures of these two cases so long as the regions where each case occurs are sufficiently far apart. In all these cases, I suspect that the random map converges to the optimal one in an appropriate sense, but do not see how to prove this off-hand. It is possible that there are other cases which I am missing, but this shows that in most cases the random process you describe will not converge to the optimal map.

[1] Santambrogio, Filippo, Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling, Progress in Nonlinear Differential Equations and Their Applications 87. Cham: Birkhäuser/Springer (ISBN 978-3-319-20827-5/hbk; 978-3-319-20828-2/ebook). xxvii, 353 p. (2015). ZBL1401.49002.

Edit: Here's an argument to show that when the intervals are disjoint, the random coupling converges to the product measure. For this, it is instructive to change perspectives and consider a sample of blue points in $I_B$ which we denote $\{B_i\}_{i=1}^n$. If we order the points from left to right and consider the $k$-th such point $B_k$, we can consider its pre-image $T^{-1} (B_k)$ under the matching process $T$.

We want to understand the distribution of $T^{-1} (B_k)$, but this will simply be the distribution of the $k$-th draw from $I_R$, and the draws are done iid with respect to $F_R$. Therefore, the distribution of $T^{-1} (B_k)$ is simply given by $F_R$. Equivalently, one can observe that if we have a sample of $n$ points that were drawn iid from $I_R$ (for a non-atomic measure), the order in which those points appear has uniform measure on the permutation group $S_n$. Therefore, if we have $n$ points drawn from $I_R$ and $I_B$, any matching of these points under the process you've described is equally likely.

This shows that the random matching is equivalent to picking random points on $I_r \times I_B$ with respect to the CDF $F_R \times F_B$, and from here it is fairly straightforward to see that the measure created by putting normalized Dirac masses at each point converges to the product measure in the weak-star sense.