Problem trzech więźniów - Three Prisoners problem

Problem Trzech Więźniów pojawił się w rubryce „ Gry matematyczne ” Martina Gardnera w „ Scientific American” w 1959 roku. Jest matematycznym odpowiednikiem problemu Monty'ego Halla, w którym samochód i kozę zastąpiono odpowiednio wolnością i wykonaniem.

Problem

Trzech więźniów, A, B i C, jest w osobnych celach i skazanych na śmierć. Gubernator wybrał losowo jednego z nich do ułaskawienia. Naczelnik wie, który z nich jest ułaskawiony, ale nie może powiedzieć. Więzień A błaga naczelnika o podanie tożsamości jednego z dwóch, którzy mają zostać straceni. „Jeśli B ma być ułaskawiony, podaj mi imię C. Jeśli C ma być ułaskawione, podaj mi imię B. A jeśli mam być ułaskawiony, potajemnie rzucaj monetą, aby zdecydować, czy nazwać B, czy C”.

Naczelnik mówi A, że B ma zostać stracony. Więzień A jest zadowolony, ponieważ wierzy, że jego prawdopodobieństwo przeżycia wzrosło z 1/3 do 1/2, tak jak to ma miejsce teraz między nim a C. Więzień A potajemnie przekazuje C wiadomość, kto argumentuje, że szansa A na ułaskawienie jest bez zmian na poziomie 1/3, ale jest zadowolony, ponieważ jego własna szansa wzrosła do 2/3. Który więzień ma rację?

Rozwiązanie

Odpowiedź brzmi, że więzień A nie uzyskał żadnych informacji o własnym losie, ponieważ wiedział już, że naczelnik nada mu czyjeś imię. Więzień A, przed wysłuchaniem naczelnika, szacuje swoje szanse na ułaskawienie na 1/3, tak samo jak B i C. Jak naczelnik mówi, że B zostanie stracony, dzieje się tak dlatego, że C zostanie ułaskawiony (1/3 szansa) lub A zostanie ułaskawiony (1/3 szansy) i moneta, aby zdecydować, czy nazwać B lub C, który obrócił strażnik, wypadła B (1/2 szansy; dla całości 1/2 × 1/3 = 1/ 6 szansa B została wymieniona, ponieważ A zostanie ułaskawiony). Zatem po usłyszeniu, że B zostanie stracony, szacunkowa szansa A na zostanie ułaskawiona jest o połowę mniejsza niż C. Oznacza to, że jego szanse na ułaskawienie, teraz wiedząc, że B nie jest, znowu są 1/3, ale C ma 2/ 3 szanse na ułaskawienie.

Tabela

Powyższe wyjaśnienie można podsumować w poniższej tabeli. Gdy naczelnik jest proszony przez A, może on odpowiedzieć tylko B lub C, aby został stracony (lub „nie ułaskawiony”).

Ułaskawienie	Strażnik: „nie B”	Strażnik: „nie C”	Suma
A	1/6	1/6	1/3
b	0	1/3	1/3
C	1/3	0	1/3

Ponieważ naczelnik odpowiedział, że B nie będzie ułaskawiony, rozwiązanie pochodzi z drugiej kolumny „nie B”. Wydaje się, że szanse na ułaskawienie A vs. C wynoszą 1:2.

Sformułowanie matematyczne

Zadzwoń , a zdarzenia, w których odpowiedni więzień zostanie ułaskawiony, oraz zdarzenie, w którym naczelnik poinformuje A, że więzień B ma zostać stracony, to, korzystając z twierdzenia Bayesa , prawdopodobieństwo późniejszego ułaskawienia A wynosi: ${\ Displaystyle A}$${\ Displaystyle B}$${\displaystyle C}$${\displaystyle b}$

