# Rate of convergence of empirical distribution with respect to Wasserstein distance induced by binary cost function

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$$.

• 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. – dohmatob Aug 9 '19 at 11:40
• If $\Omega \subset \mathcal{X}\times\mathcal{X}$ is arbitrary, e.g. with just one element $(x_1, x_2)$ and $P = \delta_{x_1}$. Then the probability $P(C_\Omega(P, \hat{P}_n) > t)$ is just always 1. What are you hoping for in the first case? – Steve Aug 10 '19 at 7:15
• This is not possible. If $P=\delta_{x_1}$, then $\hat{P}_n = P$ for all $n$ (since every draw from $P$ must correspond to the point $x_1$), and so $c_\Omega(P,\hat{P}_n)=0$. Or am I missing something in your example ? – dohmatob Aug 11 '19 at 14:22
• the point of my example is that in your general case, $c_\Omega(P, P)$ doesn't necessarily have to be 0. Or what are the assumptions on $\Omega$? – Steve Aug 11 '19 at 18:04