9
$\begingroup$

Let $U$ be the uniform distribution over $n$ bits, and let $D$ be the distribution over $n$ bits where the bits are independent and each bit is $1$ with probability $1/2-\epsilon$. Is it true that the statistical distance between $D$ and $U$ is $\Omega(\epsilon \sqrt{n})$, when $n \le 1/\epsilon^2$?

$\endgroup$
7
$\begingroup$

Denote the random bits by $x_1,\dots, x_n$. By definition, the statistical distance between $U$ and $D$ is at least $\Pr_U\left(\sum x_i \geq t\right) - \Pr_D\left(\sum x_i \geq t\right)$ for every $t$. We choose $t = n/2 + \sqrt{n}$.

Note that $\Pr_U\left(\sum x_i \geq t\right) \geq c_1$ for some absolute constant $c_1 > 0$. If $\Pr_D\left(\sum x_i \geq t\right) \leq c_1/2$, then the statistical distance is at least $c_1/2$, and we are done. So we assume below that $\Pr_D\left(\sum x_i \geq t\right) \geq c_1/2$.

Let $f(s) = \Pr\left(\sum x_i \geq t\right)$ for i.i.d. Bernoulli random variables $x_1,\dots, x_n$ with $\Pr(x_i = 1) = 1/2-s$. Our goal is to prove that $f(0) - f(\varepsilon) = \Omega(\varepsilon \sqrt{n})$. By the mean value theorem, $$f(0) - f(\varepsilon) = -\varepsilon f'(\xi),$$ for some $\xi \in (0, \varepsilon)$. Now, we will prove that $-f'(\xi) \geq \Omega(\sqrt{n})$; that will imply that the desired statistical distance is at least $\Omega(\sqrt{n} \varepsilon)$, as required.

Write, $$f(\xi) = \sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^k \left(\frac12+\xi\right)^{n-k},$$ and $$\begin{align} f'(\xi) &= \sum_{k\geq t} \binom{n}{k} \left(-k \left(\frac12 - \xi\right)^{k-1} \left(\frac12+\xi\right)^{n-k} + (n-k) \left(\frac12 - \xi\right)^{k} \left(\frac12+\xi\right)^{n-k-1}\right) \\ &= -\sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^{k} \left(\frac12+\xi\right)^{n-k}\frac{k/2 + k\xi - (n-k)/2 + (n-k)\xi}{(1/2 - \xi)(1/2 +\xi)}. \end{align}$$ Note that $$\frac{k/2 + k\xi - (n-k)/2 + (n-k)\xi}{\left(1/2 - \xi\right)\left(1/2 +\xi\right)} = \frac{(2k-n)/2 + n\xi}{(1/2 - \xi)(1/2 +\xi)} \geq 2(2t - n) = 4\sqrt{n}.$$ Thus, $$\begin{align}-f'(\xi) &\geq 4\sqrt{n} \sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^{k} \left(\frac12+\xi\right)^{n-k} \\&= 4\sqrt{n} f(\xi) \geq 4\sqrt{n} f(\varepsilon) \geq 4\sqrt{n}\cdot (c_1/2).\end{align}$$ Here, we used the assumption that $f(\varepsilon) = \Pr_D(x_1+\dots+x_n \geq t) \geq c_1/2$. We showed that $-f'(\xi) = \Omega(\sqrt{n})$.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

A somewhat more elementary, and slightly messier proof (or at least it feels so to me).

For convenience, write $\varepsilon = \frac{\gamma}{\sqrt{n}}$, with $\gamma\in [0,1)$ by assumption.

We explicitly lower bound the expression of $\operatorname{d}_{\rm TV}{(P,U)}$: \begin{align*} 2\operatorname{d}_{\rm TV}{(P,U)} &= \sum_{x\in\{0,1\}^n} \left\lvert{ \left( \frac{1}{2} + \frac{\gamma }{\sqrt{n}} \right)^{\lvert{x}\rvert}\left( \frac{1}{2} - \frac{\gamma }{\sqrt{n}} \right)^{n-\lvert{x}\rvert} - \frac{1}{2^n} }\right\rvert \\ &= \frac{1}{2^n}\sum_{k=0}^n \binom{n}{k}\left\lvert{ \left( 1 + \frac{2\gamma }{\sqrt{n}} \right)^{k}\left( 1 - \frac{2\gamma }{\sqrt{n}} \right)^{n-k} - 1 }\right\rvert \\ &\geq \frac{1}{2^n}\sum_{k=\frac{n}{2}+\sqrt{n}}^{\frac{n}{2}+2\sqrt{n}} \binom{n}{k}\left\lvert{ \left( 1 + \frac{2\gamma }{\sqrt{n}} \right)^{k}\left( 1 - \frac{2\gamma }{\sqrt{n}} \right)^{n-k} - 1 }\right\rvert \\ &\geq \frac{C}{\sqrt{n}}\sum_{k=\frac{n}{2}+\sqrt{n}}^{\frac{n}{2}+2\sqrt{n}} \left\lvert{ \left( 1 + \frac{2\gamma }{\sqrt{n}} \right)^{k}\left( 1 - \frac{2\gamma }{\sqrt{n}} \right)^{n-k} - 1 } \right\rvert \end{align*} where $C>0$ is an absolute constant. We lower bound each summand separately: fixing $k$, and writing $\ell = k-\frac{n}{2} \in [\sqrt{n},2\sqrt{n}]$, \begin{align*} \left( 1 + \frac{2\gamma }{\sqrt{n}} \right)^{k}\left( 1 - \frac{2\gamma }{\sqrt{n}} \right)^{n-k} &= \left( 1 - \frac{4\gamma ^2}{n} \right)^{n/2}\left( \frac{1 + \frac{2\gamma }{\sqrt{n}}}{1 - \frac{2\gamma }{\sqrt{n}}}\right)^\ell \\ &\geq \left( 1 - \frac{4\gamma ^2}{n} \right)^{n/2}\left( \frac{1 + \frac{2\gamma }{\sqrt{n}}}{1 - \frac{2\gamma }{\sqrt{n}}}\right)^{\sqrt{n}} \xrightarrow[n\to\infty]{} e^{4\gamma -2\gamma ^2} \end{align*} so that each summand is lower bounded by a quantity that converges (when $n\to \infty$) to $e^{4\gamma -2\gamma ^2}-1 > 4\gamma -2\gamma ^2 > 2\gamma $; implying that each is $\Omega(\gamma )$. Summing up, this yields \begin{align*} 2\operatorname{d}_{\rm TV}{(P,U)} &\geq \frac{C}{\sqrt{n}}\sum_{k=\frac{n}{2}+\sqrt{n}}^{\frac{n}{2}+2\sqrt{n}} \Omega(\gamma ) = \Omega(\gamma) = \Omega(\varepsilon\sqrt{n}) \end{align*} as claimed.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ (Using Hellinger as a proxy because of its nice properties wrt product distributions is tempting, and would be much faster, but there would be a loss by a quadratic factor in the end lower bound.) $\endgroup$ – Clement C. Sep 6 '16 at 2:02
  • 1
    $\begingroup$ Nice! I like the elementary approach. We should be able to make it non-asymptotic in $n$ too.... one way is to use $\left(\frac{1+z}{1-z}\right)^{\sqrt{n}} \geq \left(1 + 2z\right)^{\sqrt{n}}$, then use the nice inequality $1+w \geq e^{w - w^2/2}$. A bit messier. $\endgroup$ – usul Sep 6 '16 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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