Независимое время, чтобы обеспечить минимальное сокращение графика, по крайней мере, одно испытание успешно

Question

Я только что закончил с первым модулем в курсе специализации algo в Coursera.

Был экзаменационный вопрос, который я не мог понять. Я сдал этот экзамен, поэтому нет смысла его сдавать.

Из любопытства я хочу изучить принципы этого вопроса.

Вопрос был опубликован как таковой:

Предположим, что рандомизированный алгоритм успешно (например, правильно вычисляет минимальный срез графа) с вероятностью p (с 0

Сколько независимых раз вам нужно запустить алгоритм, чтобы гарантировать, что с вероятностью не менее 1 - ϵ, по крайней мере, одно испытание успешно?

Варианты были следующими:

Журнал (1-р)/log & epsi;

лог (р)/log & epsi;

log & epsi; / журнал (р)

log & epsi; / журнал (1-р)

Я сделал две попытки, и обе были не правы. Мои попытки были:

1. Журнал (1-р)/log & epsi;
2. log & epsi; / журнал (1-р)

Это не так много, я хочу знать правильный ответ. Я хочу узнать принципы, лежащие в основе этого вопроса и что он просит. Так что я знаю, как ответить на подобные вопросы в будущем.

Я разместил это на форуме, но никто не ответил через месяц. Так что я пробую это здесь.

Нет необходимости размещать ответ напрямую. Если вы дадите мне время, я отмечу это как правильное.

Благодарю.

Answer 1

Сколько независимых раз вам нужно запустить алгоритм, чтобы гарантировать, что с вероятностью не менее 1 - ϵ, по крайней мере, одно испытание успешно?

Давайте перефразируем это немного:

Каково наименьшее количество независимых испытаний, чтобы вероятность их неудачного завершения была меньше или равна ϵ?

По определению независимых событий вероятность их возникновения является произведением их индивидуальных вероятностей. Поскольку вероятность неудачного проведения одного испытания (1-p)вероятность n Испытания провал (1-p)^n,

Это дает нам неравенство для n:

(1-p)^n <= ϵ