Свойства рандомизированных алгоритмов (Монте-Карло, Лас-Вегас)

Question

Я сам сейчас изучаю алгоритмы Лас-Вегаса и Монте-Карло, и у меня есть два вопроса, которые могут быть простыми, но я не могу ответить на них, если кто-то может мне помочь ... Заранее спасибо

1. Рассмотрим алгоритмы Монте-Карло A для задачи P, ожидаемое время выполнения которой не более T (n) для любого экземпляра размера n, который дает правильное решение с вероятностью y (n). Предположим далее, что, учитывая решение P, мы можем проверить его правильность за время t (n). Покажите, как получить алгоритм Лас-Вегаса, который всегда дает правильный ответ на P и работает в ожидаемое время самое большее (T (n) + t (n)) / y (n).

2. Пусть 0 <ε2 <ε1 <1. Рассмотрим алгоритм Монте-Карло, который дает правильное решение задачи с вероятностью не менее 1-ε1 независимо от входных данных. Сколько независимых выполнений этого алгоритма достаточно, чтобы повысить вероятность получения правильного решения по крайней мере 1-ε2, независимо от ввода? </p>

Answer 1

1. Просто повторите запуск алгоритма и проверяйте результат, пока не получите правильный ответ.Каждый прогон и проверка занимает (T (n) + t (n)) единиц времени, а количество прогонов представляет собой геометрическую случайную величину со средним значением 1 / y (n).* Какова вероятность отказа за один прогон?Для двух запусков?н работает?Установите вероятность неудачи для n прогонов, равную e2, и решите для n.