Skip to main content
2 of 13
deleted 24 characters in body
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Improved bound via another method

It seems it is possible to improve the bound in the accepted answer from $d^{-1}$ to $d^{-3/2+o(1)}$ by using concentration of measure. I hope I've not made a mistake somewhere.


Let $F$ be the marginal cdf of $\sqrt{d}x_1$ and let $F^c := 1 - F$ be its survival function. Let $\Phi$ be the standard gaudssian cdf.

We will make use of the following fact (see ref https://mathoverflow.net/a/315232/78539)

Fact 1. $\sup_{t \in \mathbb R}|F(t) - \Phi(t)| \le C/d$, for an absolute constant $C>0$ which doesn't depend on $d$.

We shall also need the following fact (which follows from Gaussian concentration of $N(0,1)$ and sub-exponential concentration of $x_1$)

Fact 2. There exists an absolute constant $b>0$ such that $\max(F(-t),\Phi(-t),F^c(t),\Phi^c(t)) \le e^{-bt}$ for sufficiently large $t>0$.

Now, for any $T > 0$, one computes $$ W_1(\sqrt{d}x_1,N(0,1)) = \int_{\mathbb R} |F(t)-\Phi(t)|dt = A_1(T) + A_2(T) + A_3(T), $$ where the $A_k(T)$'s are defined by $$ \begin{split} A_1(T) &:= \int_{-\infty}^{-T}|F(t)-\Phi(t)|dt,\\ A_2(T) &:= \int_{-T}^T|F(t)-\Phi(t)|dt,\\ A_3(T) &:= \int_{T}^\infty|F(t)-\Phi(t)|dt=\int_{T}^\infty|F^c(t)-\Phi^c(t)|dt. \end{split} $$

Thanks to Fact 1, we know that $A_2(T) = \mathcal O(T/d)$. On the other hand, thanks to Fact 2 we have for sufficiently large $T>0$, $$ A_1(T) \le \int_{-\infty}^{-T} \max(F(t),\Phi(t))dt \le \int_{-\infty}^{-T} e^{bt}dt = e^{-bT}/b. $$

By a symmetric argument, we also have $A_3(T) \le e^{-bT}/b$. Taking $T=(\log d)/b$ then gives $A_2(T) = \mathcal O((\log d)/d)$ and $A_1(T),A_3(T) = \mathcal O(1/d)$. Thus $W_1(\sqrt{d} x_1,N(0,1)) = \mathcal O((\log d)/d)$, and so $$ W_1(x_1,N(0,1/d)) = \mathcal O(\frac{\log d}{\sqrt{d}}\frac{1}{d}) = \mathcal O(d^{-3/2+o(1)}) \ll d^{-1}. $$

dohmatob
  • 6.9k
  • 1
  • 18
  • 76