Let $\mathcal X=(\mathcal X, d)$ be a Polish space (i.e complete metric space), and let $\Omega$ be a non-empty subset. Consider the binary cost function $c_\Omega$ on $\mathcal X^2$ defined by $c_\Omega(x,x') = \begin{cases}1,&\mbox{ if }(x,x') \in \Omega,\\0,&\mbox{ else,}\end{cases}$
and the induced Wasserstein distance on probability distributions on $\mathcal X$, defined by
$$
c_\Omega(Q_1,Q_2) := \inf_{\gamma}\mathbb E_{(x,x') \sim \gamma}[c_\Omega(x,x')] = \inf_{\gamma}\gamma(\Omega),
$$
where the infimum is taken over all *couplings* of $Q_1$ and $Q_2$.

Finally, let $P$ be a probability distribution on this space, and let $x_1,\ldots,x_n \sim P$ be an i.i.d sample of size $n$, and let $\hat{P}_n := (1/n)\sum_{i=1}^n\delta_{x_i}$ be the induced empirical distribution.

# Question

1) What are good tail bounds for random variable $c_\Omega(P,\hat{P}_n)$ ? That is, for $t > 0$ what is a good upper bound for the probability $P(c_\Omega(P,\hat{P}_n) \gt t)$ ?

2) Same question with the additional condition that $\Omega := \{(x,x') \in \mathcal X^2 \mid d(x,x') > \alpha\}$ for some $\alpha \ge 0$.

**Related questions:** Find $\inf_{P_{X_1,X_2}}P_{X_1,X_2}(\|X_1-X_2\| > 2\alpha)$ , where $\alpha > 0$ and inf is over couplings

Observation.Note that the variance of $c_\Omega(P,\hat{P}_n)$ is at most $1/4$. So if I can get a reasonable bound for expectation of $c_\Omega(P,\hat{P}_n)$, then I can use Hoeffding's inequality to get a tail bound. $\endgroup$ – dohmatob Aug 9 '19 at 11:40