Asymptotics for Random Quadratic Transportation Costs

For p\ge 1 and n+n i.i.d. uniform random points on [0,1]^d, \mathbb{E}\left[ \min_{\sigma \in \mathcal{S}_n} \sum_{i=1}^n |X_i - Y_{\sigma(i)}|^p \right] \approx R_{d,p}(n) := \begin{cases} n \cdot n^{-p/2} & \text{for $d=1$,} \\ n \cdot (\log n /n)^{p/2} & \text{for $d=2$,}\\ n \cdot n^{-p/d} & \text{for $d\ge 3$.} \end{cases}

For p>0 and n+n i.i.d. uniform random points on [0,1]^d, the limit \lim_{n \to \infty} \frac{ \mathbb{E}\left[ \min_{\sigma \in \mathcal{S}_n} \sum_{i=1}^n |X_i - Y_{\sigma(i)}|^p \right] }{R_{d,p}(n)} is currently known to exist in the cases:

• d=1, p\neq 1/2,

• d=2, p=2,

• d\ge 3, p>0.

For d \ge 3 and p\ge 1, there are constants 0<\mathsf{\alpha}_{low}(p,d) \le \mathsf{\alpha}_{upp}(p,d)<\infty such that for every (smooth, strictly positive) density \lambda on [0,1]^d and (X_i)_{i=1}^n, (Y_i)_{i=1}^n i.i.d. with common distribution \lambda:

• \liminf_{n \to \infty}\frac{ \mathbb{E}\left[ \min_{\sigma \in \mathcal{S}_n} \sum_{i=1}^n |X_i - Y_{\sigma(i)}|^p \right] }{n^{1-p/d}} \ge \mathsf{\alpha}_{low}(p,d) \int \lambda^{1-p/d}

• \limsup_{n \to \infty} \frac{ \mathbb{E}\left[ \min_{\sigma \in \mathcal{S}_n} \sum_{i=1}^n |X_i - Y_{\sigma(i)}|^p \right] }{n^{1-p/d}} \le \mathsf{\alpha}_{upp}(p,d)\int \lambda^{1-p/d}

• \mathsf{\alpha}_{upp}(p,d) := \lim_{n \to \infty} \frac{ \mathbb{E}\left[ \min_{\sigma \in \mathcal{S}_n} \sum_{i=1}^n |X_i - Y_{\sigma(i)}|^p \right] }{n^{1-p/d}}

• \mathsf{\alpha}_{low}(p,d) := \lim_{n \to \infty} \frac{ \mathbb{E}\left[ \min_{\sigma \in \mathcal{S}_n} \sum_{i=1}^n \mathsf{b}^p_{[0,1]^d}(X_i, Y_{\sigma(i)}) \right] }{n^{1-p/d}}

