эксперимент

[a_shen]

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

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

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

Comments

[taki-net.livejournal.com]

Примерная густота простых чисел на этом отрезке, если я не путаю, около 1/700 (лень проверять). Огрубляя, среди первых 700 числе простых будет в среднем одно. Алгоритм обнаружит его, а также сделает 70 ложных срабатываний и 7 ложных двойных срабатываний.

Примерно 1/8, что простое.

[a-konst.livejournal.com]

!! класс.

[alexispokrovski.livejournal.com]

Интуитивно -- асимптотически маленькая вероятность.

Потому как первое positive будет не менее вероятности первой ошибки, т.е. 1/100, т.е. в среднем через 100 чисел. То есть каждое сотое число. Это огромная доля.

Тогда как простые числа составляют iirc не более чем логарифмическую долю.

Итого, искомая вероятность экспоненциально мала как функция интервала, в котором простое число ищется.

[011010011001011.livejournal.com]

Pust' eps = 1 / ln(2^1000) -- dolya prostyh chisel.

Togda na kazhdom shage s veroyatnostyu eps vse horosho (my nashli prostoe), s veroyatnostyu 0.01 (1 - eps) vse ploho (my vybrali sostavnoe, no etogo ne obnaruszili), i s ostalnoy veroyatnostyu vse delaem zanovo. Znachit, otvet raven eps / (0.01 (1 - eps) + eps) ~ 0.13.

[vladimir000]

Не совсем понятно условие: для составного числа в 90% случаев говорится что составное, а в 10% говорится "простое" или же "не известно"?

говорится то же

[a-shen.livejournal.com]

самое, что говорится (наверняка) для всех простых чисел. Как этот ответ обозначать "неизвестно" или "простое" - вопрос соглашения. Наверно, можно было бы говорить "возможно, простое" (наверняка для всех простых и с вероятностью 10% для составных)

[rombiknapuze.livejournal.com]

Случайное число порядка 2^1000 простое с вероятностью примерно 1/700 (потому что ln(2^1000) = 1000 ln 2 \approx 700).
Если число составное и (что важно, но весьма сомнительно) результаты двух проверок независимы, у него есть 1 шанс из 100 пройти оба теста на простоту. Так что на 700 случайных двоично-тысячезначных чисел приходится в среднем одно простое и почти семь ложно-простых.
Ответ: примерно 1/8.

Использовали асимптотику плотности простых чисел и (неявно) формулу Байеса.
Задача, конечно, несложная, но совсем простой я бы её не назвал.

[nikolenko.livejournal.com]

Задача простая, если знать распределение простых чисел; если хочется, чтобы это была задача по теории вероятностей, лучше включить это в условие, а то получается задача на знание базовой теории чисел. Ну, или я ничего не понял. :)

[stzozo.livejournal.com]

Я так понимаю, автор задачи подразумевал, что разные применения этого алгоритма на одном и том же числе - это независимые случайности?
В таком случае, двукратное применение к составному числу будет давать правильный ответ в 99% случаев.
Среди 1000 битных чисел доля простых составляет примерно 1/ log(2^1000) = 0,001/0.69 = 0.00145.
Если человек взял число, и обнаружил, что оно простое - то 0.00145 сценариев, и что оно действительно простое, и (1-0.00145)*0.01 - что оно составное, ложно распознанное как простое. То есть, примерно 15%, что найденное число действительно является простым.

[mathclimber.livejournal.com]

Чтоб решить задачу, надо еще знать сколько (хотя бы приблизительно) простых чисел среди всех 1000-битовых. (Знаю, что есть весьма точные формулы, искать лень :) )

