<p>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}$. </p>

<p>Note that $\Pr_U\left(\sum x_i \geq t\right) \geq c_1$ for some absolute constant $c_1 &gt; 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$.</p>

<p>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. </p>

<p>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) &amp;= \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) \\
&amp;= -\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) &amp;\geq 4\sqrt{n} \sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^{k} \left(\frac12+\xi\right)^{n-k} \\&amp;= 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})$.</p>

CC BY-SA 3.0
2016-09-05T01:01:28.287Z
2016-09-05T18:22:15.527Z
2016-09-05T18:22:15.527Z
Yury
<p><em>A somewhat more elementary, and slightly messier proof (or at least it feels so to me).</em></p>

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

<p>We explicitly lower bound the expression of $\operatorname{d}_{\rm TV}{(P,U)}$:
\begin{align*}
  2\operatorname{d}_{\rm TV}{(P,U)}
  &amp;= \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 \\
  &amp;= \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 \\
  &amp;\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 \\
  &amp;\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&gt;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}
  &amp;=  \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 \\
  &amp;\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 &gt; 4\gamma -2\gamma ^2 &gt; 2\gamma $; implying that each is $\Omega(\gamma )$. Summing up, this yields
\begin{align*}
  2\operatorname{d}_{\rm TV}{(P,U)} &amp;\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.</p>

CC BY-SA 3.0
2016-09-06T07:16:01.243Z
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.
usul
CC BY-SA 3.0
2016-09-06T02:02:31.653Z
(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.)
Clement C.
CC BY-SA 3.0
2016-09-06T01:57:43.160Z
2016-09-06T01:57:43.160Z
Clement C.
<p>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$?</p>

CC BY-SA 3.0
2016-09-03T00:16:16.083Z
Yes. The statistical distance between $U$ and $V$ is at least $\mathrm{Pr}_U(\sum x_i > n/2) - \mathrm{Pr}_D(\sum x_i > n/2)$, which is $\Omega(\varepsilon \sqrt{n})$; see e.g. the answer of matus here: http://cstheory.stackexchange.com/questions/14471/reverse-chernoff-bound
Yury
CC BY-SA 3.0
2016-09-03T10:38:29.023Z
Thanks. Perhaps explain how to get this from what matus wrote in an answer I can accept?
Manu
CC BY-SA 3.0
2016-09-03T21:15:53.670Z
Possibly useful: http://cstheory.stackexchange.com/q/22328/5038, http://stats.stackexchange.com/q/17405/2921.
D.W.
CC BY-SA 3.0
2016-09-04T16:15:22.613Z
Regarding Matus's answer, you can do better than Slud's inequality; see (2.13,2.14) in https://arxiv.org/abs/1606.08920
Aryeh
<pr.probability>
Statistical distance between uniform and biased coin
Manu
# Statistical distance between uniform and biased coin

(Asked by: username_0 on 2016-09-02)

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

**Tags:** pr.probability
> **Comments:**
> **username_1**: Yes. The statistical distance between $U$ and $V$ is at least $\mathrm{Pr}_U(\sum x_i > n/2) - \mathrm{Pr}_D(\sum x_i > n/2)$, which is $\Omega(\varepsilon \sqrt{n})$; see e.g. the answer of matus here: http://cstheory.stackexchange.com/questions/14471/reverse-chernoff-bound  
> **username_0**: Thanks. Perhaps explain how to get this from what matus wrote in an answer I can accept?  
> **username_2**: Possibly useful: http://cstheory.stackexchange.com/q/22328/5038, http://stats.stackexchange.com/q/17405/2921.  
> **username_3**: Regarding Matus's answer, you can do better than Slud's inequality; see (2.13,2.14) in https://arxiv.org/abs/1606.08920  

---

## 2 answers

### Answer by username_1 on 2016-09-05. Score: 7 | Accepted answer

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 by username_4 on 2016-09-06. Score: 5

*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.

> **Comments:**
> **username_4**: (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.)  
> **username_5**: 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.  

---