• where \left\{ X_i \right\}_i, \left\{ Y_i \right\}_i i.i.d. uniform and boundary cost: \mathsf{b}^p_{\Omega}(x,y) = \min\left\{ |x-y|^p, \min_{z,z' \in \partial \Omega} |x-z|^p + |z'-y|^p \right\}

For d \ge 3 and p\ge 1, there are constants 0<\mathsf{c}_{low}(p,d) \le \mathsf{c}_{upp}(p,d)<\infty

such that for every (smooth, strictly positive) density \lambda on [0,1]^d and i.i.d. (X_i)_{i=1}^n with common distribution \lambda:

\liminf_{n \to \infty}\frac{ \mathbb{E}\left[ \mathsf{W}^p\left( \frac 1 n \sum_{i=1}^n \delta_{X_i}, \lambda \right) \right] }{n^{-p/d}} \ge \mathsf{c}_{low}(p,d) \int_{[0,1]^d} \lambda^{1-p/d} \limsup_{n \to \infty} \frac{ \mathbb{E}\left[ \mathsf{W}^p\left( \frac 1 n \sum_{i=1}^n \delta_{X_i}, \lambda \right) \right]}{n^{-p/d}} \le \mathsf{c}_{upp}(p,d)\int_{[0,1]^d} \lambda^{1-p/d}

• \mathsf{c}_{upp}(p,d) := \lim_{n \to \infty} \frac{ \mathbb{E}\left[ \mathsf{W}^p\left( \frac 1 n \sum_{i=1}^n \delta_{X_i}, \mathcal{L}^d_{[0,1]^d} \right) \right] }{n^{-p/d}}

• \mathsf{c}_{low}(p,d) := \lim_{n \to \infty} \frac{ \mathbb{E}\left[ \mathsf{Wb}^p_{(0,1)^d} \left( \frac 1 n \sum_{i=1}^n \delta_{X_i}, \mathcal{L}^d_{[0,1]^d} \right) \right] }{n^{-p/d}}

• where \left\{ X_i \right\}_i are i.i.d. uniform on [0,1]^d and for \Omega \subseteq \mathbb{R}^d, \mathsf{Wb}^p_{\Omega} \left( \mu, \lambda \right) = \min_{\pi} \int_{\Omega\times \Omega} \mathsf{b}^p_{\Omega} (x,y) \pi(dx, dy).

For every d\ge 3 it holds

\mathsf{c}_{low}(2,d) = \mathsf{c}_{upp}(2,d).

If \lambda(x) \ge \lambda_0>0 for x\in \Omega, then \mathsf{W}^2(\mu,\lambda)\lesssim\lambda_0^{-1} \int_{\Omega} |\nabla f|^2.

• Neumann case (standard OT): \int_\Omega|\nabla f|^2 = \inf_{b} \left\{ \int_\Omega|b|^2\, : \, \operatorname{div}b = \mu - \lambda,\, b \cdot \nu_{\Omega} = 0 \right\}.

• Dirichlet case (boundary OT): \int_\Omega|\nabla u|^2 = \inf_{b} \left\{ \int_\Omega |b|^2\, : \, \operatorname{div}b = \mu - \lambda \right\}.

• Let \Omega \subseteq \mathbb{R}^d be convex and bounded,

  • \mu such that 1/2 \le \mu(\Omega)/|\Omega| \le 2 and set \lambda:= \mu(\Omega)/|\Omega| \mathcal{L}^d_{\Omega}

  • \eta be a smooth cutoff with \eta=1 on \partial \Omega, \eta= 0 at \mathsf{d}( , \Omega^c) \ge r

  • (v,u) be Kantorovich potentials for \mathsf{Wb}_{\Omega}^2\left( \mu, \lambda \right).

• Then, for every \varepsilon\in (0,1), \begin{equation*}\begin{split} \mathsf{W}^2\left( \mu, \lambda \right)& - \mathsf{Wb}_{\Omega}^2\left( \mu, \lambda \right) \lesssim\varepsilon\mathsf{Wb}_{\Omega}^2\left( \mu, \lambda \right) + \frac 1 {\varepsilon} \Bigg[ \mathsf{W}^2\left( \frac{\int_{\Omega} \eta d \mu }{\int_{\Omega} \eta } \eta , \eta \mu \right) \\ & \quad + \left( r^{-2} + \operatorname{diam}(\Omega)^2 r^{-4} \right) \int_{\Omega}|u|^2 \\ & \quad + \operatorname{diam}(\Omega)^{2} \left( \left| \frac{⨍_{\Omega} \eta d\mu }{ ⨍_{\Omega} \eta }-1 \right|^2 \int_{\Omega} \eta^2 + r^{-4} \mathsf{Wb}_{\Omega}^2(\mu, \lambda) ^{\frac{d+4}{d+2}} \right) \Bigg] \end{split} \end{equation*}

• Let
  • \mu be supported on [0,L]^d with \mu([0,L]^d) = L^d
  • (v, u) be Kantorovich potentials for \mathsf{Wb}_{\Omega}^2(\mu, \mathcal{L}^d_{[0,L]^d}) with ⨍_{(0,L)^d} u = 0.
• Then, it holds ⨍_{(0,L)^d} |u - \tilde u|^2 \lesssim L^2 \left[ L^{-d} \mathsf{Wb}^{2} _{(0,L)^d}(\mu, \mathcal{L}^d ) - \left( ⨍_{(0,L)^d} \tilde u + ⨍_{(0,L)^d} \tilde v d \mu \right) \right] for any pair of \mathsf{b}^2_{(0,L)^d}-conjugate functions (\tilde u, \tilde v) and ⨍_{(0,L)^d} \tilde u = 0.