Парадокс Монти-Холла и имитационное моделирование

[@YasonBy]

Прелесть имитационного моделирования в том и заключается, что аналитическое решение не требуется.
Достаточно определить правила взаимодействия компонентов модели — и после нескольких (тысяч/миллионов) итераций получаешь статистически правдоподобный результат.

[@YasonBy]

Спасибо за научный подход! :)

Прогон Perl-кода в codepad'е даёт вполне правдоподобный результат: 6792/3346.

Всё делалось «на коленке» и задачи повышения читаемости не стояло.

Как писать код — дело Ваше, но когда публикуете — читаемость кода важна. Тем более, что расставить отступы и подсветить код — дело пары минут.

[@Quiz]

Прогон Perl-кода в codepad'е даёт вполне правдоподобный результат: 6792/3346.

Да, но всё же не так явно, как 6664/3336 в случае с PHP :)

Как писать код — дело Ваше, но когда публикуете — читаемость кода важна. Тем более, что расставить отступы и подсветить код — дело пары минут.

Спасибо за замечание. Я исправлюсь, обещаю :)

[@SeLarin]

А в чем проблема-то? Или он при каждом прогоне такое выдает?

[@Quiz]

У меня — да. На 4 версии.

[@SeLarin]

Надо полагать версия до 4.2.0? :) А seed менять не пробовал? Просто добавь в начало скрипта вызов srand.

[@Quiz]

Уже. Да, значения изменились :)

[@AvRUS]

Странно, для Perl:
6792 + 3346 = 10138

Для PHP:
6664 + 3336 = 10000

Причем в изначальном варианте для Perl:
Результаты прогона:
Gamer NOT change choice: 2562
Gamer change choice: 7586

2562 + 7586 = 10148

И это из 10000 циклов. Как такое возможно?

[@YasonBy]

Дело в том, что PHP-скрипт запускается только один раз, и выдаёт количество выигрышей/проигрышей при условии, что игрок меняет выбор ($change_choice = 1;).
A Perl-программа прогоняется дважды: для случая со сменой выбора (my $change_choice = 1;) и для «упрямого» игрока (my $change_choice = 0;). Поэтому сумма двух этих результатов равняться 10000 совершенно не обязана.

[@Neophyte]

В теории вероятностей много подобных парадоксов. У меня на конференции был доклад на эту тему.

А вас, возможно, фильм «21» навел на этот парадокс. )

[@Quiz]

А вас, возможно, фильм «21» навел на этот парадокс. )

Нет. Кстати, не смотрел. Поспрашиваю у знакомых. :)
Просто меня всегда интересовали забавные логические задачи и подобные «парадоксы».
Например, в данном случае интуиция играет против человека и, казалось бы, очевидное решение является неверным либо неточным.

[@Hanhe]

Пардокс удвоения шара из матанализа =)

[@Quiz]

Пардокс удвоения шара из матанализа =)

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

[@shai_xylyd]

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

[@Neophyte]

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

[@darkk]

Может быть s/логике/интуиции/ :-)

[@Quiz]

Тем интереснее эти примеры рассматривать :)
Кстати, не так уж их и много, ИМХО. Или некоторые просто однотипны? :|

[@Neophyte]

Я рассказывал про четыре из них на конференции, все они были разными, одна тема касалась геометрии. Ну поищите уже в гугле, если вам так интересно… ;)

[@Quiz]

Ну так там и нахожу по бОльшей части :)

[@IntenT]

Никаких парадоксов.
После того как ведущий открыл первую дверь, рассуждать о всяких вероятностях, бывших до этого события — бессмысленно.
Когда осталось две двери — имеем новые вероятности и новое событие, к которому не применимы предыдущие вероятности

[@Quiz]

Однако, это не так. Задача поставлена иначе и именно в постановке задачи дело.

Какова вероятность по пути из дома на работу встретить динозавра?

[@VoidEx]

Как раз вероятность угадать не меняется от последующих событий. Т.е. как было 1/3, так и осталось. На две оставшиеся приходилось 2/3, а так как одну из них открыли (причём гарантированно забракованную), то на открытую теперь приходится 0, а на вторую закрытую — 2/3
Чтобы это не приводило к парадоксу, представьте 1000000 дверей. Вы выбираете одну, затем ведущий открывает 999998 с козами. Остаётся две. Тут уже сложно сомневаться в том, что Вы изначально не угадали (сложно угадать из миллиона), а автомобиль в невыбранной Вами двери.

[@IntenT]

Не осталось 1\3.
Учите матчасть

[@VoidEx]

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

[@VoidEx]

Есть анекдот на эту тему (без обид):
Девушку спросили, какова вероятность встретить динозавра?
— 50/50
— Но почему?
— Ну или встречу, или нет.

А разве мой пример с миллионом дверей не интуитивен? Жаль, я думал иначе.
Вот есть миллион шариков, один из них красный, остальные белые. Вы вытащили один наугад. Вероятность того, что он красный — 1/1000000. Вы открываете руку — он и правда белый. Делаете огромное число экспериментов — вероятность подтверждается. Тут всё просто.
Далее изменим эксперимент. Вы достаёте шар наугад, потом кто-то залазит в корзину и целенаправленно достаёт 999998 белых шаров, и там остаётся один. И вдруг, по Вашей логике, вероятность стала 1/2? С чего вдруг?
Теперь ещё раз изменим эксперимент. Этот кто-то достаёт 999998 шаров, но Вы этого не знаете, а он знает. Повторяете эксперименты, сколько получите?

[@VoidEx]

Если бы он сначала открыл дверь, а потом игрок сделал бы выбор, то было бы 1/2. Просто потому, что он уже не может выбрать открытую дверь! У нас ситуация другая, он сначала выбирает, а потом ведущий открывает дверь.

