Проблема трех узников - Three Prisoners problem

Не путать с Дилемма заключенного или же Парадокс палача.

В Проблема трех узников появился в Мартин Гарднер "s"Математические игры "столбец в Scientific American в 1959 г.^[1][2] Это математически эквивалентно Проблема Монти Холла с машины и козла заменены на свободу и казнь соответственно.

Проблема

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

Смотритель говорит А, что Б. должен быть казнен. Заключенный A доволен, потому что он считает, что его вероятность выжить увеличилась с 1/3 до 1/2, как сейчас между ним и C. Заключенный A тайно сообщает новости 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 шанса на помилование.

Стол

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

Прощение	Надзиратель: «не Б»	Надзиратель: "не C"	Сумма
А	1/6	1/6	1/3
B	0	1/3	1/3
C	1/3	0	1/3

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

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

Вызов ${\displaystyle A}$, ${\displaystyle B}$ и ${\displaystyle C}$ события, когда соответствующий заключенный будет помилован, и ${\displaystyle b}$ если надзиратель сообщает А, что заключенного Б следует казнить, затем, используя Теорема Байеса, апостериорная вероятность помилования А составляет:

${\displaystyle {\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}}}}={\tfrac {1}{3}}.\end{aligned}}}$

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

${\displaystyle {\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}}}}={\tfrac {2}{3}}.\end{aligned}}}$

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

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

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

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

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

1. A помилован, и надзиратель упоминает, что B должен быть казнен: 1/3 × 1/2 = 1/6 случаев
2. А помилован, и надзиратель упоминает, что С должен быть казнен: 1/3 × 1/2 = 1/6 случаев
3. B помилован, и надзиратель упоминает, что C будет казнен: 1/3 случаев
4. C помилован, и надзиратель упоминает, что B должен быть казнен: 1/3 случаев

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

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

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

1. Помилованный надзиратель говорит: B казнен (1/6)
2. Помилованный надзиратель говорит: C казнен (1/6)
3. B помилован, надзиратель говорит: B помилован (1/6)
4. B помилован, смотритель говорит: C казнен (1/6)
5. C помилован, смотритель говорит: B казнен (1/6)
6. C помилован, надзиратель говорит: C помилован (1/6)

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

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

Тенденция людей давать ответ 1/2 игнорирует тот факт, что надзиратель мог подбросить монетку до того, как дал свой ответ. Надзиратель, возможно, ответил ${\displaystyle B}$ потому что ${\displaystyle A}$ должен быть выпущен, и он подбросил монетку. Или же, ${\displaystyle C}$ должен быть выпущен. Но вероятности двух событий не равны.

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

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

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

Примечания

1. Гарднер, Мартин (октябрь 1959). «Математические игры: задачи, связанные с вопросами вероятности и двусмысленности». Scientific American. 201 (4): 174–182. Дои:10.1038 / Scientificamerican1059-174.
2. Гарднер, Мартин (1959). «Математические игры: как три современных математика опровергли знаменитую гипотезу Леонарда Эйлера». Scientific American. 201 (5): 188. Дои:10.1038 / scientificamerican1159-181.
3. Перл, Дж. (1988). Вероятностное мышление в интеллектуальных системах: сети правдоподобных выводов (Первое изд.). Сан-Матео, Калифорния: Морган Кауфманн.

Рекомендации

• Фредерик Мостеллер: Пятьдесят сложных проблем вероятности. Dover 1987 (перепечатка), ISBN  0-486-65355-2, п. 28-29 (ограниченная онлайн-версия, п. 28, в Google Книги )
• Ричард Исаак: Удовольствия от вероятности. Springer 1995, ISBN  978-0-387-94415-9, п. 24-27 (ограниченная онлайн-версия, п. 24, в Google Книги )