Проблема трех заключенных

Задача трех заключенных появилась в Мартина Гарднера « Математические игры колонке » в журнале Scientific American в 1959 году. ^[1]^[2] Математически это эквивалентно задаче Монти Холла , в которой автомобиль и коза заменены соответственно свободой и казнью. ^[3]

Проблема

Трое заключенных, А, Б и С, содержатся в отдельных камерах и приговорены к смертной казни. Губернатор наугад выбрал одного из них для помилования. Начальник тюрьмы знает, кто из них помилован, но не имеет права говорить об этом. Заключенный А умоляет надзирателя сообщить ему личность одного из двоих, которых собираются казнить. «Если нужно помиловать Б, назовите мне имя С. Если нужно помиловать С, назовите мне имя Б. А если меня нужно помиловать, тайно подбросьте монетку, чтобы решить, назвать ли имя Б или С».

Надзиратель сообщает А, что Б должен быть казнен. Заключенный А доволен, потому что считает, что его вероятность выжить возросла с ⁠ 1 / 3 ⁠ до ⁠ 1 / 2 ⁠ , как сейчас между ним и C. Заключенный А тайно сообщает новость C, который считает, что шансы A на помилование не изменились в ⁠ 1 / 3 ⁠ , но он доволен, потому что его собственный шанс увеличился до ⁠ 2 / 3 ⁠ . Кто из заключенных прав?

Решение

Ответ заключается в том, что заключенный А не получил никакой информации о своей судьбе, поскольку он уже знал, что надзиратель назовет ему чужое имя. Заключенный А, до получения известия от начальника тюрьмы, оценивает свои шансы на помилование как ⁠ 1 / 3 ⁠ , то же самое, что и B, и C. Как говорит надзиратель, B будет казнен, либо потому, что C будет помилован ( ⁠ 1/3 шанс) , ⁠ или А будет помилован ( ⁠ 1 / 3 ⁠ шанс), и монета, чтобы решить, назвать ли имя B или C, которую подбросил надзиратель, выпала B ( ⁠ 1/2 ⁠ ; шанс в целом ⁠ 1 / 2 ⁠ × ⁠ 1 / 3 ⁠ = ⁠ 1/6 шанс , что ⁠ B был назван, потому что A будет помилован). Следовательно, после того, как он узнал, что B будет казнен, оценка шансов A на помилование вдвое меньше, чем у C. Это означает, что его шансы на помилование, теперь зная, что B не будет помилован, снова равны ⁠ 1/3 , ⁠ но C имеет ⁠ 2/3 ⁠ шанс быть . помилованным

Стол

Объяснение, приведенное выше, можно резюмировать в следующей таблице. Поскольку А спрашивает надзирателя, он может ответить только Б или С, чтобы его казнили (или «не помиловали»).

Быть помилованным	Надзиратель: «не Б»	Надзиратель: «не С»	Сумма
А	1/6	1/6	1/3
Б	0	1/3	1/3
С	1/3	0	1/3

Поскольку надзиратель ответил, что Б не будет помилован, решение исходит из второй колонки «не Б». Похоже, что шансы на помилование А против С составляют 1:2.

Математическая формулировка

Вызов $A$ , $B$ и $C$ события, при которых соответствующий заключенный будет помилован, и $b$ Если надзиратель сообщает А, что заключенный Б должен быть казнен, то, используя теорему Байеса , апостериорная вероятность помилования А равна: ^[4]

{\begin{aligned}P(A|b)&={\frac {P(b|A)P(A)}{P(b|A)P(A)+P(b|B)P(B)+P(b|C)P(C)}}\\&={\frac {{\tfrac {1}{2}}\times {\tfrac {1}{3}}}{{\tfrac {1}{2}}\times {\tfrac {1}{3}}+0\times {\tfrac {1}{3}}+1\times {\tfrac {1}{3}}}}={\frac {1}{3}}.\end{aligned}}

С другой стороны, вероятность того, что C будет помилован, равна:

