2
$\begingroup$

Let $X_1, X_2, \ldots$ be independent and identically distributed random variables with mean $0$ and variance $1$ and let $S_n = (X_1 + \cdots + X_n)/\sqrt{n}$ to be their normalized sum. Define $D_n$ to the total variation (TV) distance between $S_n$ and a standard Gaussian.

Question: Is $D_n$ always monotonic decreasing?

This is similar to the well known Shannon monotonicity of entropy problem which states that the entropy of $S_n$ is monotonic increasing.

Intuitively, the conjecture might be true since visually, I cannot imagine a case where the TV distance ever decreases. Furthermore, the upper bound for TV distance from Pinsker's inequality does derease monotonically (proof sketch: decompose KL divergence as a - entropy term + constant term and the first follows from the Shannon problem.)

Any references, counter examples, or discussions would be appreciated.

$\endgroup$
3
  • 1
    $\begingroup$ What is the motivation behind the question? TV seems to be a rather useless distance here. For example, if the random variables are discrete, the distance will always be maximal for all $n$. $\endgroup$ Feb 9, 2021 at 15:05
  • 1
    $\begingroup$ The same motivations as studying the entropy question applies. Also, TV is a natural distance between distributions and it would be interesting to understand TV distance in terms of entropy. For comparisons to discrete distributions, we can just use the l1 difference between the densities as our definition and that produces a meaningful quantity. $\endgroup$ Feb 9, 2021 at 16:29
  • 1
    $\begingroup$ In different contexts you can multiply the difference in distributions by a suitable convolution operator, taking something like the distribution of $S_N$ to the distribution of $S_{N+1}$ but fixing the distribution of the Gaussian. Then you use operator-type ideas to show this convolution operator is norm one and so you are done. $\endgroup$ Feb 9, 2021 at 19:53

1 Answer 1

2
$\begingroup$

Unless I made a mistake, this is not true.

Take the random variable $X$ to be $M$ with probability $\epsilon$, $-M$ with probability $-\epsilon$, and distributed as $N(0, \frac{ 1- 2 \epsilon M^2}{ 1-2\epsilon} )$ with probability $1-2\epsilon$. Here we take $M$ very large and $\epsilon M^2$ somewhat small, for instance $\epsilon = M^{-3}$.

The total variation distance is $$\int_{-\infty}^{\infty} \max \left( \frac{ e^{ - x^2/2}}{\sqrt{2\pi}}- (1-2\epsilon)\frac{ e^{ - x^2 (1-2\epsilon) / (1-2 \epsilon M^2)} }{\sqrt{ 2\pi (1- 2 \epsilon m^2)/ (1-2\epsilon)}} , 0 \right) dx $$

since the spikes at $-M$ and $M$ don't contribute.

Now the distribution of $(X_1 + X_2)/\sqrt{2}$ is

  • $N(0, \frac{ 1- 2 \epsilon M^2}{ 1-\epsilon} )$ with probability $(1-2 \epsilon)^2$
  • $N(M/\sqrt{2}, \frac{ 1- 2 \epsilon M^2}{ 2 -2 \epsilon } )$, with probability $2 \epsilon (1-2\epsilon)$
  • $N(-M/\sqrt{2}, \frac{ 1- 2 \epsilon M^2}{ 2 -2 \epsilon } )$
  • $\sqrt{2} M$ with probability $\epsilon^2$
  • $0$ with probaiblity $2\epsilon^2$
  • $-\sqrt{2} M$ with probability $\epsilon^2$

The last three are peaks and don't contribute to the total variation distance. The two shifted Gaussians are supported around $M/\sqrt{2}$, with exponential error, and thus contribute an amount exponentially small in $M$ to the total variation distance. So the total variation distance is

The total variation distance is $$\int_{-\infty}^{\infty} \max \left( \frac{ e^{ - x^2/2}}{\sqrt{2\pi}}- (1-2\epsilon)^2\frac{ e^{ - x^2 (1-2\epsilon) / (1-2 \epsilon M^2)} }{\sqrt{ 2\pi (1- 2 \epsilon m^2)/ (1-2\epsilon)}} , 0 \right) dx $$

plus a term exponentially small in $M$. This integral is greater than the integral above by a factor linear in $\epsilon$, which has size $M^{-3}$, which is much larger than the exponentially small factor factor, so the total variation distance is larger than the previous case.

$\endgroup$
1
  • $\begingroup$ Thanks for the detailed answer! $\endgroup$ Feb 11, 2021 at 1:04

Your Answer

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

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