Лемма о получении генератора из перестановки

Лемма 2

$\beta(x)$ - трудный бит для $f(x) \Leftrightarrow x \mapsto f(x)\beta(x)$ - генератор.

Доказательство

$\Leftarrow$
$\beta$ можно угадать $\Rightarrow$ $f(x)\beta(x)$ можно отличить от $y$.
$D_n(y) = (C_n(y \mid_{1 \ldots n}) \leftrightarrow y_{n + 1})$
$y$ случайное $\Rightarrow$ $D_n$ угадывает с вероятностью $\frac{1}{2}$.
$y = f(x)\beta(x) \Rightarrow D_n$ угадает с вероятностью $\frac{1}{2} + \frac{1}{p(n)}$

$\Rightarrow$
$f(x)\beta(x)$ умеем отличать от $y$ $\Rightarrow$ можно предсказать $\beta(x)$ по $f(x)$.
$y$ можно представить в виде $f(x)r$.

$$ \begin{array}{|cc|c|c|} \hline & & D(f(x)1) & D(f(x)1) \\ & & 0 & 1\\ \hline D(f(x)0) & 0 & \mathrm{random} & 1 \\ D(f(x)0) & 1 & 0 & \mathrm{random} \\ \hline \end{array} $$

Введем $p_0, p_1, q_0, q_1, r_0, r_1, s_0, s_1$ - вероятности в соответствующих условиях того, что $\beta(x) = 0$ и $\beta(x) = 1$.

Например: $r_1 = Pr\{\beta(x) = 1,\ D(f(x)0) = 1,\ D(f(x)1) = 0\}$.

$$Pr\{C_n(f(x)) = \beta(x)\} = \frac{1}{2}(p_0 + p_1) + q_1 + r_0 + \frac{1}{2}(s_0 + s_1) \boldsymbol{\circeq} \\ = Pr\{D(f(x)r) = 1\} = (s_0 + s_1) + \frac{1}{2}(r_0 + r_1) + \frac{1}{2}(q_0 + q_1) = Pr\{D(f(x)\beta(x)) = 1\} = \\ = (s_0 + s_1) + r_0 + q_1 = \frac{1}{2}(r_0 - r_1) + \frac{1}{2}(q_1 - q_0) > \varepsilon = \\ \boldsymbol{\circeq} \frac{1}{2}(p_0 + p_1) + \frac{1}{2}(q_1 + q_0) + \frac{1}{2}(r_0 + r_1) + \frac{1}{2}(r_0 - r_1) + \frac{1}{2}(s_0 + s_1) = \\ = \frac{1}{2} + \frac{1}{2}(q_1 - q_0) + \frac{1}{2}(r_0 - r_1) > \frac{1}{2} + \varepsilon $$