Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $(X,d)$ be some metric space and assume that $d\leq 1$. Further, let $\mu, $ $\nu$ be two Borel probability measures on $X$ and let $$ \Gamma(\mu,\nu) = \{\gamma - \text{measure on }X\times X:\gamma(A,X) = \mu(A),\gamma(X,A) = \nu(A) \} $$ to be the space of all couplings of $\mu$ and $\nu$. Define $$ W_1(\mu,\nu) = \inf_{\gamma\in \Gamma(\mu,\nu)}\int_{X\times X} d(x,y)\gamma(\mathrm dx\times\mathrm dy) $$ to be the Wasserstein distance (of order $1$) between $\mu$ and $\nu$.

Suppose, we are able to draw two sets of random elements according to these distributions. E.g. $\{X_i\}$ is iid such that $X_i\sim \mu$ and $\{Y_j\}$ is iid such that $Y_j\sim \nu$ where $1\leq i,j\leq n$.

Is it possible to derive any results on $W_1(\mu,\nu)$ using $\{d(X_i,Y_j)\}_{ij}$, with some confidence-like bounds?

Some thoughts: let $\gamma(d):=\int_{X\times X}d(x,y)\mathrm d\gamma$. A dummy way is for a fixed $\gamma$, we can simulate pairs $(X_i,Y_i)\sim \gamma$ and then define $$ \overline{\gamma(d)}:=\frac1n\sum d(X_i,Y_i). $$ By the Hoeffding inequality we get $$ \Bbb P\left(\left|\gamma(d) - \overline{\gamma(d)}\right|\geq t\right)\leq 2 \mathrm e^{-nt^2} $$ and since $\gamma(d) \geq W_1(\mu,\nu)$ we can get some conservative upper bounds on the distance. The conservatism clearly depends on how $\gamma$ is far from the optimal coupling.

Perhaps, we can do something like that: simulate $\{X_i\}$ and $\{Y_j\}$ and consider $$ \bar W:= \frac1n\sum_{i=1}^n \min_j d(X_i,Y_j) $$ thus "coupling" $X$ and $Y$ on-the-run. But I am not sure whether this is an unbiased estimate and whether it allows for some bounds on the error.

Please feel free to retag. Perhaps I shall better ask it on statistics.SE?

share|cite|improve this question
up vote 5 down vote accepted

The authors of the recent paper "On the empirical estimation of integral probability metrics (2012, Electronic Journal of Statistics)" have a setting where they present an estimator for Wasserstein metrics based on data and where they derive consistency of the estimator with convergence rates. It could be directly applied to a Monte Carlo setting.

share|cite|improve this answer
Awesome, that shall be a benchmark example of how the bounty helps :) – Ilya Mar 4 '13 at 13:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.