![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
a_shenитоги эксперимента:
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) интересно, что многие решавшие суммируют геометрическую прогрессию, а не говорят (интуитивно или обоснованно), что это просто условная вероятность получить простое число при условии получить что-то при одном испытании
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
какой-то Peter Donnelly предупредил
Date: 2015-12-01 10:46 am (UTC)Peter Donnelly: How juries are fooled by statistics
http://www.ted.com/talks/peter_donnelly_shows_how_stats_fool_juries
(Надо где-то с середины смотреть.)
no subject
Date: 2015-12-01 10:53 am (UTC)Зная последовательность проб и ошибок можно применить правило Байеса и посчитать вероятность числа оказаться простым как матожидание. Я почему-то думал, что задача именно об этом.
без сведений
Date: 2015-12-01 10:54 am (UTC)Re: без сведений
Date: 2015-12-01 11:26 am (UTC)no subject
Date: 2015-12-01 11:35 am (UTC)Re: какой-то Peter Donnelly предупредил
Date: 2015-12-01 01:45 pm (UTC)no subject
Date: 2015-12-01 05:09 pm (UTC)no subject
Date: 2015-12-01 09:28 pm (UTC)no subject
Date: 2015-12-02 03:09 am (UTC)no subject
Date: 2015-12-02 06:42 am (UTC)no subject
Date: 2015-12-02 06:44 am (UTC)no subject
Date: 2015-12-02 06:45 am (UTC)(frozen) no subject
Date: 2015-12-02 07:21 am (UTC)Объяснения про красное-зеленое слегка запутывают: про числа понятно, что если мы каждый раз генерим биты, то вероятность, что из ста бит мы сгенерим что-то(например, простое) = const. А алгоритм действует всегда одинаково и не учитывает резутьтаты наших прошлых проверок.
А с носками можно обходиться по-разному, складывать уже вытащенные в карман, либо обратно в урну, и тогда соотношение оставшихся в урне цветов будет меняться со временем (пока там есть носки разных цветов). Ну, и если мы будем оценивать цвет носков, которые складываем в карман вероятностно, то сможем запутать задачу еще сильнее.
собственно,
Date: 2015-12-02 08:40 am (UTC)ну да,
Date: 2015-12-02 08:41 am (UTC)думаю, что
Date: 2015-12-02 08:43 am (UTC)см выше
Date: 2015-12-02 08:44 am (UTC)(frozen) если носки
Date: 2015-12-02 08:45 am (UTC)(frozen) Re: если носки
Date: 2015-12-02 02:56 pm (UTC)например, мы знаем, что в урне было 2 носка, красный(простой) и зеленый(сложный). Мы вытащили зеленый, применили к нему алгоритм(нам повезло, алгоритм не записал его в "простые") и мы знаем, что он сложный, и убрали его в карман. Тогда, после такой процедуры, первый же носок(в урне остался один простой носок и мы знаем это наверняка), прошедий две проверки, окажется простым с вероятностью 100%.
Если бы первый же вытащенный носок прошел обе проверки, то вероятность, что он простой, была бы меньше, чем 100%.
А тк мы играем до первого носка, прошедшего обе проверки, то получается, что результат будет зависеть от правил игры: если возвращать носки в урну, то каким бы по счету не был первый-носок-прошедший-2-проверки, мы никогда не сможем сказать что "он простой с вер-ю 100%".
(frozen) Re: если носки
Date: 2015-12-02 04:33 pm (UTC)(frozen) Re: если носки
Date: 2015-12-04 08:19 pm (UTC)(frozen) Re: если носки
Date: 2015-12-05 09:02 am (UTC)(frozen) Re: если носки
Date: 2015-12-05 09:09 am (UTC)Кстати, я как-то не задумался раньше, что это за "вероятностный алгоритм" в условии задачи. @a_shen, этот алгоритнм одно и то же число может определить в один день, как простое, а в другой, как составное?
(frozen) Re: если носки
Date: 2015-12-05 09:13 am (UTC)2) В аналогии с красными и зелёными носками нельзя сказать, что красные носки соответствуют составным числам, а зелёные простым. Более формально надо говорить так, что у нас есть эксперимент с тремя исходами - a,b,c. Мы повторяем его независимо столько раз, пока не получится а или b. Какова вероятность, что получится a, а не b? Ответ: отношение вероятностей a и b. Исходы: выдано простое число, выдано составное, ошибочно объявленное простым, и ничего не выдано.
(frozen) Re: если носки
Date: 2015-12-05 09:20 am (UTC)То есть, в ситуации с носками, за "базовое" вероятностное пространство можно взять множество носков, а в случае с числами, надо брать декартово произведение множества чисел и множество возможных наборов "случайных битов", которые использует алгоритм.
(frozen) Re: если носки
Date: 2015-12-05 09:21 am (UTC)Если число составное -- алгоритм всегда говорит "составное"
(если мы нашли делитель -- оно составное, а если хорошо поискали и не нашли -- то, вероятно, что простое)
(frozen) Re: если носки
Date: 2015-12-05 09:22 am (UTC)(frozen) Re: если носки
Date: 2015-12-05 09:24 am (UTC)ps: просьба подписывать сообщения, следуя традиции этого журнала
(frozen) Re: если носки
Date: 2015-12-05 09:25 am (UTC)(frozen) Re: если носки
Date: 2015-12-05 09:27 am (UTC)Если "красный" и "зеленый" это не то же самое, что "простое" и "составное", а какие-то внутренние состояния -- тогда я совсем не понимаю, в чем смысл этого примера, и для чего он нужен, тк лично меня запутывает больше, чем условие задачи (пример с простыми/сложными числами, как минимум, не требует уточнений для решения)
(frozen) Re: если носки
Date: 2015-12-05 09:30 am (UTC)если алгоритм говорит, что число составное -- то оно составное.
если говорит, что число простое -- то оно может быть как простым, так и составным.
(frozen) Re: если носки
Date: 2015-12-05 09:32 am (UTC)если алгоритм говорит, что число составное -- то оно составное.
если говорит, что число простое -- то оно может быть как простым, так и составным.
(frozen) Re: если носки
Date: 2015-12-05 09:34 am (UTC)(frozen) Re: если носки
Date: 2015-12-05 09:37 am (UTC)если алгоритм говорит, что число составное -- то оно составное.
Это два разных утверждения.
Повторяю просьбу подписывать сообщения - на анонимные сообщения отвечать здесь не принято...
(frozen) Re: если носки
Date: 2015-12-05 09:40 am (UTC)Извиняюсь, не подумал, что это можно понять в другую сторону -- вроде идея про определение простоты совсем очевидная.
Re: думаю, что
Date: 2015-12-05 10:52 pm (UTC)Re: думаю, что
Date: 2015-12-06 08:57 am (UTC)(frozen) Саша,
Date: 2015-12-07 02:31 pm (UTC)у вас традиция требовать подпись под анонимным комментарием, читателям это требование безразлично. Было бы логично запретить анонимные комментарии.
Исключительно из уважения к вам, подписываю комментарий
Подпись: без подписи.