![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
итоги эксперимента:
0) решение: при одном выборе вероятность выбрать простое равна p (доле простых чисел среди 1000-битовых), а вероятность выбрать составное равна (1-p)*0.1^2. Дальше можно суммировать геометрическую прогрессию или сослаться на общий факт: если мы вибираем из урны носок, пока не выберем красный или зелёный, и таковые вообще есть, то вероятность выбрать в итоге выбрать красный равна доле красных среди красных-или-зелёных: отношение вероятностей выбрать красный и выбрать зеленый на любом шаге одно и то же, поэтому и в сумме одно и то же. Чтобы оценить p, можно воспользоваться теоремой о распределении простых чисел (это примерно 1/ln 2^{1000}).
1) большинство комментаторов в ловушку не попалось, я всё-таки подозреваю, что отчасти потому, что они были настороже - к чему бы такое спрашивают? Наверно, более провокационный вариант был бы такой: Вася выбрал наугад 1000-битовое число, проверил его вероятностным алгоритмом дважды и теперь спорит, что оно простое, ставя 10 против 1. Выгоден ли для него этот спор?
2) в условии вызывает трудность сама формулировка о вероятности разоблачить непростоту с помощью вероятностного алгоритма: хотя я и пытался написать яснее, но всё равно это можно понимать как то, что вероятность берётся не по случайным битам алгоритма для любого входа, а по случайным входам.
3) интересно, что многие решавшие суммируют геометрическую прогрессию, а не говорят (интуитивно или обоснованно), что это просто условная вероятность получить простое число при условии получить что-то при одном испытании
0) решение: при одном выборе вероятность выбрать простое равна p (доле простых чисел среди 1000-битовых), а вероятность выбрать составное равна (1-p)*0.1^2. Дальше можно суммировать геометрическую прогрессию или сослаться на общий факт: если мы вибираем из урны носок, пока не выберем красный или зелёный, и таковые вообще есть, то вероятность выбрать в итоге выбрать красный равна доле красных среди красных-или-зелёных: отношение вероятностей выбрать красный и выбрать зеленый на любом шаге одно и то же, поэтому и в сумме одно и то же. Чтобы оценить p, можно воспользоваться теоремой о распределении простых чисел (это примерно 1/ln 2^{1000}).
1) большинство комментаторов в ловушку не попалось, я всё-таки подозреваю, что отчасти потому, что они были настороже - к чему бы такое спрашивают? Наверно, более провокационный вариант был бы такой: Вася выбрал наугад 1000-битовое число, проверил его вероятностным алгоритмом дважды и теперь спорит, что оно простое, ставя 10 против 1. Выгоден ли для него этот спор?
2) в условии вызывает трудность сама формулировка о вероятности разоблачить непростоту с помощью вероятностного алгоритма: хотя я и пытался написать яснее, но всё равно это можно понимать как то, что вероятность берётся не по случайным битам алгоритма для любого входа, а по случайным входам.
3) интересно, что многие решавшие суммируют геометрическую прогрессию, а не говорят (интуитивно или обоснованно), что это просто условная вероятность получить простое число при условии получить что-то при одном испытании
