Еще о теореме Байеса: задачка Монти Холла

[scholar_vit]

В комментариях к предыдущей записи cheeha напомнила классическую задачку Монти Холла. Я хочу показать, что байесовское решение не только проще классического, но и позволяет увидеть неявное допущение в последнем.

Итак, перед нами три двери. За одной приз, две другие пусты. Вы выбираете дверь A, ведущий, который знает, где приз, показывает, что за дверью B пусто. Следует ли настаивать на A или открыть C?

Пусть A, B, C - события, которые состоят в том, что приз находится за соответствующей дверью. Пусть OB - событие, которое состоит в том, что ведущий открыл дверь B после того, как игрок выбрал дверь A. Найдем P(C|OB) (вычислить P(A|OB) можно аналогично и предоставляется читателю в качестве упражнения).

По теореме Байеса P(C|OB) = P(OB|C)P(C)/P(OB). A priori P(C)=1/3. Если приз лежит за дверью C, то ведущий обязательно выберет дверь B, поэтому P(OB|C)=1. А как вычислить P(OB)?

Очевидно, что P(OB) = P(OB|A)P(A) + P(OB|B)P(B) + P(OB|C)P(C). В этой сумме второй член равен нулю, а третий 1/3. Как быть с первым? Иначе говоря, что делает ведущий, если обе оставшиеся двери пусты?

Если ведущий подбрасывает монетку, выбирая одну из двух пустых дверей, то P(OB|A)=1/2. Тогда теорема Байеса дает P(C|OB)=2/3. Это и есть ответ, который обычно приводят.

Но что, если мы знаем, что ведущий очень ленив и стоит у двери C? Иначе говоря, мы знаем, что он всегда открывает ее, если только за ней нет приза. Это значит, что P(OB|A)=0, и P(C|OB)=1. Что понятно: если ведущий преодолел лень и пошел открывать дверь B, значит, за дверью C точно лежит приз. Аналогично если ведущий очень ленив и стоит у двери B, то P(C|OB)=1/2. Тут поучительно рассмотреть, как в этом случае меняется P(A|OB) по сравнению с априорным P(A).

Можно рассмотреть случай, когда ведущий не очень ленив, и иногда идет к другой двери без необходимости. В итоге можно доказать, что смена выбора игроком никогда не ухудшает его позиции, но может ее улучшить.

Мы видим, что байесовское решение не только проще, но и глубже "обычного".

Comments

[agasfer.livejournal.com]

А откуда игрок знает, ленив ведущий, или нет? Если он это знает, то это уже как игра Смока Белью в рулетку.

[scholar-vit.livejournal.com]

А почему игра Смока Беллью не должна описываться теорией вероятности?

[agasfer.livejournal.com]

Вы роман забыли? Смок заметил, что колесо рассохлось т к стол с рулеткой стоял слишком близко к печке. Поэтому, определенные позиции были более выйгрышными, чем другие. Игрок, севший за такой стол впервые, этого не знает, поэтому думает, что имеет дело с теорией вероятности, или везением.

Если ведущий ленивый, кстати, он может всегда класть приз за дверь А, что тоже может быть замечено.

[scholar-vit.livejournal.com]

Я прекрасно помню Джека Лондона. Повторяю вопрос: почему Вы думаете, что теория вероятностей описывает только равновероятные события? Описывает ли теория вероятностей ситуацию, когда определенные номера выпадают чаще, чем другие?

[agasfer.livejournal.com]

В общем виде теория вероятностей описывает любые случайные события, даже если некторые события случайнее других; просто применять ее к частному случаю Р=1 неинтересно. В ситуации, когда ленивый ведущий открыл дверцу В, а не ближайшую к нему С, "опытный" игрок знает на 100%, что приз за дверцей С. Здесь он использует не теорию вероятностей, а свое знание о лени ведущего (аналог знания Смока о дефективной рулетке).

[m61.livejournal.com]

А что подразумевается под "обычным" решением? А то самое простое решение, известное мне, заключается в следующем соображении: так как ведущий _всегда_ открывает дверь, за которой нет приза - то, очевидно, упрямец, который не пожелает изменить на втором этапе свой первоначальный выбор, может выиграть, только если он изначально выбрал правильную дверь. А вероятность этого равна 1/3, разумеется. Следовательно, изменяя на втором этапе свой выбор - он выигрывает с вероятностью 2/3.

По-моему, это решение явно проще. Но, конечно, выигрывая в простоте - проигрываем в глубине.

Схожая задачка, которая проще решается от предположения, что первым своим ходом "игрок" достигает поставленной цели - это известная задачка про круговую дуэль.

[scholar-vit.livejournal.com]

Это и есть один из вариантов обычного решения. Интересное упражнение: проанализировать его в случае, когда стратегия ведущего известна.

[scholar-vit.livejournal.com]

Что касается простоты - то см. предыдущую запись. "Обычное" решение проще изложить, но додуматься до него как раз сложнее. Байесовское решение проще в том смысле, что получается автоматическим применением стандартного алгоритма, а не рассуждениями ad hoc. Вместо паззла - задачка группы А. Ну в крайнем случае Б.

[egh0st.livejournal.com]

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

простейшее решение элементарно: после первого выбора нахождение приза 1/3 в выбранной опции и 2/3 в остальных.

т.к. ведущий открывает гаранта™, де-факто вероятность нахождения приза НЕ меняется. 1/3 в выбранной опции и 2/3 в оставшейся единственной опции.

