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

#### Лемма 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
$$Copy