Когда алгоритм Monte Carlo решает проблему?

Question

Когда мы можем сказать, что алгоритм Monte Carlo решает проблему?

Цитировать из Wikipedia на алгоритмах Монте-Карло

Например, тест соловай-страженской просьбы используется для определения того, является ли данный номер простым числом.Это всегда отвечает на True для входов простых номеров;Для композитных входов он отвечает ложно с вероятностью, по меньшей мере, ½ и true с вероятностью менее ½.

Что произойдет, если бы тест соловай-страженской ответ отвечал, что только для 1% композитных входов?

тогда мы все еще говорим, что это решает проблему тестирования главной?

Или есть ли такое требование, такое, что алгоритм Monte Carlo должен ответить на True для более чем половины случаев?

Answer 1

В общем Monte Carlo используется для решения широкого спектра различных видов проблем. В этом конкретном случае вы хотите узнать, является ли случайная переменная константой 1 или нет. Идея проста, образец случайной величины несколько раз, (каждый образец независимо от предыдущего образца, чтобы избежать смещения) и проверять, были ли все результаты 1. Если хотя бы некоторые из результатов было 0, мы точно знаем, что случайная переменная Константа 1 (в контексте прозрачности Соловай-страженна число композит).

Важно подчеркнуть, поскольку Monte Carlo является рандомизированным алгоритмом, что, как говорят, решает проблему, если вероятность возврата неправильного ответа ниже некоторого порога (небольшое число, которое мы позвоним $ \ epsilon $ ).

Что произойдет, если все результаты были 1? Есть вероятность, что это постоянная 1, но и есть вероятность, что нам не повезло, и все результаты были 1, когда они также могут быть 0. Если вероятность отбора проб A 1 - $ p <1 $ , затем после $ n $ Образцы Вероятность получения всего 1 - $ p_n= p ^ n $ . Обратите внимание, что, хотя $ n $ Увеличение $ p_n \ prightarrow 0 $ . Мы можем указать порог, давайте скажем, $ \ Epsilon= 10 ^ {- 10} $ , так что если $ p_n < \ epsilon $ (т.е. вероятность того, что наличие ложного положительного положения меньше, чем $ \ epsilon $ ) Мы в порядке с этим результатом.

---

Теперь ответ на ваш вопрос. $ \ forall p <1, \ epsilon> 0 \ space \ Существует n \ space p ^ n <\ epsilon $ . Что это точно говорит вам?

Независимо от вероятности успеха, насколько он меньше, чем $ 1 $ (например, $ P= 0,99 $ или $ p= 0,01 $ или $ p= 0,5 $ ) и порог $ \ epsilon $ существует $ n $ такое, что если мы запустим эксперимент $ n $ times (образец $ n $ Times Случайная переменная независимо) Мы собираемся потерпеть неудачу с вероятностью в большей степени $ \ epsilon $ . Таким образом, Monte Carlo может быть применен для не вырожденных значений $ p $ , только номер $ n $ Образец необходимо отрегулировать, чтобы удовлетворить $ \ epsilon $ Пороговое требование.