165
правок
Изменения
→Вероятность существования единственного удовлетворяющего набора
#Следовательно, всего имеется не менее <tex>2^i n \cdot D \ge 2^{2i-1}n</tex> искомых отличающих пар. В данной оценке мы использовали равенство из второго пункта.
#Таким образом, вероятность выбрать отличающую пару чисел (<tex>p_l</tex>, <tex>r_l</tex>) составляет не менее <tex>\frac{2^{2i-1}n}{16\cdot2^{2i}n^4}=\frac{1}{32n^3}</tex>.
#Домножая полученную вероятность на вероятность выбрать подходящее <tex>i</tex> (см. второй пункт), получим, что вероятность ошибочного верного построения формулы <tex>\phi_k</tex> составляет <tex>1-\frac{1}{32n^3(n+1)}</tex>.
Составив набор {<tex>\phi_1 \ldots \phi_m</tex>} из ''O''(''n''<sup>4</sup>) формул, каждый раз выбирая тройку (<tex>i</tex>, <tex>p_i</tex>, <tex>r_i</tex>) чисел случайным образом, получим константную вероятность ошибки. Таким образом необходимый набор формул построен, а теорема доказана.
