Lex Kravetski (lex_kravetski) wrote,
Lex Kravetski
lex_kravetski

Categories:
  • Music:

Проблема трёх заключённых и парадокс Холла

Камрады напомнили благополучно и надолго мной забытый парадокс, который, хоть и просто сформулирован, весьма непрост для понимания. И, самое главное, если его всё-таки понять, это весьма хорошо укладывает в голову «физический смысл» понятия «вероятность». При этом парадокс вдобавок ярко иллюстрирует ошибки, которые возникают при попытке оценивать вероятность интуитивно из общих соображений.

Суть парадокса такая: в тюрьме сидят трое заключённых — А, Б и Ц. Всем троим вынесли смертный приговор, однако по случаю праздника и всего такого прочего глав-нач-пупс государства решил одного из них помиловать. В общем, своей волей он заменил один из приговоров со смертного на общественное порицание, однако заключённым про это говорить не разрешил, вплоть до дня X, когда как раз и состоится казнь. Но заключённые про такое решение прознали.

Заключённый А очень маялся и страдал от неопределённости и стал упрашивать охранника, чтобы тот сказал ему, что с ним будет. Охранник, памятуя приказ глав-нач-пупса, упорно отказывался. Ну просто наотрез. Тогда заключённый предложил охраннику хотя бы сказать, кого казнят из Б и Ц. Охранник понял, что если он огласит судьбу двоих других, то А наверняка вычислит и свою тоже, поэтому сказал только про одного. А именно: Б не помилован. Конечно, ему казалось, что огласив такую информацию, он никоим образом не раскрыл судьбу самого А.

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

Так вот, внимание, вопрос. Поменялась ли вероятность (и если да, то как) помилования заключённых А и Ц? Иными словами, если бы у А была чудесная возможность махнуться с Ц приговорами неглядя, то имело бы ему смысл такой возможностью воспользоваться?

Интуиция тут буквально-таки засыпает вариантами ответов. Самый первый из них — вероятности никак не изменились. Ведь вердикт вынесен до получения информации от охранника, поэтому как вероятность была 1/3 для каждого из заключённых, так и осталась. И смысла меняться никакого нет.

Чуть более напряжённая работа мысли в сопровождении некоторых минимальных знаний позволяет интуиции подсказать иное. А именно, вероятность помилования Б теперь стала равной нулю — ведь про него точно известно, что он не помилован. Но вероятность помилования остальных двоих до получения информации была 1/3 + 1/3 = 2/3. Что меньше единицы. То есть, как минимум у одного из заключённых вероятность помилования должна возрасти.

«У кого же?» — спросим мы интуицию. «У обоих», — ответит она. Ведь выбор изначально был равновероятный, теперь один отсеялся, но равновероятность не могла куда-то внезапно исчезнуть. Она наверно осталась, поэтому вероятность помилования каждого — 1/2. В сумме единица и равновероятно при этом. Меняться, стало быть, по-прежнему смысла нет.

Далее интуиция отягощается эмоциями с примеркой положения А на себя и рассуждениями о «вдруг он угадал, а поменяется!», но тут количественных критериев уже нет, одна только паника.

Ну так, верный-то ответ про одну вторую? Ответ неверный. Интуиция обманула.

Причём, сделала это настолько ловко и убедительно, что зачастую крайне тяжело бывает убедить людей, что ответ — иной. Я специально почитал мнения людей в интернете и с удивлением выяснил, что на данном парадоксе «срезаются» даже некоторые специалисты по теорверу и статистике, а уж про обычных людей говорить, так среди них это — обычное дело.

В общем, всё неочевидно. А чтобы стало очевиднее, мы рассмотрим несколько другую, сопряжённую с данной задачу, которая носит название «парадокс Холла».

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

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

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

Вопрос: имеет ли игроку смысл менять изначально выбранную дверь? И если да, то насколько возрастёт вероятность выигрыша автомобиля.

Если внимательно приглядеться к «парадоксу Холла», то станет понятно, что он очень сильно похож на проблему трёх заключённых. С тем отличием, что заключённый, в отличие от игрока, не выбирал изначально свою участь (то бишь, сам себя). Остальные же моменты совпадают. То есть, если первоначальный выбор не критичен, то обе задачи будут иметь один и тот же ответ с соответсвующей перефразировкой под условия («дверь» = «приговор», «коза» = «казнь», «автомобиль» = «помилование», «открытая дверь с козой за ней» = «информация о том, что Б не помилован»). Правда, тут есть ещё тонкий момент: в парадоксе Холла не говорится, какую дверь открыл ведущий, однако в проблеме заключённых известно, что указан именно Б. Этот нюанс обязательно будет разъяснён позже.

