*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

воскресенье, 26 июля 2009 г.

Парадокс Монти-Холла

Есть такая интересная задача - парадокс Монти-Холла.

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

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

Самое прямолинейное решение, приходящее в голову: смена ящика ничего особенно не даст. Вы выбрали один ящик из трех - вероятность выиграть 1/3. После открытия одного ящика ведущим их осталось два, поэтому вероятность угадать где приз 50/50. Выбор вы уже сделали, и он и так является одним из текущих вариантов. Выходит, что нет особого смысла менять выбор.

Но эта задачка тем и интересна, что при столь тривиальной постановке ее правильное решение не совсем очевидно, хотя с точки зрения теории вероятности тут все прозрачно - теорему Байеса еще никто не отменял.

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

В Википедии приведено исчерпывающее объяснение.

Ну а чтобы уж окончательно развеять все сомнения, пришлось провести эксперимент.

montihall.cpp:
#include <iostream>
#include <set>
#include <cstdlib>
#include <cassert>
#include <ctime>

int all_doors[] = { 1, 2, 3 };

bool no_change_strategy() {
// doors - это множество доступных дверей (1, 2, 3) для выбора игроком.
std::set<int> doors(all_doors, all_doors + 3);

// Выбираем истинную дверь (от 1 до 3).
int real_door = (std::rand() % 3) + 1;

// Выбираем первый и окончательный выбор игрока (от 1 до 3).
int primary_choice_door = (std::rand() % 3) + 1;

return real_door == primary_choice_door;
}

bool change_strategy() {
// doors - это множество доступных дверей (1, 2, 3) для выбора двери,
// открываемой ведущим после первого выбора игрока.
std::set<int> doors(all_doors, all_doors + 3);

// Выбираем истинную дверь (от 1 до 3).
int real_door = (std::rand() % 3) + 1;

// Выбираем первый выбор игрока (от 1 до 3)
int primary_choice_door = (std::rand() % 3) + 1;

// Исключаем из множества дверей истинную дверь и выбор игрока.
doors.erase(real_door);
doors.erase(primary_choice_door);
// На всякий пожарный проверим целостность данных.
assert(doors.size() == 1 || doors.size() == 2);

// Из оставшихся элементов (их может быть 1 или 2 штуки) выбираем дверь,
// которую откроет ведущий. reveal_door равно либо 1, либо 2.
int reveal_door = (std::rand() % doors.size()) + 1;

// i указывает на первый элемент в множестве (всего в нем 1 или 2 элемента).
std::set<int>::const_iterator i = doors.begin();
// Сдвигаем итератор на элемент, номер которого равен reveal_door.
// Можно было бы написать "if (reveal_door == 2) ++i;", но цикл как-то
// универсальнее.
while (--reveal_door) ++i;
reveal_door = *i;

// 'doors2' - это множество доступных дверей (1, 2, 3) для игрока,
// меняющего свой первоначальный выбор.
std::set<int> doors2(all_doors, all_doors + 3);

// Исключаем из множества дверей первый выбор игрока и
// и дверь, открытую ведущим.
doors2.erase(primary_choice_door);
doors2.erase(reveal_door);
// На всякий пожарный проверим целостность данных.
assert(doors2.size() == 1);

// В множестве оставшихся дверей будет только одна дверь, так как истинная
// дверь точно не равна двери, открытой ведущим, во второй выбор игрока
// точно отличается от первоначального. Поэтому просто берем из этого
// множества первый элемент.
int second_choice = *doors2.begin();

return real_door == second_choice;
}

int main() {
std::srand(std::time(0));
int guess_on_change = 0;
int guess_on_not_change = 0;
int N = 100000;
for (int i = 0; i < N; ++i) {
if (change_strategy())
guess_on_change = guess_on_change + 1;
if (no_change_strategy())
guess_on_not_change = guess_on_not_change + 1;
}
std::cout << "Вероятность выиграть при смене изначального выбора: "
<< guess_on_change * 1.0 / N << std::endl;
std::cout << "Вероятность выиграть не меняя изначального выбора: "
<< guess_on_not_change * 1.0 / N << std::endl;
return 0;
}
Компилируем и запускаем:
cl /EHsc /D_NDEBUG montihall.cpp && montihall
Результат подтверждает теорию:
Вероятность выиграть при смене изначального выбора: 0.67005
Вероятность выиграть не меняя изначального выбора: 0.33347
Лично я провел замечательные несколько часов, вспоминая всю эту тему условных вероятностей. А вы?

8 комментариев:

  1. Спасибо, очень интресно! Впервые познакомился с данной проблемой в последнем романе С. Лукьяненко "Недотепа", где решение было воспринято на интуитивном уровне. А тут, оказывается, есть и математическая аргументация! Воистину, заочное образование - это зло! :)

    ОтветитьУдалить
  2. На вики проводится интересная аналогия:
    1) Берутся 100 дверей
    2) Мы выбираем 1 дверь
    3) Ведущий открывает 98 неверных
    4) Остаются "наша" дверь и та которую не тронул ведущий

    В этом случае правильный ответ становится более очевиден.

    ОтветитьУдалить
  3. [k06a]: Разве? Тут тоже можно подумать так: ну раз вариантов осталось всего два, и один из них и так мой изначальный, получает куда ни крути 50/50. ;-)

    ОтветитьУдалить
  4. Этот комментарий был удален автором.

    ОтветитьУдалить
  5. k06a +1

    Когда меняешь свой выбор, то, как нетрудно понять, то если у тебя была призовая дверь - сменишь её на пустую, и наоборот: поменяешь пустую дверь на призовую. А вероятность из трёх дверей выбрать пустую больше чем вероятность выбрать призовую. Вот и всё - никаких теорем Байеса не надо. Это, кстати, в википедии написано "1.4 Словесное решение".

    ОтветитьУдалить
  6. Именно, вероятность в любом случае остаётся 50/50, т.е. 0.5, она конечно выше чем 0.3, но никак не становится 0.6

    ОтветитьУдалить
  7. То есть моя программа дает неправильные данные?

    ОтветитьУдалить
  8. Меня тоже интересовала когда то данная задача, тоже проводил эксперименты, недавно наткнулся на это видео и еще раз убедился в правильности решения при смене двери.
    http://univertv.ru/video/matematika/matematicheskaya_smes/matematicheskie_zagadki_i_paradoksy/paradoks_monti_holla/

    ОтветитьУдалить