1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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
    Commented Aug 9, 2019 at 11:40
  • $\begingroup$ 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? $\endgroup$
    – Steve
    Commented Aug 10, 2019 at 7:15
  • $\begingroup$ 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 ? $\endgroup$
    – dohmatob
    Commented Aug 11, 2019 at 14:22
  • $\begingroup$ 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$? $\endgroup$
    – Steve
    Commented Aug 11, 2019 at 18:04

0

Reset to default

You must log in to answer this question.