[efimpp.livejournal.com]

почему-то формулировка задачки не упоминает, что ведущий всегда предлагает меняться (или, точнее, делает это независимо от первого выбора игрока)

[darth-vasya.livejournal.com]

Для байесианского решения условие про "всегда" не требуется, потому что субъективная вероятность не нуждается в предельном переходе к "бесконечному числу повторений".

[efimpp.livejournal.com]

не понял ....
а если ведущий предлагает поменять только когда игрок выбрал правильно?

[darth-vasya.livejournal.com]

Если это откуда-то нам известно, тогда байесианское решение меняется с учётом этой информации. Когда у нас нет такой информации, то и никакого "а если".

Приведённое в посте решение верно (точнее - оптимально) даже в том случае, если в игру никогда раньше не играли и никогда больше не будут играть.

[efimpp.livejournal.com]

вот на этом месте я замираю в полном недоумении. мы ведь не отказываемся выбирать значение корреляции между удачностью первого выбора игрока и предложением его изменить.
мы почему-то решаем, что оно равно 0.

[darth-vasya.livejournal.com]

В отсутствие информации о корреляции A и B мы должны предполагать, что P(A|B) = P(A) и т.д. Любой другой выбор понизил бы информационную энтропию нашего распределения, то есть, привнёс бы в него информацию, которой у нас нет - "из ниоткуда", то есть практически наверняка ухудшил бы его.

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

[efimpp.livejournal.com]

да, не не честнее ли в этом случае сказать, что мы не знаем ответа?
в каком смысле наше решение является оптимальным? в предположении, что распределение возможных значений этой самой корреляции симметрично относительно 0?

[darth-vasya.livejournal.com]

"Не знаю" по байесианским понятияи означало бы "у меня нет совсем никакой информации", что неверно. Информация у нас таки есть: что дверей три, что приз - за одной из них, что одну уже выбрали, что ведущий даёт возможность передумать. На основании этой и никакой другой информации оптимальный ответ (данный в посте) совпадает с тем, который бы мы получили, если бы знали, что ведущий "не коррелирует". То есть, информация о том, что ведущий точно "не коррелирует" не принесла бы нам большой пользы. Это вполне логично: в первом случае у нас нет информации о корреляции ведущего и приза. Во втором мы знаем, что такой информации нет в природе, то есть у нас её таки по-прежнему нет :)

Оптимально - в конечном итоге, следует формальным правилам индуктивного мышления, любое отклонение от которых гарантировано приведёт к отклонениям от того, что мы в быту называем здравым смыслом (например - высасывание из пальца информации, которой на самом деле нет). Звучит, наверное, несколько сумбурно, но за этим скрывается вполне себе неиллюзорное смысловое содержание, которое очень хорошо изложено в книге Джейнса Probability Theory: The Logic of Science - http://www.med.mcgill.ca/epidemiology/hanley/bios601/GaussianModel/JaynesProbabilityTheory.pdf

[efimpp.livejournal.com]

>На основании этой и никакой другой информации оптимальный ответ
есть неизвестная нам переменная, которая легко и непринужденно может изменить наш ответ до наоборот.
давайте, чтоб что-то сказать, назначим ей 0.0. не верю (С).

>Это вполне логично: в первом случае у нас нет информации о корреляции ведущего и приза. Во втором мы знаем, что такой информации нет в природе, то есть у нас её таки по-прежнему нет :)
а вот нет ли в этом рассуждении неявной предпосылки, что отсутствие корреляции является "нормальным", типичным случаем, а вот ее ненулевое значение надо специально оговаривать?

PS почему 0 (ноль) отображается как o? или это только у меня???

она у меня как раз в телефон закачана - но не начинал читать еще :-)

[darth-vasya.livejournal.com]

> есть неизвестная нам переменная, которая легко и непринужденно может изменить наш ответ до наоборот. давайте, чтоб что-то сказать, назначим ей 0.0. не верю (С).

Это параметр_в_модели, а не переменная_в_реальности. Значение о.о этого параметра как раз и означает - "[у нас] нет [взаимной] информации [между положениями ведущего и приза]". Появится информация - будет другое значение.

> а вот нет ли в этом рассуждении неявной предпосылки, что отсутствие корреляции является "нормальным", типичным случаем, а вот ее ненулевое значение надо специально оговаривать?

Нет такой неявной предпосылки. Есть вполне себе явная констатация факта, что у нас здесь сейчас в данном конкретном случае нет информации о такой корреляции. Действительно, любое другое значение подразумевает наличие такой информации, и тогда неплохо было бы мочь её, так скть, предъявить. Иначе мы вместо реального мира рассуждаем о каких-то вымышленных вселенных :)

Вот если мы проведём дополнительные наблюдения и увидим наличие такой корреляции, тогда мы по-байесиански эту информацию учтём и получим новое постериорное распределение - учитывающее в себе всю полноту информации, имеющейся у нас на тот момент в будущем.

> она у меня как раз в телефон закачана - но не начинал читать еще :-)

Большой респект за благие намерения ;) Там всё это по-человечески написано :)

[efimpp.livejournal.com]

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


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

вот задачка: пролетит ли свободно падающее тело с начальной скоростью 0 больше 40000м за первые 100 сек?
можно конечно посчитать для случая g ~ 9.8 m/c^2, а можно сказать, что вообще-то оснований считать, что дело происходит на поверхности Земли у нас особых нет и ограничиться выводом формулы с переменной g.