Статистическое расстояние между униформой и смещенной монетой

Пусть будет равномерным распределением по битам, и пусть будет распределением по битам, где биты независимы, и каждый бит равен с вероятностью . Правда ли, что статистическое расстояние между и равно , когда ?$U$$n$$D$$n$$1$$1/2-\epsilon$$D$$U$$\Omega(\epsilon \sqrt{n})$$n \le 1/\epsilon^2$

Обозначим случайные биты через . По определению, статистическое расстояние между и составляет не менее для каждого t . Мы выбираем t = n / 2 + \ sqrt {n} .$x_1,\dots, x_n$$U$$D$$\Pr_U\left(\sum x_i \geq t\right) - \Pr_D\left(\sum x_i \geq t\right)$$t$$t = n/2 + \sqrt{n}$

Обратите внимание, что для некоторой абсолютной константы . Если , то статистическое расстояние составляет не менее , и мы закончили. Поэтому ниже мы предполагаем, что .$\Pr_U\left(\sum x_i \geq t\right) \geq c_1$$c_1 > 0$$\Pr_D\left(\sum x_i \geq t\right) \leq c_1/2$$c_1/2$$\Pr_D\left(\sum x_i \geq t\right) \geq c_1/2$

Пусть для случайных переменных Бернулли с . Наша цель - доказать, что . По теореме о среднем значении для некоторого . Теперь мы докажем, что ; это будет означать, что требуемое статистическое расстояние составляет не менее , как требуется.$f(s) = \Pr\left(\sum x_i \geq t\right)$$x_1,\dots, x_n$$\Pr(x_i = 1) = 1/2-s$$f(0) - f(\varepsilon) = \Omega(\varepsilon \sqrt{n})$

$$f(0) - f(\varepsilon) = -\varepsilon f'(\xi),$$ $\xi \in (0, \varepsilon)$$-f'(\xi) \geq \Omega(\sqrt{n})$$\Omega(\sqrt{n} \varepsilon)$

Напишите, и Обратите внимание, что Таким образом,

$$f(\xi) = \sum_{k\geq t} \binom{n}{k} \left(\frac12 - \xi\right)^k \left(\frac12+\xi\right)^{n-k},$$ $$\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}$$ $$\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}.$$ $$\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}$$ Здесь мы использовали предположение, что . Мы показали, что .$f(\varepsilon) = \Pr_D(x_1+\dots+x_n \geq t) \geq c_1/2$$-f'(\xi) = \Omega(\sqrt{n})$

Несколько более элементарное и немного грязное доказательство (или, по крайней мере, мне так кажется).

Для удобства напишите с в предположении.$\varepsilon = \frac{\gamma}{\sqrt{n}}$$\gamma\in [0,1)$

Мы явно опускаем нижнюю границу выражения : $\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*}$$ где - абсолютная константа. Мы понижаем границу каждого слагаемого отдельно: фиксируем и пишем , так что каждое слагаемое снизу ограничено величиной, сходящейся (когда ) в$C>0$$k$$\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*}$$ $n\to \infty$$e^{4\gamma -2\gamma ^2}-1 > 4\gamma -2\gamma ^2 > 2\gamma$ ; подразумевая, что каждый является . Подводя итог, это приводит к как заявлено.$\Omega(\gamma )$ $$\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*}$$