In this article, we briefly explore the optimal transport problem on the real line along with some examples.
Linear Cost Example
For this example, consider the cost function along with a given linear map . Moreover, if let be any transport plan, then by direct computation we see that
which suggests that this result only depends on the marginals of (wherein and are compactly supported probability measures). In fact, in such cases, every transport plan/map is optimal.
Distance Cost Example
Consider the cost function along with probability measures (on ) and . Then, for any we see that , which then immediately puts us back in the linear cost position, so any transport map/plan is also optimal for such costs.
Book Shifting Example
Consider the cost function along with and (where is the one-dimensional Lebesgue measure). A (monotone) transport plan that rearranges to look like is given by and its corresponding cost is
Furthermore, notice that the piecewise map given by (for ) and (for ) satisfies , i.e. is a transport map from to ; moreover, the corresponding cost is
and so we conclude that is indeed optimal as well.
Theorem: Let be probability measures on with cumulative distribution functions (CDFs) and , respectively. Also, let be the probability measure on with the CDF . Then, and is optimal (in the Kantorovich problem setting) between and for the (quadratic) cost function , and the corresponding cost is
where and are the pseudo-inverses of the respective CDFs.
Ideas and Remarks for the Proof
Note the proof from Cedric-Villani gives this result in arbitrary dimensions. Below is a rough outline of proof, and the full details can be found in "Topics in Optimal Transportation" (Villani, cite later). Moreover, the measure constructed in the theorem indeed is optimal provided that the cost function is of the form where is a convex, nonnegative symmetric function on .
One of the first major steps in proving this theorem is showing that by considering specific cases. Upon showing this, we may conclude that is supported in a monotone subset of and hence also supported in the sub-differential of some lower semi-continuous convex function. From here, we make use of the Knott-Smith optimality criterion (Villani pg 66) which establishes that is an optimal transference plan. Then, upon showing that , we see that for any nonnegative, measurable function on
This then immediately yields the cost and completes the proof.