Are gaussians with different moments far in total variation distance?

Question

If two Gaussians disagree on one moment, it seems like this should imply that they have a large variation distance--equivalently, if two Gaussians are close in variation distance it's hard for their moments to differ very much. But I'm having trouble proving this without getting into a terrible mess and ending up with weak bounds. I'm hoping someone here can offer a slick proof or point me to one.

Suppose that $\Sigma_1$ and $\Sigma_2$ are two positive-semidefinite matrices, with diagonal entries bounded by 1, and that $\Sigma_1$ and $\Sigma_2$ differ by at least $\delta$ in one of their entries.

Can we lower-bound the total variation distance between the multivariate gaussians with covariance matrices $\Sigma_1$ and $\Sigma_2$? In particular, is this distance at least $\Theta(\delta)$? It seems like it ought to be, since the gaussians are pretty well concentrated. But trying to formalize the obvious approach seems to create a bit of a mess.

Edit: Douglas Zare and guest point out that you can trivially reduce to the 2 dimensional case by projecting onto the relevant subspace. So we can restrict attention to that case.

Answer 1

Letting $\mu_{a,\Sigma}$ be the Gaussian measure with covariance matrix $\Sigma$ and mean $a$. Then (double) the variation distance can be written as $$ \left\lVert\mu_{a_1,\Sigma_1}-\mu_{a_2,\Sigma_2}\right\rVert_1 = \max_f\left\lvert\mu_{a_1,\Sigma_1}(f)-\mu_{a_2,\Sigma_2}(f)\right\rvert, $$ where the maximum is taken over functions $f\colon\mathbb{R}^n\to\mathbb{C}$ with $\lvert f\rvert\le1$. Taking $f(x)=\exp(ix\cdot u)$ for a fixed $u\in\mathbb{R}^n$, plugging in the characteristic function for Gaussian distributions, $$ \begin{align} \left\lVert\mu_{a_1,\Sigma_1}-\mu_{a_2,\Sigma_2}\right\rVert_1&\ge\max_{u\in\mathbb{R}^n}\left\lvert e^{ia_1\cdot u-\frac12 u^t\Sigma_1u}-e^{ia_2\cdot u-\frac12 u^t\Sigma_2u}\right\rvert\\ &\ge\max_{u\in\mathbb{R}^n}\left\lvert e^{-\frac12 u^t\Sigma_1u}-e^{-\frac12 u^t\Sigma_2u}\right\rvert\\ &=\max_{u\in\mathbb{R}^n,\lVert u\rVert_1=1}\max_{\lambda\ge0}\left\lvert e^{-\frac12 \lambda^2u^t\Sigma_1u}-e^{-\frac12 \lambda^2u^t\Sigma_2u}\right\rvert. \end{align} $$ Note that, for any $1\ge\alpha > \beta > 0$, we can consider $\lambda=1/\sqrt{\alpha}$ to get the following bound, $$ \max_{\lambda\ge0}\left(e^{-\lambda^2\beta}-e^{-\lambda^2\alpha}\right)\ge e^{-\frac\beta\alpha}-e^{-1}=\Theta\left(1-\frac\beta\alpha\right)=\Theta(\alpha-\beta). $$ Hence, as we are assuming $\Sigma_i$ are positive semidefinite with diagonal entries bounded by 1, we have $1\ge u^t\Sigma_iu\ge0$ for $u\in\mathbb{R}^n$ with $\lVert u\rVert_1=1$ and, $$ \left\lVert\mu_{a_1,\Sigma_1}-\mu_{a_2,\Sigma_2}\right\rVert_1=\Theta\left(\max_{\lVert u\rVert_1=1}\left\lvert u^t(\Sigma_1-\Sigma_2)u\right\rvert\right) $$ For any symmetric matrix $M$ we have $2M_{ij}=(e_i+e_j)^tM(e_i+e_j)-e_i^tMe_i-e_j^tMe_j$ where $e_i$ is the unit vector along coordinate dimension $i$, from which we get $$ \left\lVert\mu_{a_1,\Sigma_1}-\mu_{a_2,\Sigma_2}\right\rVert_1=\Theta\left(\lVert\Sigma_1-\Sigma_2\rVert_\infty\right) $$

Answer 2

(This is actually more of a comment, but I do not have that privilege. Since it may be useful, I post it as an answer. If someone can make this a comment, please do so.)

Section IV of the paper Total Variation Distance and the Distribution of Relative Information states some lower bounds on total variation in terms of KL divergence, which may be helpful as KL divergence of normal variables has a closed form.

Answer 3

Here's another comment. I'm assuming the gaussians are mean 0. If you pick some linear combination of the gaussians, you get in each of cases 1 and 2 a mean 0 gaussian with a variance depending on the covariance matrix entries. A lower bound on the variation distance between these univariate gaussians is a lower bound on the variation distance between the multivariate gaussians. This doesn't seem too tough. Is it the approach that was problematic?

Answer 4

Suppose entry $i,j$ differs by $\delta$. For one of $X_i$, or $X_j$, or $X_i+X_j$, the variance differs by at least $\delta/2$ under the two measures, which brings the problem to the 1 dimensional case, which is easy.