Изменения
→Доказательство
Выберем <tex>k</tex> так, чтобы <tex>2^{k-2} \le 2K \le 2^{k-1}</tex>.
Далее, <tex>h \in H_{m,k}</tex>; <tex>y \in 2^k</tex>. Отправляем запрос <tex>P</tex> на получение <tex>s \in S</tex>:
<tex>h(s) = y</tex>, и проверяем, верно ли в действительности, что <tex>s \in S</tex>.Пусть <tex>p = \frac{2K}{2^k}</tex>.* если <tex>|S| < K </tex> , то <tex>|h(s)| < \frac{p \cdot 2^k}{2} = K \Rightarrow P(</tex>успех<tex>) \le p/2</tex>.* если <tex>|S| > 2K</tex>, и <tex>|S| < 2^{k-1} </tex>, то поступим следующим образом. Мы хотим, чтобы выполнялось:
<tex>P_{h,y}(\exists s: h(s)=y) \ge \frac{3}{4} \cdot \frac{|s|}{2K}</tex>
Рассмотрим <tex>y \in 2^m</tex>. <tex>P_{h}(\exists s: h(s)=y) = P_{h}(y \in \bigcup \limits_{s}h(s)) = P_{h}(\bigcup \limits_{s}E_s) \ge \sum_{j}P(E_s) - \sum \limits_{s_1 \ne s_2}P(E_{s_1} \bigcap E_{s_2})= </tex>
