Должен признаться, я невероятный профан в теории вероятностей, а наука эта крайне содержательная, глубокая и позволяет ученым очень часто решать задачи, для которых стандартные методы поиска решений оказываются бесполезными или безумно сложными. Плохо владею вероятностью я только лишь от того, что курсы по теорверу в бакалавриате слушал очень уж шапочно, а в дальнейшем повторения и закрепления материала не случилось. Увы и ах.
Тем не менее, душа просит прекрасного, и захотелось написать о двух красивых и до неприличия попсовых задачах (более того - задачи даже не совсем про теорию вероятностей, а всего лишь «по мотивам»). Если вы хоть сколько-нибудь имели в жизни отношение к математике, шансы почти стопроцентные что ничего нового сегодня здесь не прочитаете. Но вдруг? Идея написать такую заметку пришла после рекомендации одного очень гордого анонима (ДПС), за что ему большая благодарность. Для тех кто «в танке» достаточно будет одной картиночки чтобы понять в каком ключе пойдет рассказ:
Первый сюжет, о котором поговорим, это заезженный всеми парадокс Монти-Холла (коза бесстыдно намекала). Для тех кто по какой-то причине еще не слышал про этот парадокс коротко опишу условие задачи откуда он родился:
Вы — участник телевизионной викторины. Правила просты: перед Вами три двери, за одной из них большой денежный приз (например — автомобиль), за двумя другими — козы. Телеведущий предлагает Вам выбрать дверь, за которой по Вашему предположению находится приз, Вы её называете. После этого ведущий открывает одну из двух оставшихся невыбранными дверей, за которой обязательно стоит коза, и предлагает Вам возможность изменить свой выбор. Вы можете либо выбрать другую неоткрытую ведущим дверь, либо не поменять мнения и настоять на выбранной ранее двери. После этого ведущий открывает ту дверь, которую Вы окончательно называете, и если за ней приз, то Вы его забираете. Если там коза — Вы не получаете ничего.
Вопрос: меняются ли шансы на Вашу победу если Вы поменяете свое первоначальное решение после того, как ведущий открывает дверь за которой точно находится коза?
Откуда же здесь взяться парадоксу? На первый взгляд кажется, что шансы игрока никак не меняются после того, как ведущий открывает дверь за которой коза — всё ещё остаются две двери, и шансы на победу как-будто бы 50 на 50.
Именно здесь и зарыто противоречие нашей интуиции, на самом деле действие ведущего вносит невероятно большой вклад в информацию о системе, и шансы на победу, оказывается, значительно увеличиваются, если Вы будете всегда менять свой первоначальный выбор. Но почему же так? Здесь на помощь приходит статья с википедии и одна восхитительная иллюстрация:
Несложно понять, что если Вы будете менять решение после действий ведущего, то в 2 из 3 случаев Вы будете побеждать, и вот почему:
- Если изначально Вы выбрали дверь с призом (1 случай из 3), то смена решения приведет к проигрышу.
- Если изначально Вы выбрали дверь с козой (2 случая из 3), то смена решения приведет к победе (потому что ведущий откроет дверь с "козой" и изменит информацию о системе).
На бумаге все гладко, но мне очень нравится проверять такие вещи на практике. Давайте набросаем короткую симуляцию:
Примеры вывода указаны в коде, действительно шансы увеличиваются примерно до 2/3 если менять дверь. Это и есть парадокс, потому что нам кажется что так быть не должно, но бессердечная вероятность нас водит за нос.
Однако история про Монти-Холла это только цветочки. Ягодки, собственно, и притащил гордый аноним (ДПС), задав мне не менее попсовую задачу (о которой я, к сожалению, раньше не слышал ничего), задачу о заключенных и коробках:
Есть сто заключенных, у каждого свой номер (от 1 до 100). Их номера написали на бумажках и разложили в сто коробок, на каждой коробке тоже есть свой номер. Номера по коробкам раскладывали случайным образом, но в каждой коробке есть бумажка с номером заключенного. Заключенные должны будут по одному заходить в комнату, им можно будет открыть пятьдесят коробок, и задача каждого — найти свой собственный номер на бумажке. Если хотя бы один не найдет своего номера, всех заключенных казнят. Если каждый найдет свой номер, всех помилуют. Во время испытания заключенные никак не могут переговариваться или видеть друг друга.
Существует ли стратегия с приемлемыми шансами заключенных выжить (хотя бы более чем 1 к 100)?
Откровенно сказать, я сразу не смог придумать ничего толкового. Понятно, что если выбрать фиксированный набор для просмотра для всех, то все точно проиграют (хотя бы потому что открыть можно не более 50 коробок). Таким образом, каждый должен будет просматривать свой уникальный набор коробок, но как его выбирать? Если выбирать случайно, то каждый найдет свой номер с вероятностью 0.5, а значит 100 человек найдут свои номера с общей вероятностью (0.5)^100, а это невероятно малое число. В итоге мне все же понадобились подсказки, и снова спасибо википедии за отличный разбор. Оказывается есть очень простая и очень даже хорошая (по меркам такой сложной ситуации для заключенных) стратегия просмотра коробок:
Пусть у заключенного номер i. Он смотрит сначала коробку со своим номером, т.е. коробку с номером i. Если в коробке i лежит бумажка, на которой написан номер i, то поиск окончен. Иначе, он берет номер j, который написан на бумажке в этой коробке, и смотрит теперь коробку с номером j. Если в ней бумага с номером i, то можно остановиться, иначе повторяем процедуру, до тех пор пока не исчерпаем ходы (50 просмотров) или не найдем свой номер.
Все дело в том, что все эти коробки и номера по существу являются просто перестановкой. Проигрыш в указанной выше стратегии произойдет только в случае, если в нашей перестановке находится цикл длины больше 50, а это случается далеко не всегда (лишь с вероятностью близкой к 0.69, за подробностями доказательства отсылаю снова на википедию).
Таким образом, шансы на успех должны быть примерно равны 0.31 у заключенных, а это совсем недурно. Здесь все кажется уже не так интуитивно понятно как с Монти-Холлом, поэтому вдвойне хочется провести симуляцию:
Вот это уже вызвало у меня настоящее удивление и восторг, такой простой принцип приводит к очень серьезным успехам, главное правильно осознать математическую суть задачи (а именно то, что речь всего лишь о перестановках, про которые мы какие-то общие закономерности можем понять). Хотя, конечно, если Вы эту задачу уже видели, или просто хорошо учили теорию вероятностей, то никакого удивления у Вас не случится. =)
На сегодня у меня всё, большое спасибо за внимание! Подписывайтесь на канал и ставьте лайки, если Вам понравился материал.
Желаю Вам чаще делать во всех смыслах правильный выбор и не попадаться на удочку парадоксов!