2
$\begingroup$

Given two random variables $X,Y$ which are both $\mathbb{N}$-valued and have the same expected value (which is some fixed positive constant), and denote their probability mass functions by ${\bf p} = (p_0,p_1,\ldots)$ and ${\bf q} = (q_0,q_1,\ldots)$, respectively. We also assume that $q_n > 0$ for all $n \in \mathbb N$. I am pretty sure one can upper bound the Wasserstein distance (of order 1) $W_1({\bf p},{\bf q})$ by the so-called $\chi^2$ distance defined via $$\chi^2({\bf p},{\bf q}) = \sum\limits_{n\geq 0} \frac{|p_n-q_n|^2}{q_n} = \sum\limits_{n\geq 0} \frac{p^2_n}{q_n} - 1.$$ However, I fail to found any specific reference containing a statement like $$W_1({\bf p},{\bf q}) \leq f\left(\chi^2({\bf p},{\bf q})\right)$$ for some appropriate non-negative function $f$ which vanishes at the origin. I will appreciate any help in locating a suitable reference for the advertised bound...


Remark: I forgot to mention that ${\bf p}$ and ${\bf q}$ have the same mean value in my original post.

$\endgroup$
7
  • $\begingroup$ Some basic thoughts: You can use chi squared to bound TV and then use that to bound W1 if your measures are defined on a finite subset (see arxiv.org/pdf/math/0209021.pdf). Otherwise, I fail to see how we are controlling W1 which depends on the order of the p_i s with chi squared which does not? $\endgroup$
    – Efe
    Oct 26, 2022 at 22:43
  • $\begingroup$ @Efe Thank you for pointing out this very interesting reference! As I mentioned in the updated post, I forgot to mention that ${\bf p}$ and ${\bf q}$ have the same expected value. Also, the relative entropy does depend on the order of ${\bf p}$ and ${\bf q}$ but it is still a very "strong" measure of closeness between two distributions (stronger than Wasserstein), right? $\endgroup$
    – Fei Cao
    Oct 26, 2022 at 23:25
  • $\begingroup$ In general it isn't? you need to impose a bunch of structure on q for that kind of control (think bakry-emery criterion and T2). I am not sure if mean is enough, as it seems I can move p_n -> p_5n and q_n -> q_5n which should scale the mean (and W1?), but not the chi squared? Now, if f is dependent on the mean, I dont have an example off the top of my head. $\endgroup$
    – Efe
    Oct 26, 2022 at 23:50
  • $\begingroup$ @Efe Actually in my problem I only care about the case when ${\bf q}$ is a Poisson distribution. I believe such estimate must have been done somewhere in the literature for a genetic ${\bf q}$ with full support on $\mathbb N$. $\endgroup$
    – Fei Cao
    Oct 26, 2022 at 23:57
  • $\begingroup$ Wasserstein is almost an anagram of Weierstrass. $\endgroup$ Oct 27, 2022 at 1:31

1 Answer 1

1
$\begingroup$

Such a real-valued function $f$ does not exist.

Indeed, for any natural $N$, let $$(p_N,p_{2N},p_{3N})=\tfrac18(1,4,2),\ (q_N,q_{2N},q_{3N})=\tfrac18(2,2,3),$$ so that $p_N+p_{2N}+p_{3N}=q_N+q_{2N}+q_{3N}=\frac78$ and $Np_N+2Np_{2N}+3Np_{3N}=Nq_N+2Nq_{2N}+3Nq_{3N}$. Next, for $n\in J:=\{0,1,\dots\}\setminus\{N,2N,3N\}$, let $q_n$ be any positive real numbers such that $\sum_{n\in J}q_n=1-\frac78$, and let $p_n=q_n$ for $n\in J$.

Then $EX=EY$ and the $\chi^2$ distance between the distributions of $X$ and $Y$ is a certain positive real number, not depending on $N$.

On the other hand, the Wasserstein distance between the distributions of $X$ and $Y$ is $\sim cN\to\infty$ (as $N\to\infty$) for a certain positive real number $c$. (this easily follows from, say, the [known expression for such Wasserstein distance][1]

So, your desired inequality cannot hold for any real-valued function $f$.

$\endgroup$
7
  • $\begingroup$ Hello professor, indeed, I only care about the case when ${\bf q}$ is a Poisson distribution... $\endgroup$
    – Fei Cao
    Oct 26, 2022 at 23:58
  • $\begingroup$ @FeiCao : Too bad, your post did not say that. It is disrespectful to add one condition after another to your original post, especially after getting an answer. However, as an exercise, you should be able to easily modify the example above, with the same effect. $\endgroup$ Oct 27, 2022 at 0:04
  • $\begingroup$ I am so sorry for that! Thank you for your answer! $\endgroup$
    – Fei Cao
    Oct 27, 2022 at 0:09
  • $\begingroup$ @FeiCao : If $f$ is allowed to depend on the second moment of $Y$, then the answer becomes positive -- see mathoverflow.net/a/433344/36721 $\endgroup$ Oct 27, 2022 at 14:29
  • $\begingroup$ Dear Professor, I am sorry that my problem description is not precise (and it's totally my fault), here the mean value of X and Y are fixed (hence it is equal to some fixed constant) and hence is not "scalable". $\endgroup$
    – Fei Cao
    Oct 27, 2022 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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