эксперимент

[a_shen]

Тут недавно обсуждалась (простая) задача по теории вероятностей - просьба к читателям, изучавшим эту науку, потратить минуту или две и написать в комментарии, как они её решали бы и насколько эта задача, по их мнению, лёгкая.

Есть вероятностный алгоритм, который для простого числа всегда говорит, что оно простое, а для составного числа говорит, что оно составное в 90% случаев. (Реальные алгоритмы действуют лучше, и не одинаково для всех составных чисел, но примем такую условность и предположим, что рассматриваемый алгоритм действительно таков.) Некто хочет найти 1000-битовое простое число так: выбирает случайные 1000 битов бросанием монеты и проверяет, не получилось ли простое число по этому алгоритму, при этом делает две проверки для повышения надёжности (пока не найдётся число, которое дважды будет названо простым этим алгоритмом). Какова вероятность, что первое найденное им число действительно окажется простым?

(Для чистоты эксперимента комментарии вначале скрываются - потом будут открыты)

Comments

[p-k-zombie.livejournal.com]

Имея в виду, что плотность простых чисел падает как обратный логарифм, вероятность того что случайно выбранное 1000-битное число простое - q=1/(1000*ln(2))=0.00144. Если случайно выбранное число прошло тест, то либо оно было простое (исходная вероятность q), либо было пропущено по ошибке (исходная вероятность (1-q)*0.01). Таким образом доля простых чисел среди прошедших тест равна q/(q+(1-q)*0.01)=0.126.