2
$\begingroup$

Let $P = N(\vec{0}, I^d)$ be a standard multivariate Gaussian distribution in $d$ dimensions. Let $Q$ be distributed the same as $P$, except that samples from $Q$ have one of their coordinates, chosen uniformly at random from $1$ to $d$, distributed as $N(\mu, \sigma^2)$ instead.

That is, $Q$ is a mixture of $d$ multivariate Gaussians, each with weight $\frac1d$. The $i$th mixture component has mean $\vec{0} + \vec{e}_i \cdot \mu$ and variance with diagonal $\vec{1} + \vec{e}_i \cdot (\sigma^2 - 1)$.

I'd like to bound the total variation distance between $P$ and $Q$, as a function of $d$ (when $\mu$ and $\sigma$ are constants that do not depend on $d$).

My intuition is that $Q$ is very close to a multivariate Gaussian $N(\frac{\vec{\mu}}{d}, I^d \cdot (1+\frac{\sigma^2}{d}+ o(\frac1d))$, which would give a Kullback–Leibler divergence of $D_{KL}(P || Q) = O(\frac1d)$ and thus a total variation distance of $O(\frac{1}{\sqrt d})$.

The case where $\sigma^2=1$ might be easier and sufficient for what I need. Any suggestions on how I could bound the TV distance between P and Q?

$\endgroup$
1
$\begingroup$

$\newcommand{\m}{\vec{\mu}} \newcommand{\e}{\vec{e}} \newcommand{\x}{\vec{x}}$ Let $n:=d$. Assume that $\sigma=1$ and $\mu\ne0$. Then for the densities \begin{equation*} f_Q(\x)=(2\pi)^{-n/2}\,\frac1n\,\sum_1^n e^{-|\x-\mu\e_i|^2/2} \end{equation*} and \begin{equation*} f_P(\x)=(2\pi)^{-n/2}\,e^{-|\x|^2/2} \end{equation*} of $P$ and $Q$ we have \begin{equation*} f_Q(\x)<f_P(\x)\iff \sum_1^n e^{\mu x_i}<ne^{\mu^2/2}, \end{equation*} where $\x=(x_1,\dots,x_n)\in\mathbb R^n$ and $|\cdot|$ denotes the Euclidean norm. Hence, \begin{equation*} d_{TV}(P,Q)=p_1-p_2, \tag{1} \end{equation*} where \begin{equation*} p_1:=P(S_n<ne^{\mu^2/2}),\quad p_2:=P(T_n<ne^{\mu^2/2}), \end{equation*} \begin{equation*} S_n:=\sum_1^n U_i,\quad T_n:=S_{n-1}+V_n, \end{equation*} \begin{equation*} U_i:=e^{\mu Z_i},\quad V_n:=e^{\mu(Z_n+\mu)}=e^{\mu^2}U_n, \end{equation*} and the $Z_i$'s are iid standard normal random variables. Note that \begin{equation*} ES_n=na,\quad ET_n=na+O(1),\quad Var\, S_n=nb^2,\quad Var\,T_n=nb^2+O(1), \end{equation*} where $a:=e^{\mu^2/2}$ and $b^2:=e^{2\mu^2}-e^{\mu^2}$. Also, $E|U_1|^3<\infty$. So, letting $\Phi$ denote the standard normal cumulative distribution function and using the Berry--Esseen inequality, we have \begin{equation*} p_1=P(S_n<na)=\Phi(0)+O(1/\sqrt n)=\frac12+O(1/\sqrt n) \end{equation*} and \begin{multline*} p_2=P(T_n<na)=\Phi\Big(\frac{na-ET_n}{\sqrt{Var\,T_n}}\Big)+O(1/\sqrt n) \\ =\Phi\Big(\frac{O(1)}{\sqrt{nb^2+O(1)}}\Big)+O(1/\sqrt n) =\frac12+O(1/\sqrt n) \end{multline*} Thus, by (1), we have \begin{equation*} d_{TV}(P,Q)=O(1/\sqrt n), \end{equation*} as conjectured.

$\endgroup$
  • $\begingroup$ Very nice! I'll try to go through a similar approach for the general case with $\sigma \neq 1$ (or does your approach crucially rely on $\sigma=1$ somewhere?). It also seems that the Berry--Esseen inequality should let us get an explicit (rather than asymptotic) result involving $\mu, \sigma$ and $1/\sqrt{n}$, right? $\endgroup$ – Florian Tramèr Mar 15 at 0:27
  • $\begingroup$ I think this should work for $\sigma\ne1$ too, but I have not gone through the details. $\endgroup$ – Iosif Pinelis Mar 15 at 2:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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