Statistical distance between uniform and biased coin

Question

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$?

Answer 1

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})$.

Answer 2

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.