[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.

[janatem.livejournal.com]

Во-первых, здесь нужны базовые знания из теории чисел о распределении простых чисел. Я помнил про функцию π(x) и ее асимптотику x/ln x, но не знал или не помнил, в какой форме можно записать остаточный член, чтобы сделать оценку для π(2^1000). Не заглядывая в справочники, можно понадеяться, что для практически применимого ответа достаточно считать долю простых чисел среди всех 1000-битовых с большой точностью равной p=1/(1000 ln 2).

Во-вторых, задаче не хватает данных о том, как скоррелированы повторные запуски алгоритма на одном и том же составном числе. Предположим, что они независимы, поэтому вероятность ложного срабатывания после двухкратного запуска равна q=1/100.

В этих предположениях можно нарисовать граф событий и подсчитать вероятность прохождения по плохой ветке (когда полученное число оказалось составным). Искомая вероятность выражается как x=q(1-p)\sum_{n=0}^\infty ((1-p)(1-q))^n. У меня получилось на калькуляторе примерно 0.87 (выходит, какой-то бесполезный метод).

Задачу можно считать легкой, если поцыэнту известно что-нибудь о распределении простых чисел.

[musatych.livejournal.com]

Для простоты примем, что e=2, а для 1000-битных чисел уже выполняется закон распределения простых. Тогда среди 1000-битных чисел будет 0.1% простых. Взяв случайное число, мы с вероятностью 0.1% получим простое, и для него алгоритм скажет, что оно простое, а с вероятностью 99.9% получим составное, а для него алгоритм с вероятностью 1% скажет, что оно простое. Таким образом, по формуле Байеса условная вероятность простоты, если алгоритм сказал "простое", будет около 1/11.

Если решать, то вроде несложно, а вот если пытаться угадать ответ из нескольких вариантов, то могут быть проблемы.

[ksega.livejournal.com]

У меня получилось ~ 13%

Вероятность что случайное 1000 битное число простое ~= 1/693 = (1000*log(2)-1)/(1000*log(2))^2
Обозначим эту вероятность a, а вероятность успеха алгоритма для составного числа (90%) обозначим b.
Вероятность того, что после двух проверок, мы правильно идентифицируем составное число = 1 - (1-b)^2

Для того чтобы найти простое число за n шагов, мы должны попробовать n-1 составное число, причем каждое из них правильно идентифицировать, и на последнем шаге должны взять простое число. Вероятность этого равна
((1-a)*(1-(1-b)^2))^(n-1) * a

суммируя по n получаем а/(1-(1-a)*(1-(1-b)^2)) . Это порядка 12.6%

[ulwr.livejournal.com]

Я не специалист по теории вероятности, но по-моему достаточно очевидно, что мы ищем 1-вероятность того, что первое найденное (и признанное простым) число окажется составным. То есть, нам нужно 1-n/2^1000*q, где n — общее количество составных чисел, которые можно записать 1000 битами, а q=0.1 или 0.01 в зависимости от того, стабильны ли false positives данного алгоритма (то есть, если он уже обозвал составное число простым, может ли он его признать составным при ещё одной проверке). Это решение не требует никаких конкретных знаний и основано на общегуманитарных соображениях, то есть если оно правильное, то задача лёгкая (а если нет, то нет).

[rwalk.livejournal.com]

Это условная вероятность того, что при исследовании отдельного числа оно будет действительно простым при условии, что алгоритм признал его простым, т.е. p/(p+.01*q), где p - доля истинно простых чисел в выборке, и q=1-p.

[mikev.livejournal.com]

А доля простых чисел среди 1000-битных известна?

[(Anonymous)]

Может я не совсем понял условие, но, как мне показалось, ответ зависит от неизвестного нам количества простых чисел в 1000-битных числах: например если там не было бы ни одного простого числа то, вероятность очевидно 0,01 или 0 (зависит от ответа алгоритма проверки в случае ошибки), а если все числа простые, то ответ 1. Из википедии: число простых чисел от 1 до N примерно N/lnN, тогда вероятноcть встретить простое число около 1/ln (2 power (1000))=1/1000ln2=1/693, ну и надо учесть ошибку ( то есть еще один процент от всех составных чисел или 0)
итого 1/693+6.92/693≈0.0114
задача простая, если иметь википедию))

[antchi.livejournal.com]

Проверки-то независимые для одного и того же числа? То есть для составного числа будет с вероятностью 0,81 дважды и с вероятностью 0,18 - ровно один раз сказано, что оно составное?

да

[a-shen.livejournal.com]

вероятность имеется в виду по внутренним случайным битам алгоритма для фиксированного входа

[ilya-dogolazky.livejournal.com]

