Вероятностное усиление для рандомизированного алгоритма

Question

Я пропустил лекцию о рандомизированных алгоритмах и не могу обернуть голову вокруг усиления вероятности алгоритма двусторонней ошибки.

Может кто-нибудь объяснить, почему вероятность того, что следующий алгоритм дает правильный выходной сигнал, увеличивается черезповторение и как можно рассчитать эту вероятность?

L является формальным языком
Если входной сигнал x ∈ L, выходной сигнал алгоритма будет ДА ​​с вероятностью 2/3
Есливход x! ∈ L, выход алгоритма будет НЕТ с вероятностью> 1/2

Заранее спасибо

Answer 1

Вам нужно прикольное правило принятия решения, чтобы взломать это.Выполните алгоритм n раз, и если по крайней мере 7/12 (= на полпути между 1/2 и 2/3) дроби выходов - ДА, выведите ДА.

Выровненное вручную выражениечто для каждого входа NO ожидаемая доля выходов YES сходится по закону больших чисел не более чем на 1/2, а для каждого входа YES ожидаемая доля выходов YES сходится как минимум до 2/3.Формально мы должны вызвать неравенство Хеффдинга или что-то эквивалентное, что показывает, что вероятность ошибки уменьшается как O(exp(-cn)) для некоторой фиксированной константы c.