3
$\begingroup$

Problem setup

Let $X$ and $Y$ random variables on the real line with following properties:

  • $X$ and $Y$ are $\sigma^2$ sub-gaussian
  • $E[X] = 0$
  • and $E[Y] = \Delta$.

Question

Whats the lower bound on total variation distance between $X$ and $Y$?

Let: $$ \big|\big|X-Y\big|\big|_{TV} \geq f(\sigma,\Delta) $$

What is $f(\sigma,\Delta)$? Are there any known (or trivial) lower bounds in the literature?

Few obvious properties $f(\sigma,\Delta)$ satisfy :

  1. $f$ decreases as $\sigma$ increases (fixed $\Delta$).
  2. $f$ increases as $\Delta$ increases (fixed $\sigma$).
$\endgroup$
2
  • $\begingroup$ Are $X,Y$ assumed to be independent? $\endgroup$
    – Alex R.
    Commented Apr 11, 2016 at 22:11
  • $\begingroup$ Alex: No independence assumptions. $\endgroup$ Commented Apr 14, 2016 at 6:55

2 Answers 2

3
$\begingroup$

Sub-Gaussianity is an asymptotic property whereas expectations and the total variation are global properties. Provided the tails of the distribution are not too heavy (and any sub-Gaussian distribution has very light tails indeed), they will have negligible effect on those global properties. Thus we may modify any sub-Gaussian variable $X$ just a tiny bit (in probability) by mixing in a point mass far out from its mean without harming its asymptotic tail behavior. Although this is a short total variation distance, it's an arbitrarily large difference in means. Thus the only possible lower bound is zero.

The following is a rigorous version of this argument. It improves on an earlier answer in that it applies more widely, requires less detailed analysis, and perhaps offers more insight into the interactions between fundamental operations (truncation and mixing) and the total variation distance.


Preliminaries

The key ideas are embodied in the properties of two operations on random variables. To describe them, let's begin with some terminology and definitions.

  • Let $X$ be a random variable with distribution function $F$ and let $N$ be any number. The "tail probability" (of $X$ beyond $N$) is the chance that $X$ exceeds $N$,

    $$\Pr(|X| \gt N) = \Pr(X \notin [-N,N]) = F(N) - \lim_{\varepsilon \to 0^{+}} F(-N-\varepsilon).$$

    Let's call this quantity $e_F(N)$. It equals $1$ for negative values of $N$ and eventually decreases asymptotically toward $0$ as $N$ increases. (It is the survival function of $|X|$.)

  • The total variation distance between two random variables $X$ and $Y$ is the total variation distance between their probability distributions,

    $$||X-Y||_{TV} = \sup_{A\subset \mathcal{F}}\left| \Pr(X\in A) - \Pr(Y \in A) \right|.$$

    $\mathcal{F}$ is the sigma-algebra of Borel sets.

  • Although specific definitions appear to vary slightly, to say that $X$ is "sub-Gaussian" means its tails are no heavier than some Gaussian function $t\to C \exp(-\sigma^2 (t-\mu)^2)$. That immediately implies sub-Gaussian variables have finite expectations, because the expectation of $|X|$ is bounded above by the integral of $C \exp(-\sigma^2 (t-\mu)^2)$, which is finite.

Truncation

Suppose $N$ is large enough to make $\Pr(X \in [-N, N])$ nonzero. We may truncate $X$ at $N$ by removing all chance that it exceeds $N$. The value of the new distribution function at $x$ is $0$ for $x \lt -N$, $1$ for $x \ge N$, and otherwise equals

$$F_{[N]}(x) = \frac{F(x) - \lim_{\varepsilon \to 0^{+}} F(-N-\varepsilon)}{1-e_F(N)}.$$

When we truncate $X$ at $N$, we remove a total probability of $e_F(N)$ from the tails of $X$ and, to compensate, uniformly divide all probabilities in the interval $[-N,N]$ by $1-e_F(N)$. Therefore the most that the probability can change is $e_F(N)$ (and in fact that much change occurs for $A=[-N,N]$). Consequently

$$||X - X_{[N]}||_{TV} = e_F(N).$$

Changing the mean

Let $0 \lt p \lt 1$ and $\Delta$ be any number, the amount by which we wish to shift the mean of $X$. One way to accomplish this shift is to form a mixture with an atomic variable. Its distribution function is

$$F_{\Delta,p}(x) = \cases{(1-p) F(x), \quad\quad x\lt (\Delta-\mathbb{E}(X))/p \\ (1-p)F(x) + p \ \text{ otherwise.}}.$$

This moves a total probability of $p$, spread throughout the range of $X$, onto a single value. When that value is $\Delta/p$ away from the mean of $X$, the mean is shifted by $\Delta$. Let $Y$ be a random variable with this mixture distribution. Because the probability of no event changes by any more than $p$,

$$||X - Y||_{TV} \le p.$$

Let's say that $Y$ has been attained by means of a $p$-mixture with $X$.


Solution

Let $X$ be any random variable with finite expectation.

Let $\varepsilon \gt 0$. Pick an $N$ for which $e_F(N) \le \varepsilon/2$ and truncate $X$ at $N$. Now shift the mean of $X_{[N]}$ to $\Delta$ using an $\varepsilon/2$-mixture. As we have seen, such a shift changes the total variation distance by at most $\varepsilon/2$. Therefore, by the triangle inequality,

$$||X - Y||_{TV} \le ||X - X_{[N]}||_{TV} + ||X_{[N]} - Y||_{TV} \le \varepsilon/2 + \varepsilon/2 = \varepsilon.$$

