Вероятностная задачка

[spamsink]

Даны две неотличимые на вид монеты, об одной из которых известно, что орлом и решкой она выпадает равновероятно, а о другой - что орлом и решкой она выпадает с вероятностями p и 1-p, но неизвестно, какой стороной чаще. Какое количество бросков обеих монет нужно потребовать, чтобы гарантировать различение двух монет с вероятностью ошибки не более r? Изменится ли ответ, и если да, то как, если известно, какой стороной фальшивая монета выпадает чаще?

Задачу я только что придумал, поэтому сам ответа на большинство вопросов задачи не знаю.

Comments

[ormuz.livejournal.com]

binomial test называется.
не изменится.

[spamsink]

Рассмотрите p=0 и r=0.49.

[ormuz.livejournal.com]

3 броска

[spamsink]

Что-то многовато.

[ormuz.livejournal.com]

может с нулем специальный случай.

[no more turtles (from livejournal.com)]

При двух бросках у нас 50% вероятности, что обе монеты будут падать на одну сторону в первом и втором броске. Если же мы знаем, на какую сторону падает фальшивая монета, то вероятноть того, что другая монета два раза упадет на туже сторону уже 1/4. То есть двух бросков хватает.

[spamsink]

Если мы знаем, какой стороной вверх падает фальшивая монета, то достаточно одного броска, чтобы сократить вероятность ошибки до 25%.

[no more turtles (from livejournal.com)]

зависит от того каков алгоритм выбора и как считать ошибку. Если вы после одного броска и выпадания двух монет на одну и ту же сторону случайно выбраете одну из них и при этом ошибаетесь -- тогда да, общая вероятность такого сценария 25%. Если же бросаете монеты до тех пор, пока не сможете точно гарантировать вероятность ошибки <=r (что в случае p=0 идентично r=0), то среднее число таких бросков - 2.

Тут как и во всем тервере дьявол в деталях.
Все зависит от точной формулировке задачи и от способа подсчета ошибки. Например, если вы знаете p заранее и потребуете найти минимальное число бросков, при котором *для каждого* эксперимента ошибка будет гарантированно <=0.49, то ответ будет -- бесконечность. Ибо нельзя исключить n одинаковых выпаданий, хотя вероятность этого конечно мала.
Если же вы считаете среднюю ошибку по всему ряду или какую-нибудь оценку этой средней ошибки -- то ответы будут другие. Или же вы каждый раз делаете столько бросков, сколько надо для <=r и потом потом считаете среднее числу бросков по ряду. Или p неизвестно заранее (то есть при бросании), но его можно использовать для подчета минимального числа бросков -- будет совсем другой ответ.

[no more turtles (from livejournal.com)]

> не изменится.
а разве это как раз не разница между one-tailed и two-tailed test? Если мы знаем какой стороной монета выпадает чаще и проверяем только одну сторону, то вероятность ошибки при том же количестве бросков будет в два раза меньше.

[ormuz.livejournal.com]

да, точно

[amigofriend.livejournal.com]

pr вероятности детектед!

[spamsink]

Вероятно.

[phoonzang.livejournal.com]

Есть красивое обобщение на применение метода expectation maximization.

Даны N монет с p_i, на каждом шаге случайно выбирается одна из них и подбрасывается M раз. Как после S шагов определить, какая монета подбрасывалась на каждом шаге и какие у монет были p_i?

[sab123.livejournal.com]

Оказалось, что в вопросе Машинного Учения весьма краегуольной является похожая задача:

Есть кривая монета, мы производим N бросков и записываетм результат. По этому результату предлагается оценить, насколько крива монета.

[spamsink]

Получится распределение вероятностей кривизны. Ответом должна мода служить?

[sab123.livejournal.com]

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