{\begin{aligned}P(C|b)&={\frac {P(b|C)P(C)}{P(b|A)P(A)+P(b|B)P(B)+P(b|C)P(C)}}\\&={\frac {1\times {\tfrac {1}{3}}}{{\tfrac {1}{2}}\times {\tfrac {1}{3}}+0\times {\tfrac {1}{3}}+1\times {\tfrac {1}{3}}}}={\frac {2}{3}}.\end{aligned}}

Решающее различие, делающее A и C неравными, заключается в том, что $P(b|A)={\tfrac {1}{2}}$ но $P(b|C)=1$ . Если А будет помилован, надзиратель может сказать А, что казнить следует либо Б, либо С, и, следовательно, $P(b|A)={\tfrac {1}{2}}$ ; тогда как, если C будет помилован, надзиратель может только сказать A, что B казнен, поэтому $P(b|C)=1$ .

Интуитивное объяснение

У заключенного А есть только ⁠ 1/3 на ⁠ шанс помилование. Знание того, будет ли казнен B или C, не меняет его шансов. Узнав, что Б будет казнен, заключенный А понимает, что, если он сам не получит помилования, то оно должно быть направлено только к С. Это означает, что у С есть шанс 2/3 получить помилование. Это сравнимо с проблемой Монти Холла .

Перечень возможных случаев

Могут возникнуть следующие сценарии:

А помилован, и надзиратель предлагает казнить Б: ⁠ 1 / 3 ⁠ × ⁠ 1 / 2 ⁠ = ⁠ 1 / 6 ⁠ случаев
А помилован, и надзиратель предлагает казнить С: ⁠ 1 / 3 ⁠ × ⁠ 1 / 2 ⁠ = ⁠ 1 / 6 ⁠ случаев
Б помилован, и надзиратель предлагает казнить С: ⁠ 1 / 3 ⁠ случаев
C помилован, и надзиратель предлагает казнить B: ⁠ 1 / 3 ⁠ случаев

При условии, что надзиратель будет выбирать случайным образом, в ⁠ 1/3 времени , в ⁠ течение которого А подлежит помилованию, ⁠ 1/2 шанс , ⁠ что он скажет Б и ⁠ 1/2 шанс , что ⁠ он скажет C. Это означает, что в целом, ⁠ 1 / 6 ⁠ времени ( ⁠ 1 / 3 ⁠ [что А помилован] × ⁠ 1 / 2 ⁠ [этот надзиратель говорит B]), надзиратель скажет B, потому что A будет помилован, и ⁠ 1 / 6 ⁠ времени ( ⁠ 1 / 3 ⁠ [что А помилован] × ⁠ 1 / 2 ⁠ [этот надзиратель говорит C]) он скажет C, потому что A помилован. Это в сумме составляет ⁠ 1 / 3 ⁠ времени ( ⁠ 1 / 6 ⁠ + ⁠ 1 / 6 ⁠ ) А прощается, и это правда.

