On a Kantorovich-Rubinstein inequality

Abstract

An easy consequence of Kantorovich-Rubinstein duality is the following: if $f:[0,1{]}^d\to \infty$ is Lipschitz and $\left\{x_1,\dots ,x_N\right\}\subset [0,1{]}^d$, then $$\left|{\int }_{[0,1{]}^d}f(x)dx-\frac{1}{N}\sum _{k=1}^{N}f(x_k)\right|\le {\Vert \nabla f\Vert }_{L^{\infty }}\cdot W_1\left(\frac{1}{N}\sum _{k=1}^N{\delta }_{x_k},dx\right),$$ where $W_1$ denotes the $1-$Wasserstein (or Earth Mover's) Distance. We prove another such inequality with a smaller norm on $\nabla f$ and a larger Wasserstein distance. Our inequality is sharp when the points are very regular, i.e. $W_{\infty }\sim N^{-1/d}$. This prompts the question whether these two inequalities are specific instances of an entire underlying family of estimates capturing a duality between transport distance and function space.