[@EiZeRR]

Вы упустили тот факт, что по условию задачи, открытие ведущим двери является достоверным событием, то есть происходящим с вероятностью 1.

[@VoidEx]

Как раз именно этот факт и создаёт такую вероятность.

[@shai_xylyd]

Как же все многословно.

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

Если выбор человека случаен (равномерно) и мы проводим имитационное моделирование, то можно полагать, что он делает такой выбор i%3, где i — номер итерации. Таким образом код, который описывает стратегию, в которой он меняет свои показания:

int fail = 0;
int success = 0;
for(int i=0;i<100000;i++)
{
  if ((i%3)==2) fail++; // очевидно, что если он угадал, где и сменил свой выбор, то он проиграл
  else success++;
}

[@shai_xylyd]

Из этого кода, кстати, становиться очевидно, почему стратегия с изменением выбора выигрышная.

[@EiZeRR]

объясните пожалуйста такой момент в парадоксе.

Почему при его объяснении считается изначально, что вероятность того, то игрок выберет дверь с козой равна 2/3, а с автомобилем — 1/3, при этом не учитывая тот факт, что событие «ведущий открывает дверь с козой» является достоверным? То есть учитывая этот факт, шансы игрока выбрать дверь с козой и автомобилем — равноправны и их вероятности равны 1/2.

[@shai_xylyd]

Потому настоящее не зависит от будущего=) и количество исходов не определяет вероятность.

[@EiZeRR]

Это не будущее — это условие задачи. А по нему дано — что в любом случае ведущий откроет дверь, Таким образом игрок в любом случае всегда окажется в ситуации, когда у него будет две двери и соответственно выбор из них с вероятностью 1/2.

[@shai_xylyd]

Будет два исхода, а вероятности будут 2/3 и 1/3.

[@EiZeRR]

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

[@shai_xylyd]

1/3

[@EiZeRR]

Я не правильно выразился.

Вот вы стоите перед дверьми — выбираете одну из них. Ведущий открывает дверь с козой. Опа! и ваша 1/3 сразу превращается в 1/2. То есть с вероятностью 1/2 вы будете указывать на дверь с авто или козой.

[@Quiz]

Но мы не знаем какую именно дверь откроет ведущий!

[@EiZeRR]

Да-да, я хотел сказать не совсем то, а о том, что хотел сказать написал чуть выше.
А именно — выбор вами двери и открытие двери с козой являются достоверными событиями, следовательно на них можно забить. И считать что игрок уже находится в ситуации, когда он стоит перед двумя закрытыми дверьми и одной открытой. В одной закрытой коза, в другой — авто, он указывает на какую-то из них. Тут же очевидно, что от того, сменит он указанную дверь или нет — ничего не изменится, т.к. вероятности по 1/2.

[@EiZeRR]

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

[@Quiz]

Суть заключается в последовательности действий. В данном случае действий два. Но эксперимент один.
Если бы ведущий сначала открыл дверь и только потом игрок делал свой выбор — всё было бы очевидно и вероятность сотавляла бы 50/50, то есть 0,5.

Посмотрим на это с другой стороны. Какова вероятность проигрыша игрока?
Игрок не меняет свой выбор. Без вариантов. Откроет ведущий одну из двух оставшихся дверей или нет, шанс проигрыша игрока составляет 2/3. Так? Так. То есть вероятность выигрыша в ситуации, когда игрок не меняет свой выбор 1/3. Так? Так.

[@EiZeRR]

вот как я понимаю ваш ход рассуждений.

допустим игрок выбрал дверь с козой — это возможно в двух случаях из трех, тогда ведущий открывает вторую дверь с козой и сменой двери игрок укажешь на дверь с авто, и только в одном случае из трех, то есть когда игрок сначала указывает на автомобиль, он его потеряешь. То есть шансы при смене двери 2/3.
Отлично, только вот если учесть что опять же по условию задачи ведущий открывает дверь с вероятностью равной 1, то у нас это рассуждение ломается, т.к. вероятность изначально выбрать дверь с козой или авто становится равной 1/2.

[@EiZeRR]

То есть если игрок знает, что ведущий точно откроет дверь с козой, то он априори будет знать, что изначально у него шансы выбрать дверь с козой или авто будет равны пор 1/2, а не 1/3 и 2/3. А вот если он не знает точно как поступает ведущий, то тут уже темный лес, и задача вообще не будет иметь решения (если конечно игроку не будет известна вероятность того, что ведущий откроет дверь после хода игрока).

[@Quiz]

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

[@Quiz]

И мы не знаем какую именно дверь откроет ведущий. Поэтому изначально шанс выигрыша составляет 1/3 (в случае без смены выбора).

[@falone]

Если вдруг кто забыл, то эту тему мы уже обсуждали: habrahabr.ru/blogs/zadachki/23346/
Много копий было сломано. Там в комментах есть объяснение для тех, кто совсем не рубается (типа меня:)

[@Quiz]

Не думал, что такая простая задача может вызвать столько споров…

[@Scala]

Что касается «случайных чисел» — они вовсе не случайные, почитайте про линейный конгруентный генератор.

[@Swappp]

P.S.: Кстати, после написания именно этого скрипта я начал относиться к генератору псевдослучайных чисел в движке Zend с долей недоверия. Просто посмотрите ещё раз на результаты прогона в PHP и в Perl :)

PHP насколько я помню просто использует стандартный rand, из stdlib в C. Про srand и php < 4.2 уже написали :)

[@mix2000]

Мы вот тут недавно тоже рассуждали на эту тему.

Здесь можно посмотреть реализацию на руби и java.
А здесь — на Small Basic.

[@Quiz]

Отличные примеры!