${\ Displaystyle {\ zacząć {wyrównany} P (A | b) i = {\ 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{wyrównany}}}$

Z drugiej strony prawdopodobieństwo ułaskawienia C wynosi:

${\ Displaystyle {\ zacząć {wyrównany} P (C | b) i = {\ 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{wyrównany}}}$

Kluczową różnicą, która sprawia, że ​​A i C są nierówne, jest to, że ale . Jeśli A zostanie ułaskawiony, naczelnik może powiedzieć A, że ma zostać stracony B lub C, a zatem ; podczas gdy C zostanie ułaskawiony, naczelnik może tylko powiedzieć A, że B został stracony, więc . ${\ Displaystyle P (b | A) = {\ tfrac {1} {2}}}$${\ Displaystyle P (b | C) = 1}$${\ Displaystyle P (b | A) = {\ tfrac {1} {2}}}$${\ Displaystyle P (b | C) = 1}$

Intuicyjne wyjaśnienie

Więzień A ma tylko 1/3 szans na ułaskawienie. Wiedza, czy zostanie wykonane „B” czy „C”, nie zmienia jego szansy. Po usłyszeniu, że B zostanie stracony, Więzień A uświadamia sobie, że jeśli sam nie otrzyma ułaskawienia, musi to być skierowane tylko do C. Oznacza to, że C ma 2/3 szans na uzyskanie ułaskawienia. Jest to porównywalne z problemem Monty'ego Halla .

Wyliczenie możliwych przypadków

Mogą wystąpić następujące scenariusze:

1. A zostaje ułaskawiony, a naczelnik wymienia B do rozstrzelania: 1/3 × 1/2 = 1/6 przypadków
2. A zostaje ułaskawiony, a naczelnik wskazuje, że C ma zostać stracony: 1/3 × 1/2 = 1/6 przypadków
3. B zostaje ułaskawiony, a naczelnik wskazuje, że C ma zostać stracony: 1/3 przypadków
4. C zostaje ułaskawiony, a naczelnik wskazuje B do rozstrzelania: 1/3 przypadków

Z zastrzeżeniem, że naczelnik wybierze losowo, w 1/3 przypadków, gdy A ma zostać ułaskawiony, istnieje 1/2 szansy, że powie B i 1/2 szansy, że powie C. Oznacza to, że ogólnie w 1/6 przypadków (1/3 [że A jest ułaskawiony] × 1/2 [że naczelnik mówi B]), naczelnik powie B, ponieważ A zostanie ułaskawiony, a 1/6 przypadków (1 /3 [że A jest ułaskawiony] × 1/2 [ten naczelnik mówi C]) powie C, ponieważ A jest ułaskawiony. Daje to w sumie 1/3 przypadków (1/6 + 1/6) ułaskawiania A, co jest dokładne.

Jest teraz jasne, że jeśli naczelnik odpowie B na A (1/2 czasu w przypadku 1 i przypadku 4), wtedy 1/3 czasu C zostanie ułaskawiona, a A nadal będzie stracony (przypadek 4), oraz tylko w 1/6 przypadków A jest ułaskawiony (przypadek 1). Stąd szanse C wynoszą (1/3)/(1/2) = 2/3, a A wynoszą (1/6)/(1/2) = 1/3.

Kluczem do tego problemu jest to, że naczelnik nie może ujawnić nazwiska więźnia, który zostanie ułaskawiony. Jeśli wyeliminujemy ten wymóg, może to zademonstrować pierwotny problem w inny sposób. Jedyną zmianą w tym przykładzie jest to, że więzień A prosi naczelnika o ujawnienie losu jednego z pozostałych więźniów (bez wskazania tego, który zostanie stracony). W tym przypadku naczelnik rzuca monetą i wybiera jeden z B i C, aby ujawnić los. Przypadki są następujące:

1. Ułaskawiony, naczelnik mówi: B stracony (1/6)
2. Ułaskawiony, naczelnik mówi: C stracony (1/6)
3. B ułaskawiony, naczelnik mówi: B ułaskawiony (1/6)
4. B ułaskawiony, naczelnik mówi: C stracony (1/6)
5. C ułaskawiony, naczelnik mówi: B stracony (1/6)
6. C ułaskawiony, naczelnik mówi: C ułaskawiony (1/6)

Każdy scenariusz ma prawdopodobieństwo 1/6. Pierwotny problem Trzech Więźniów można zobaczyć w tym świetle: naczelnik w tym problemie wciąż ma te sześć przypadków, każdy z prawdopodobieństwem wystąpienia 1/6. W takim przypadku naczelnik nie może jednak ujawnić losu ułaskawionego więźnia. Dlatego w 1/6 przypadków występuje przypadek 3, ponieważ powiedzenie B nie jest opcją, naczelnik mówi zamiast tego C (co czyni to tak samo jak w przypadku 4). Podobnie w przypadku 6 naczelnik musi powiedzieć B zamiast C (tak samo jak w przypadku 5). To pozostawia przypadki 4 i 5 z prawdopodobieństwem wystąpienia 1/3 i pozostawia nam takie samo prawdopodobieństwo jak powyżej.

Dlaczego paradoks?

Tendencja ludzi do udzielania odpowiedzi 1/2 nie bierze pod uwagę, że naczelnik mógł rzucić monetą, zanim udzielił odpowiedzi. Naczelnik mógł odpowiedzieć, bo ma zostać zwolniony, i rzucił monetą. Lub ma zostać zwolniony. Ale prawdopodobieństwa tych dwóch wydarzeń nie są równe. ${\ Displaystyle B}$${\ Displaystyle A}$${\displaystyle C}$

Judea Pearl (1988) użył wariantu tego przykładu, aby zademonstrować, że aktualizacje przekonań muszą zależeć nie tylko od zaobserwowanych faktów, ale także od eksperymentu (tj. zapytania), który do tych faktów doprowadził.

Powiązane problemy i aplikacje

• Paradoks chłopca czy dziewczyny
• Zasada ograniczonego wyboru , zastosowanie w brydżu gry karcianej
• Dylemat więźnia , problem teorii gier
• Problem ze Śpiącą Królewną
• Problem z dwiema kopertami

Uwagi

Bibliografia

• Frederick Mosteller : Pięćdziesiąt trudnych problemów dotyczących prawdopodobieństwa . Dover 1987 (przedruk), ISBN  0-486-65355-2 , s. 28-29 ( ograniczona wersja online , s. 28, w Google Books )
• Richard Isaac: Przyjemności prawdopodobieństwa . Springer 1995, ISBN  978-0-387-94415-9 , s. 24-27 ( ograniczona wersja online , s. 24, w Google Books )