Practical bounds for the Wasserstein distance in 2 dimensions Let $X_1,\dots,X_n$ be a set of independent samples of a distribution $\mu$ on the unit square, let $\hat\mu_n$ be the empirical distribution on the points $X_1,\dots,X_n$, and let $W_1(\mu,\hat\mu_n)$ denote the $1$-Wasserstein distance between $\hat\mu_n$ and $\mu$.  Are there any simple, concrete bounds on $\Pr(W_1(\mu,\hat\mu_n)\geq t)$, where $n\leq 100$ and $t$ is fairly large (e.g. order of $n^{-1/2}$)?.
There are many results that describe the asymptotic behavior of this quantity, such as the papers http://www.emis.ams.org/journals/EJP-ECP/article/download/958/1147.pdf and http://link.springer.com/article/10.1007/s00440-014-0583-7 , but these tend to take the form of existence proofs and limiting statements (e.g. "There exist constants $C$ and $c$ such that $\Pr(W_1(\mu,\hat\mu_n)\geq t)\to (*)$).  Are there any simple "ad-hoc" bounds that can bound  $\Pr(W_1(\mu,\hat\mu_n)\geq t)$ for fixed values of $n$ and $t$?
 A: Sorry, I don't have the reputation to comment. 


*

*Most of the bounds in the first paper you cite are completely explicit as you go through the proofs, and can be used to obtain a bound of the form you want. Of course, the constants they write down are a little more complicated than the ones you normally get in e.g. Hoeffding's inequality, but you can always do something a little bit lazy.

*You can get rather poor bounds without much work by combining the  Dvoretzky–Kiefer–Wolfowitz inequality, the Wasserstein duality theorem and a covering argument. An argument would go something like:
A. By Wasserstein duality, $W_{1}(\mu, \hat{\mu}) \leq \sup_{f \in \mathcal{F}} | \mu(f) - \hat{\mu}(f) |$ for some `nice' family $\mathcal{F}$. 
B. By a covering argument, for all $\epsilon > 0$ there exists a finite set $\mathcal{F}_{\epsilon} \subset \mathcal{F}$ s.t. $W_{1}(\mu, \hat{\mu}) \leq \sup_{f \in \mathcal{F}_{\epsilon}} | \mu(f) - \hat{\mu}(f) | + \epsilon$.
C. Look at a particular $f \in \mathcal{F}_{\epsilon}$. The Dvoretzky–Kiefer–Wolfowitz theorem gives us a bound on $P[ | \mu(f) - \hat{\mu}(f) | > \epsilon]$. Taking a union bound over   $f \in \mathcal{F}_{\epsilon}$ and applying 2.B gives the result you want.
Unfortunately, I don't remember where to find the `right' covering argument for the 1-Wasserstein distance and the unit square (the details of which Wasserstein distance you're using and the target space make a difference to the efficiency of this bound).
A: There are a few references worth mentioning:


*

*https://hal.archives-ouvertes.fr/hal-00915365/document

*https://www.lpsm.paris/pageperso/bolley/bgv.pdf

*https://arxiv.org/pdf/1804.10556.pdf
Example of a bound you could hope to get
Let $d \ge 2p$ be the dimensionality of your square. Suppse $\mu$ is light-tailed, i.e suppose there exists $\alpha > p$ such that $\int \exp(|X|^\alpha) d\mu < \infty $. Then for every $t > 0$, one has
$$
P(W_p(\mu,\hat{\mu}_n) \ge t) \le \begin{cases}c_1\exp(-c_2Nt^{d/p}),&\mbox{ if }t \le 1,\\ c_1\exp(-c_2Nt^{\alpha/p}),&\mbox{ else,}\end{cases}
$$
where $c_1$ and $c_2$ are positive constants independent of $N$ and $t$.
This is a direct consequence of Theorem 2 of the first paper.
You can get an even finer bound by using Proposition 10.
