Изменения

'''thenreturn''' <tex>f = f + 1</tex> '''else''' <tex>t = t + 1</tex> '''return''' <tex>f > t \ ? \ false : true0</tex>Если слово <tex>x \notin L</tex>, то <tex>m_{\mathrm{RP_{weak}}}(x)</tex> всегда возвращает <tex>false0</tex>. Тогда <tex>P(m_{\mathrm{RP}}(x) = 0) = 1</tex>, при <tex>x \notin L</tex>. <tex>k</tex> надо выбрать таким, что вероятность ошибки Если хотя бы один вызов программы <tex>m_{\mathrm{RPRP_{weak}}}(x)</tex> вернёт <tex>1</tex> при , то слово <tex>x \in L</tex> была меньше . Вероятность ошибки программы <tex>m_{\frac mathrm{1RP}{2}</tex>. Вероятность ошибки программы равна <tex>(1-\frac{1}{q(|x|)})^k</tex>, то есть программа <tex>m_{\mathrm{RP_{weak}}}</tex> ошиблась на всех вызовах. <tex>k</tex> надо выбрать таким, что вероятность ошибки программы <tex>m_{\mathrm{RP}}</tex> при <tex>x \in L</tex> была меньше <tex>\frac {1}{2}</tex>. Получается неравенство <tex>(1-\frac{1}{q(|x|)})^k < \frac{1}{2}</tex>. Логарифмируя, получаем: <tex>k\ ln(1-\frac{1}{q(|x|)}) < ln(\frac{1}{2})</tex>. Разложив логарифм в ряд Тейлора, получаем <tex>k(-\frac{1}{q(|x|)} + o(\frac{1}{q(|x|)})) < -ln(2)</tex>. Отсюда <tex>k > q(|x|)ln(2)</tex>.<br/>