Теперь ясно, что если надзиратель ответит Б на А ( ⁠ 1/2 то всех ⁠ случаев), ⁠ 1/3 и ⁠ только времени, когда C будет помилован, а A все равно будет казнен (случай 4), ⁠ 1/6 ) ⁠ . времени помилования А (случай 1 Следовательно, шансы C равны ( ⁠ 1 / 3 ⁠ )/( ⁠ 1 / 2 ⁠ ) = ⁠ 2/3 и ( ⁠ А равны ⁠ 1 / 6 ⁠ )/( ⁠ 1 / 2 ⁠ ) = ⁠ 1 / 3 ⁠ .

Ключом к этой проблеме является то, что надзиратель может не назвать имя заключенного, который будет помилован. Если мы устраним это требование, это может продемонстрировать исходную проблему другим способом. Единственное изменение в этом примере заключается в том, что заключенный А просит надзирателя раскрыть судьбу одного из других заключенных (не указывая, кто будет казнен). В этом случае надзиратель подбрасывает монету и выбирает один из B и C, чтобы раскрыть судьбу. Случаи следующие:

А помилован, надзиратель говорит: Б казнён( ⁠ 1 / 6 ⁠ )
Помилованный, надзиратель говорит: C казнён( ⁠ 1 / 6 ⁠ )
Б помилован, надзиратель говорит: Б помилован ( ⁠ 1 / 6 ⁠ )
Б помилован, надзиратель говорит: С казнен ( ⁠ 1 / 6 ⁠ )
C помилован, надзиратель говорит: B казнен ( ⁠ 1 / 6 ⁠ )
C помилован, надзиратель говорит: C помилован ( ⁠ 1 / 6 ⁠ )

Каждый сценарий имеет ⁠ 1/6 вероятность ⁠ . Исходную задачу о трех заключенных можно рассматривать в следующем свете: у надзирателя в этой задаче все еще есть шесть ящиков, в каждом из которых есть ⁠ 1/6 ⁠ возникновения . вероятность Однако надзиратель в первоначальном случае не может раскрыть судьбу помилованного заключенного. Таким образом, например, в случае 3, поскольку сказать «Б помилован» невозможно, надзиратель вместо этого говорит «С казнен» (что делает его таким же, как в случае 4). Это оставляет случаи 4 и 5 каждый с ⁠ 1/3 . раньше ⁠ вероятность возникновения и оставляет нас с той же вероятностью, что и

Почему парадокс?

Склонность людей давать ответ 1/2, скорее всего, связана с тенденцией игнорировать контекст, который может показаться незначительным. Например, то, как вопрос задан надзирателю, может повлиять на ответ. Это можно показать, рассмотрев модифицированный случай, когда $P(A)={\frac {1}{4}},P(B)={\frac {1}{4}},P(C)={\frac {1}{2}}$ и все остальное, касающееся проблемы, остается прежним. ^[4] Еще раз воспользуемся теоремой Байеса:

{\begin{aligned}P(A|b)&={\frac {{\tfrac {1}{2}}\times {\tfrac {1}{4}}}{{\tfrac {1}{2}}\times {\tfrac {1}{4}}+0\times {\tfrac {1}{4}}+1\times {\tfrac {1}{2}}}}={\frac {1}{5}}.\end{aligned}}

Однако если А просто спросит, будет ли казнен Б, и надзиратель ответит «да», вероятность того, что А будет помилован, составит:

{\begin{aligned}P(A|b)&={\frac {1\times {\tfrac {1}{4}}}{1\times {\tfrac {1}{4}}+0\times {\tfrac {1}{4}}+1\times {\tfrac {1}{2}}}}={\frac {1}{3}}.\end{aligned}}

^[4]

Аналогичное предположение состоит в том, что А планирует заранее запросить эту информацию у начальника тюрьмы. Аналогичный вышеописанному случай возникает, если А не планирует ничего спрашивать у надзирателя, а надзиратель просто сообщает ему, что он будет казнить Б. ^[5]

Еще одно предположение, которое, вероятно, упускают из виду, заключается в том, что у начальника тюрьмы есть вероятностный выбор. Давайте определим $p$ как условная вероятность того, что надзиратель назовет B при условии, что C будет казнен. Условная вероятность $P(A|b)$ тогда можно выразить как: ^[6]

{\begin{aligned}P(A|b)&={\frac {p}{p+1}}\end{aligned}}

Если мы предположим, что $p=1$ , то есть мы не учитываем, что надзиратель делает вероятностный выбор, тогда $P(A|b)={\frac {1}{2}}$ . Однако реальность проблемы в том, что надзиратель подбрасывает монетку ( $p={\frac {1}{2}}$ ), так $P(A|b)={\frac {1}{3}}$ . ^[5]

Джудея Перл (1988) использовал вариант этого примера, чтобы продемонстрировать, что обновление убеждений должно зависеть не только от наблюдаемых фактов, но и от эксперимента (т. е. запроса), который привел к этим фактам. ^[7]

Связанные проблемы и приложения

Проблема Монти Холла
Парадокс мальчика или девочки
Принцип ограниченного выбора , применение в карточном бридже
Дилемма заключённого , теории игр. проблема
Проблема Спящей Красавицы
Проблема с двумя конвертами

Ссылки

^ Гарднер, Мартин (октябрь 1959 г.). «Математические игры: задачи, связанные с вопросами вероятности и неоднозначности». Научный американец . 201 (4): 174–182. дои : 10.1038/scientificamerican1059-174 .
^ Гарднер, Мартин (1959). «Математические игры: как три современных математика опровергли знаменитую гипотезу Леонарда Эйлера». Научный американец . 201 (5): 188. doi : 10.1038/scientificamerican1159-181 .
^ Бейли, Херб (2000). «Монти Холл использует смешанную стратегию». Журнал «Математика» . 73 (2): 135–141. JSTOR 2691085 .
^ Перейти обратно: ^а ^б ^с Симодзё, Синсуке; Итикава, Синъити (август 1990 г.). «Интуитивные рассуждения о вероятности: Теоретический и экспериментальный анализ «проблемы трех заключенных» ». Познание . 36 (2): 205. дои : 10.1016/0010-0277(89)90012-7 . ПМИД 2752704 . S2CID 45658299 .
^ Перейти обратно: ^а ^б Векслер, Серджио; Эстевес, Л.Г.; Симонис, А.; Пейшото, К. (февраль 2005 г.). «Безразличие, нейтралитет и информативность: обобщение парадокса трех узников» . Синтезируйте . 143 (3): 255–272. дои : 10.1007/s11229-005-7016-1 . JSTOR 20118537 . S2CID 16773272 . Проверено 15 декабря 2021 г.
^ Биллингсли, Патрик (1995). Вероятность и мера . Серия Уайли по вероятности и математической статистике (третье издание оригинального издания 1979 г.). Нью-Йорк: John Wiley & Sons, Inc., упражнение 33.3, стр. 441 и 576. ISBN. 0-471-00710-2 . МР 1324786 .
^ Перл, Дж. (1988). Вероятностные рассуждения в интеллектуальных системах: сети правдоподобного вывода (первое изд.). Сан-Матео, Калифорния: Морган Кауфманн.

Дальнейшее чтение

Фредерик Мостеллер , Пятьдесят сложных задач теории вероятности , с. 28, в Google Книгах .
Ричард Айзек, «Удовольствия от вероятности» , с. 24, в Google Книгах .

[1] Гарднер, Мартин (октябрь 1959 г.). «Математические игры: задачи, связанные с вопросами вероятности и неоднозначности». Научный американец . 201 (4): 174–182. дои : 10.1038/scientificamerican1059-174 .

[Gardner1959b-2] Гарднер, Мартин (1959). «Математические игры: как три современных математика опровергли знаменитую гипотезу Леонарда Эйлера». Научный американец . 201 (5): 188. doi : 10.1038/scientificamerican1159-181 .

[3] Бейли, Херб (2000). «Монти Холл использует смешанную стратегию». Журнал «Математика» . 73 (2): 135–141. JSTOR 2691085 .

[Shimojo-4] Перейти обратно: ^а ^б ^с Симодзё, Синсуке; Итикава, Синъити (август 1990 г.). «Интуитивные рассуждения о вероятности: Теоретический и экспериментальный анализ «проблемы трех заключенных» ». Познание . 36 (2): 205. дои : 10.1016/0010-0277(89)90012-7 . ПМИД 2752704 . S2CID 45658299 .

[Wechsler-5] Перейти обратно: ^а ^б Векслер, Серджио; Эстевес, Л.Г.; Симонис, А.; Пейшото, К. (февраль 2005 г.). «Безразличие, нейтралитет и информативность: обобщение парадокса трех узников» . Синтезируйте . 143 (3): 255–272. дои : 10.1007/s11229-005-7016-1 . JSTOR 20118537 . S2CID 16773272 . Проверено 15 декабря 2021 г.

[6] Биллингсли, Патрик (1995). Вероятность и мера . Серия Уайли по вероятности и математической статистике (третье издание оригинального издания 1979 г.). Нью-Йорк: John Wiley & Sons, Inc., упражнение 33.3, стр. 441 и 576. ISBN. 0-471-00710-2 . МР 1324786 .

[7] Перл, Дж. (1988). Вероятностные рассуждения в интеллектуальных системах: сети правдоподобного вывода (первое изд.). Сан-Матео, Калифорния: Морган Кауфманн.

[1]

[2]

[3]

[4]

[5]

[6]

[7]