А пока вернёмся к игре в коз и автомобиль. Итак, игрок сделал выбор. Для определённости — это первая дверь (А). Ведущий открыл для определённости дверь Б. Имеет ли смысл игроку поменять свой выбор на дверь Ц? Как уже говорилось, интуиция нам подсказывает, что смысла никакого нет: ведь автомобиль был помещён за одну из дверей изначально, до выбора игрока и до подсказки ведущего. Следовательно, — говорит интуиция, — автомобиль либо за А, либо за Ц. Равновероятно.

Однако это не так. Наилучшим из известных мне ключей для понимания является вот какой: представим, что дверей не три, а сто. Игрок всё так же выбирает одну, а ведущий после этого открывает 98 дверей. Предлагая на выбор настоять на первоначальном выборе или выбрать 99-ю из оставшихся. Тут интуиция замолкает, понимая, что автомобиль ну просто наверняка за 99-й. Маловероятно ведь, что игрок угадал с первого раза (вероятность — 1/100). Ведущий же фактически неприкрыто сказал, за какой из оставшихся дверей находится автомобиль.

Способ апробации на предельных значениях — вообще очень мощный способ. При решении любой задачи в общем виде не просто имеет смысл, а обязательно надо пробовать решение именно на них — предельных значениях. Ведь зачастую решение для крайних точек вырождается в ощутимо более простое, нежели для рассматриваемого случая. И зачастую гораздо более очевидное. Если вы решаете задачу про десять объектов, примерьте решение (да и саму задачу тоже) на ноль объектов, один объект, два объекта и тысячу объектов. С большой вероятностью многое прояснится. Полного решения это, быть может, и не даст, но вот куда копать станет понятнее.

И действительно, открывание дверей — это для отвода глаз. На деле же ведущий предлагает выбор между дверью А и всеми остальными. Игру можно было бы переиначить: ведущий не просто открывает дверь, а предлагает игроку сменить свой выбор и при этом, если игрок с первого раза не угадает, то может попробовать ещё раз — пока не кончатся оставшиеся двери. Ну а поскольку в нашем случае «остальных» дверей всего две, то вероятности ровно так и распределяются — два к одному, две двери против одной. Две третих при смене выбора и одна третья в противном случае.

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

Каким же образом изначальная вероятность вдруг меняется? Да понятно теперь каким: правила игры изменились, информация изменилась, изменилась  — вероятность поэтому тоже изменилась.

Вероятность же, она не в природе вещей, как многим кажется, она — в моделях, которые строит человек для того, чтобы эти вещи описать. Глубинная суть вероятности состоит не в описании «физически случайной» природы явления, а в выборе наилучшей стратегии действий при заведомой неполноте информации и невозможности её восполнить. Пока игрок не знал, что за дверью Б коза, для него вероятность нахождения автомобиля за каждой из дверей была 1/3. Но когда он узнал, что находится за дверью Б, да ещё и вдобавок был в курсе, что ведущий не имеет права открывать дверь А, знания о явлении поменялись. Хотя козы с автомобилями остались всё там же.

Тут нет никакой мистики. Повторюсь, вероятность — это критерий выбора стратегии, который зависит от имеющейся о явлении информации. Ничего больше. Если бы мы имели возможность предсказать, как именно будет бросаться кубик, то вычислили бы на какую грань он упадёт. С вероятностью единица, а не одна шестая. Одна шестая — только потому, что мы не можем предсказать необходимые для точных вычислений нюансы броска.

Собственно, вся парадоксальность двух рассматриваемых задач заключена строго в непонимании «физического смысла» вероятности. На деле никакого парадокса нет.

С парадоксами, кстати, всегда так: они либо результат непонимания, либо результат вынесения теории за область её определения.

Теперь вернёмся к проблеме трёх заключённых. Как уже говорилось, она идентична игре в коз и автомобиль. То есть, ответ: да, имеет смысл махнуться приговорами неглядя. И с вероятностью 2/3 помилование у заключённого А в кармане.

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

А ответ не меняется. Совершенно всё равно, выбирал ли игрок дверь наугад или ему принудительно вручили первую. Выбор всё равно идёт между одной дверью и двумя. С заключёнными ровно так же: заключённый А выбирает между своим приговором и наилучшим из приговоров Б и Ц. Опять же можно переформулировать: «ты имеешь право взять приговор любого из Б и Ц, а если он всё-таки окажется смертным, то поменять его на оставшийся приговор».

И всё-таки остаётся чувство некоторой неизъяснимой потери: а ну как оправдательный приговор вынесли именно А? Не прогадает ли он в этом случае. Может, конечно, и прогадать. Но вероятность такого вдвое меньше, чем вероятность прогадать в противоположном случае. То есть, если бы этот бесчеловечный эксперимент проводился много раз, то регулярный обмен приговорами повысил бы выживаемость вдвое.