We have shown that provided $X$ has finite expectation, there is always a way to truncate $X$ and shift its mean to $\Delta$, no matter what value $\Delta$ might have, without moving by more than $\varepsilon$ in the total variation distance.

These constructions put an upper bound on $|Y|$: it is no greater than the larger of $N$ or the absolute value of the position of the atom located at $2(\Delta - \mathbb{E}(X))/\varepsilon$. Consequently the tails of $Y$ are zero, which makes them sub-Gaussian.

Since $\varepsilon$ can be arbitrarily small, the only possible lower bound on the distance is zero.


Conclusion

We have shown how to modify any finite-expectation random variable $X$ into a bounded variable $Y$ with mean $\mathbb{E}(X)+\Delta$ in such a way that the total variation distance between $X$ and $Y$ is arbitrarily small. As a special case, when $X$ is a zero-mean $\sigma^2$ sub-Gaussian (whatever that might specifically mean), then $Y$ is $\sigma^2$ sub-Gaussian with mean $\Delta$. This demonstrates the lower bound on $||X - Y||$ is zero, QED.

$\endgroup$
5
  • $\begingroup$ :Great answer! Shouldn't the sub gaussianity condition for $Y$ be $Pr(|Y-\Delta| >t ) \leq C' exp(-\sigma^2t^2)$? I wanted(meant) $Y$ to have gaussian "level" concentration around its mean. $\endgroup$ Commented Apr 12, 2016 at 4:35
  • 1
    $\begingroup$ That's a natural definition of sub-Gaussian. Dealing with it requires a slightly different technique. I have therefore modified the answer so it applies very broadly, certainly covering any conceivable definition of sub-Gaussian you would like to use. $\endgroup$
    – whuber
    Commented Apr 13, 2016 at 15:38
  • $\begingroup$ whuber: In the above construction $Y$ is sub-gaussian because it was truncated. The reason one assumes their variables to be sub-gaussian is because they want it to have gaussian-like concentration results. In the above construction, the $C'$ parameter of $Y$ is too large (and hence the concentration limits are bad). a) What if we limit $C'$ to $2$ or b) What if constrain the variance of $X$ and $Y$ to be lesser than $\sigma^2$ instead of constraining them to be $\sigma^2-$ sub-gaussian? $\endgroup$ Commented Apr 15, 2016 at 5:00
  • $\begingroup$ Using exactly the same construction you can modify $Y$ to have any kind of tails you want. Limit their total probability to $\epsilon/3$ and use $\epsilon/3$ instead of $\epsilon/2$ in the argument. If you want to constrain $C$ or the variance then the problem completely changes. $\endgroup$
    – whuber
    Commented Apr 15, 2016 at 13:58
  • 1
    $\begingroup$ This is one of best piece of mathematics I've read in a while. Simple ideas, but very powerful. $\endgroup$
    – dohmatob
    Commented Jan 29, 2020 at 14:11
1
$\begingroup$

Here is a possible approach to a modified version of the above problem. The modification preserves the motivation of the original problem.

Modification - $X$ and $Y$ are constrained to have $\sigma^2$ variance instead of being $\sigma^2$ sub-gaussian.

Let $E[X] = -\Delta$ and $E[Y] = \Delta $ \begin{eqnarray} \Big(\int_z z\big(p_X(z)- p_Y(z)\big)dz \Big)^2 &\leq& \Big(\int_z \big|z\big|\big|\;p_X(z)- p_Y(z)\;\big|dz \Big)^2\\ &=& \Big(\int_z \big|z\big|\sqrt{\big|\;p_X(z)- p_Y(z)\;\big|}\sqrt{\big|\;p_X(z)- p_Y(z)\;\big|}dz \Big)^2 \\ &&\leq \Big(\int_z z^2\big|\;p_X(z)- p_Y(z)\;\big|dz \int_z \big|\;p_X(z)- p_Y(z)\;\big|dz \Big)\\ &&\overset{(a)}{\leq}\Big(\int_z z^2\big(p_X(z)+p_Y(z)\big)dz \int_z \big|\;p_X(z)- p_Y(z)\;\big|dz \Big)\\ &&\overset{(b)}{\leq} \Big(2\big(\sigma^2+\Delta^2\big) \int_z \big|\;p_X(z)- p_Y(z)\;\big|dz \Big)\\ &&=\Big(2\big(\sigma^2+\Delta^2\big) 2\big|\big|\;p_X(z)- p_Y(z)\;\big|\big|_{TV}\Big)\\ \end{eqnarray}

Re-writting the above

$\big|\big|\;p_X(z)- p_Y(z)\;\big|\big|_{TV} \geq \frac{\Big(\int_z z\big(p_X(z)- p_Y(z)\big)dz \Big)^2}{4(\sigma^2+\Delta^2)} \overset{(c)}{\geq} \frac{4\Delta^2}{4(\sigma^2+\Delta^2)} {\geq} \frac{\Delta^2}{\sigma^2+\Delta^2} $

(a): $|a-b| \leq a+b$, when both $a$ and $b$ are positive.

(b): Because $Var(X), Var(Y) \leq \sigma^2 $ and $E[X]^2 = E[Y]^2 = \Delta^2$

(c): Because $E[X] = -\Delta, E[Y] = \Delta$

Note: Solving the above problem as a convex optimization problem might lead to better bounds.

Any ideas are appreciated and thanks in advance!

$\endgroup$

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.