ну во-первых ответ зависит от количества простых числе в этом промежутке, или лучше даже вероятности случайно выбранного тысячью киданий монетки, что получится простое, обозначим её буквой Р. Затем рассмотрим случай, что первые К выбранных монеткой чисел будут не простыми, получится некая вероятность того, что из них никто не будет признан простым. Потом останется это всё просуммировать по К от 0 до бесконечности, что в данном случае просто геометрическая прогрессия, так что нефиг делать просуммировать.

[ilya-dogolazky.livejournal.com]

да, и кстати если монетка выберет за тысячу киданий число 0 или число 1, то вероятностный алгоритм взорвётся ... они ж не простые и не составные

[cross-join.livejournal.com]

Навскидку, 0,9.
Мне интереснее другое. Пассаж про 1000 бит используется с той же целью, что и соседка в задачке с шапкой и фальшивой купюрой?

[relf.livejournal.com]

В моделе Крамера будет что-то типа
p / (p + 0.01*(1-p)),
где p=1/ln(2^1000).

[ile-eli.livejournal.com]

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

[avva.livejournal.com]

Пишу не читая комментарии. 1000-битное число будет простым с вероятностью примерно 1/1000, потому что доля простых чисел до N примерно 1/логарифм N. Предполагая, что две проверки составного числа дают независимый друг от друга результат, составное число будет с вероятностью 1% названо простым. Интуитивно говоря, он с намного большей вероятностью сначала наткнется на составное число, прошедшее проверки, чем на простое число. Я бы оценил в >90%, не пытаясь вычислять.

Теперь попытка вычислить (я плохо знаю и помню теорвер). P(простое|прошло проверку) = P(прошло проверку|простое) * P(простое) / P(прошло проверку) = 1*0.001*P(прошло проверку). Это последнее расписывается как

P(прошло проверку) = P(прошло проверку|простое)*P(простое) + P(прошло проверку|составное)*P(составное) = 1*0.001+0.01*0.999 = 1.099%

Конечное значение "какова вероятность, что простое, если прошло проверку" равно 0.001/1.099% = 9%.

Поскольку выборы не зависят друг от друга, количество попыток до первой прошедшей проверку нас не интересует и не влияет на ответ, который остается примерно 9%.

[aamisha.livejournal.com]

Навскидку кажется, что это задача по ТЧ не меньше чем по теорверу.
Из тервера нужна формула Баеса + какие-то базовые понятия о вероятности, из ТЧ - распределение простых чисел.

Все шаги одинаковы и независимы: условная вероятность остановиться на простом числе на iом шаге при условии остановки на iом шаге не зависит от i, а значит общая вероятность остановиться на простом числе равна этой условной вероятности (потому что вероятность остановиться равна 1).

Осталось посчитать вероятность выбрать простое число при условии, что мы остановились за один шаг.
Количество простых чисел меньших N - это N/lnN, значит, количество составных = N*(1-1/ln N).
Количество составных, на которых наш алгоритм дважды дает ложноположительный ответ: N(1-1/ln N)*0.01.
Всего положительный ответ получается на N/ln N + N(1-1/ln N)*0.01, из них простых N/ ln N.
Откуда условная вероятность остановиться на простом - это (N/ln N)/( N/ln N + N(1-1/ln N)*0.01) = (1/ln N)/( 1/ln N + (1-1/ln N)*0.01) = 1/(1 + (ln N - 1)*0.01), ln N = 1000*ln2 из условия, получаем итоговую вероятность: 1/(0.99 + 10ln2).
Если взять калькулятор и посчитать, то получается примерно 12.5%.


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

[slazav.livejournal.com]

Я, вообще, плохо чувствую и понимаю теорию вероятностей. Решение у меня есть, но полной уверенности в нем нет, оценить сложность не могу. Я бы решал так:

Пусть вероятность того, что 1000-битное число - простое = p.
На каждом шаге мы получаем положительный ответ с вероятностью p+0.1(1-p) и останавливаемся,
или отрицательный с вероятностью 0.9(1-p) и делаем следующий шаг.

На "положительном" шаге (последнем) вероятность настоящего простого числа = p/(p + 0.1(1-p)) и она не зависит от того, сколько "отрицательных" шагов было перед этим.

Это и есть ответ, 1/(0.9 + 0.1/p). Если простых чисел мало (p->0), то вероятность найти их таким способом тоже близка к нулю...