Осталось последнее возражение: это ведь всё слова-слова, а как быть с точным математическим подходом? Вон она, таблица-то. В ней всего три варианта.

АБЦ
100
010
001

(1 — оправдательный приговор, 0 — смертный)

Охранник «вычеркнул» второй вариант. Остались, соответственно, первый и третий. Откуда вдруг возьмётся перекос в вероятностях? Два варианта только. У каждого вероятность — 1/2.

Дело в том, что сам подход неправильный — таблица у нас несколько иного рода.

АБЦ
100
100
010
001

(серым тут помечен выбор охранника)

Иными словами, возможных вариантов у нас четыре. Но они при этом не являются равновероятными. Ведь если оправдательный приговор вынесен Б или Ц, то охранник ограничен в своём выборе Ц или Б, соответственно. В случае же оправдательного приговора для А охранник может выбрать как Б, так и Ц, причём сумма условных (при условии, что помилован именно А) вероятностей этих вариантов — единица. Если предположить, что выбор охранника в данном случае абсолютно случаен, то условная вероятность  каждого варианта — 1/2. Безусловная же вероятность «выпадения» каждого из них (в том случае, что выбор охранника абсолютно случаен) 1/3 * 1/2  = 1/6 — произведение вероятности того, что помилован А на вероятность того, что охранник выбрал при этом одного из Б и Ц. Последние же две строки таблицы соответствуют вероятности 1/3.

АБЦВероятность
1001/6
1001/6
0101/3
0011/3

Иными словами, при любом ответе охранника, вероятность того, что помилован второй из оставшихся заключённых (не названый охранником), вдвое больше вероятности того, что помилован сам А (1/3 + 1/3 против 1/6 + 1/6).

Тут важно имено «неназванный из оставшихся». Ведь речь идёт именно о стратегии для А — не о его тактике в одной конкретной реализации события. Со стратегической точки зрения А имеет смысл всегда соглашаться на обмен приговорами с неназванным охранником заключённым. Поэтому имеет смысл согласиться и в конкретной реализации, сформулированной в задаче.

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

Наконец, имеет смысл рассмотреть ещё один парадоксальный нюанс, о котором при рассмотрении проблемы трёх заключённых почему-то умалчивают. Положим, что охраннику задал вопрос не только А, но и Ц тоже. И получил, соответственно, ровно тот же ответ: Б не помилован. Повторив для Ц рассуждения, проделанные для А, мы придём к занимательному выводу: для Ц вероятность того, что А помилован, вдвое больше, чем того, что помилован он сам. То есть, для А с вероятностью 2/3 помилован Ц, а для Ц с вероятностью 2/3 помилован А. Обменявшись, они оба вдвое повысят вероятность своего помилования. Таковое кажется абсурдным.

Однако стоит взглянуть на таблицу, как становится видно, что ничего парадоксального тут нет. В данном конкретном раскладе — да, один из них прогадает. Однако такой расклад реализуется лишь в двух третях случаев. В одной же трети случаев охранник не сможет сказать обоим, что Б не помилован, поскольку Б как раз помилован. И вот эта треть случаев и обеспечивает стратегический выигрыш обмена — на длинной серии экспериментов и А, и Ц меняя свой выбор на неназванного охранником заключённого будут выживать с вероятностью 2/3. Правда, в некоторых случаях им обоим придётся меняться приговорами с одним и тем же заключённым — Б. Чего, по-видимому, им сделать не дадут.

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

Надеюсь, что читателей после всего этого настигло просветление.

 

UPDATE: Ради интереса численно проверил, поменяется ли что-нибудь, если ведущий при возможности открыть обе двери будет делать выбор не случайным образом, а строго в пользу самой левой из них. Оказалось, ничего не поменяется. Как и следовало ожидать.

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


public class Main {
         static int main = 0;
          static int other = 0;
          public static void main( String[] args ) {
                  int expNum = 1000000;
                 for ( int i = 0; i < expNum; i++ ) {
                         experiment();
                 }
                 System.out.println( (double) main / expNum + " " + (double) other / expNum );
         }
 
          private static void experiment() {
                 int car = (int) ( Math.random() * 3 );
                 int chosen = (int) ( Math.random() * 3 ); //Можете сюда подставить ноль вместо случайного числа. Тогда получится задача про заключённых.
                  int opened = 0;
 
                  // Оптимизации тут специально нет. Чтобы ещё и в ней не пытались ошибки искать.
                 do {
                         opened = (int) ( Math.random() * 3 );
                 } while ( ( opened == car ) || ( opened == chosen ) );
 
                  for ( int i = 0; i < 3; i++ ) {
                         if (car == i) {
                                 if (i == chosen) {
                                         main++;
                                 } else {
                                         other++;
                                 }
                         }
                 }
         } 
}
Tags: контрманипуляция сознанием, статистика
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 198 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →