Problém tří vězňů - Three Prisoners problem - Wikipedia

The Problém tří vězňů objevil se v Martin Gardner „“Matematické hry "sloupec v Scientific American v roce 1959.^[1]^[2] Je to matematicky ekvivalentní s Monty Hall problém s autem a kozou nahrazeno svobodou a popravou.

Problém

Tři vězni, A, B a C, jsou v samostatných celách a jsou odsouzeni k smrti. Guvernér náhodně vybral jednoho z nich, aby byl omilostněn. Dozorce ví, kdo je omilostněn, ale nesmí to říci. Vězeň A prosí dozorce, aby mu oznámil totožnost jednoho ze dvou, kteří budou popraveni. „Pokud má být B prominut, dej mi jméno C. Pokud má být prominut C, dej mi jméno B. A pokud mám být prominut, tajně otoč mincí, abych se rozhodl, zda pojmenuji B nebo C.“

Dozorce říká A, že B má být popraven. Vězeň A je potěšen, protože věří, že jeho pravděpodobnost přežití vzrostla z 1/3 na 1/2, jak je to nyní mezi ním a C. Vězeň A tajně sděluje C zprávu, která zdůvodňuje, že šance A na prominutí je beze změny v 1/3, ale je potěšen, protože jeho vlastní šance vzrostla na 2/3. Který vězeň má pravdu?

Řešení

Odpověď je, že vězeň A nezískal žádné informace o svém osudu, protože už věděl, že mu dozorce dá jméno někoho jiného. Vězeň A před vyslechnutím dozorce odhaduje své šance na odpuštění jako 1/3, stejně jako B i C. Jak dozorce říká, že B bude popraven, je to buď proto, že C bude omilostněn (1/3 šance), nebo A bude omilostněn (1/3 šance) a mince B / C, kterou hodil hlídač, vyšla B (1/2 šance; pro celkovou 1/2 * 1/3 = 1/6 šanci byla B pojmenována, protože A bude omilostněna). Po vyslechnutí, že B bude popraven, je tedy odhad šance, že A bude omilostněn, poloviční oproti C. To znamená, že jeho šance na omilostnění jsou nyní, protože věděl, že B není, opět je 1/3, ale C má 2 / 3 šance na odpuštění

Stůl

Výše uvedené vysvětlení lze shrnout v následující tabulce. Protože dozorce je požádán A, může odpovědět pouze B nebo C, aby byl popraven (nebo „neprominut“).

Je milost	Správce: „ne B“	Správce: „ne C“	Součet
A	1/6	1/6	1/3
B	0	1/3	1/3
C	1/3	0	1/3

Protože dozorce odpověděl, že B nebude prominut, řešení pochází z druhého sloupce „ne B“. Zdá se, že šance na odpuštění A vs. C jsou 1: 2.

Matematická formulace

Volání ${ displaystyle A}$ , ${ displaystyle B}$ a ${ displaystyle C}$ události, které budou odpuštěny příslušnému vězni, a ${ displaystyle b}$ událost, kterou dozorce řekne A, že vězeň B má být popraven, pak pomocí Bayesova věta, zadní pravděpodobnost prominutí A je:

{ displaystyle { begin {zarovnáno} 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}} krát { tfrac {1} {3}}} {{ tfrac {1} {2}} times { tfrac {1} {3}} + 0 times { tfrac {1} {3}} + 1 times { tfrac {1} {3}}} } = { tfrac {1} {3}}. end {zarovnáno}}}

Pravděpodobnost, že bude C omilostněn, je naproti tomu:

{ displaystyle { begin {zarovnáno} 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 {zarovnáno}}}

Rozhodující rozdíl, který činí A a C nerovné, je to ${ displaystyle P (b | A) = { tfrac {1} {2}}}$ ale ${ displaystyle P (b | C) = 1}$ . Pokud bude A prominut, může dozorce říct A, že má být popraveno buď B nebo C, a tedy ${ displaystyle P (b | A) = { tfrac {1} {2}}}$ ; vzhledem k tomu, že pokud bude C prominut, může dozorce říci pouze A, že B je popraven, takže ${ displaystyle P (b | C) = 1}$ .

Intuitivní vysvětlení

Vězeň A má pouze 1/3 šanci na odpuštění. Vědět, zda bude provedeno „B“ nebo „C“, nezmění jeho šanci. Poté, co vězeň A uslyší, že B bude popraven, si uvědomí, že pokud nedostane milost sám, musí jít pouze do C. To znamená, že C má 2/3 šanci získat milost. To je srovnatelné s Monty Hall problém.

Výčet možných případů

Mohou nastat následující scénáře:

A je omilostněn a dozorce uvádí, že B má být popraven: 1/3 × 1/2 = 1/6 případů
A je omilostněn a dozorce uvádí, že C má být popraven: 1/3 × 1/2 = 1/6 případů
B je omilostněn a dozorce uvádí, že C má být popraven: 1/3 případů
C je omilostněn a dozorce uvádí, že B má být popraven: 1/3 případů

S podmínkou, že si dozorce vybere náhodně, v 1/3 času, kdy má být prominut A, existuje 1/2 šance, že řekne B a 1/2 šance, že řekne C. To znamená, že celkově 1/6 času (1/3 [že A je odpuštěno] × 1/2 [že dozorce říká B]), správce řekne B, protože A bude odpuštěno, a 1/6 času (1 / 3 [že A je omilostněn] × 1/2 [že dozorce říká C]) řekne C, protože A je omilostněn. To sčítá celkem 1/3 času (1/6 + 1/6) A, který je prominut, což je přesné.

Nyní je jasné, že pokud dozorce odpoví B na A (1/2 času případu 1 a případu 4), pak je 1/3 času C omilostněn a A bude popraven (případ 4), a pouze 1/6 času A je omilostněna (případ 1). Proto šance C jsou (1/3) / (1/2) = 2/3 a A jsou (1/6) / (1/2) = 1/3.

Klíčem k tomuto problému je strážce nesmí odhalit jméno vězně, který vůle být omilostněn Pokud tento požadavek odstraníme, může to původní problém demonstrovat jiným způsobem. Jedinou změnou v tomto příkladu je, že o to vězeň A požádá dozorce odhalit osud jednoho z ostatních vězňů (neurčeno jednoho, který bude popraven). V tomto případě hází strážce mincí a vybere jednu z B a C, aby odhalil osud. Případy jsou následující:

Prominutý dozorce říká: B popraven (1/6)
Prominutý dozorce říká: C popraven (1/6)
B prominut, dozorce říká: B prominut (1/6)
Prominut B, dozorce říká: C popraven (1/6)
Prominuto C, dozorce říká: B popraven (1/6)
Prominutý C, dozorce říká: Prominutý C (1/6)

Každý scénář má pravděpodobnost 1/6. Původní problém se třemi vězni lze vidět v tomto světle: Strážce v tomto problému má stále těchto šest případů, každý s pravděpodobností 1/6 výskytu. V tom případě však dozorce nesmí odhalit osud omilostněného vězně. Proto v 1/6 času, kdy nastane případ 3, protože řeč B není volbou, dozorce místo toho řekne C (což je stejné jako v případě 4). Podobně v případě 6 musí dozorce namísto C říci B (stejné jako v případě 5). To ponechává případy 4 a 5 s 1/3 pravděpodobností výskytu a ponechává nás se stejnou pravděpodobností jako výše.

Proč paradox?

Tendence lidí poskytovat odpověď 1/2 zanedbává zohlednění toho, že dozorce možná hodil minci, než odpověděl. Dozorce možná odpověděl ${ displaystyle B}$ protože ${ displaystyle A}$ má být propuštěn a hodil minci. Nebo, ${ displaystyle C}$ má být propuštěn. Pravděpodobnosti těchto dvou událostí však nejsou stejné.

Judea Pearl (1988) k prokázání toho použili variantu tohoto příkladu aktualizace víry musí záviset nejen na pozorovaných skutečnostech, ale také na experimentu (tj. dotazu), který k těmto skutečnostem vedl.^[3]

Související problémy a aplikace

Chlapec nebo dívka paradox
Zásada omezeného výběru, aplikace v karetní hře most
Vězňovo dilema, a herní teorie problém
Problém Šípkové Růženky
Problém se dvěma obálkami

Poznámky

^ Gardner, Martin (říjen 1959). "Matematické hry: Problémy týkající se otázek pravděpodobnosti a dvojznačnosti". Scientific American. 201 (4): 174–182. doi:10.1038 / scientificamerican1059-174.
^ Gardner, Martin (1959). „Matematické hry: Jak tři moderní matematici vyvrátili slavnou domněnku Leonharda Eulera“. Scientific American. 201 (5): 188. doi:10.1038 / scientificamerican1159-181.
^ Pearl, J. (1988). Pravděpodobnostní uvažování v inteligentních systémech: sítě pravděpodobného závěru (První vydání). San Mateo, Kalifornie: Morgan Kaufmann.

Reference

Frederick Mosteller: Padesát náročných problémů v pravděpodobnosti. Dover 1987 (dotisk), ISBN 0-486-65355-2, str. 28-29 (omezená online verze, str. 28, v Knihy Google )
Richard Isaac: Potěšení z pravděpodobnosti. Springer 1995, ISBN 978-0-387-94415-9, str. 24-27 (omezená online verze, str. 24, v Knihy Google )

[1] Gardner, Martin (říjen 1959). "Matematické hry: Problémy týkající se otázek pravděpodobnosti a dvojznačnosti". Scientific American. 201 (4): 174–182. doi:10.1038 / scientificamerican1059-174.

[Gardner1959b-2] Gardner, Martin (1959). „Matematické hry: Jak tři moderní matematici vyvrátili slavnou domněnku Leonharda Eulera“. Scientific American. 201 (5): 188. doi:10.1038 / scientificamerican1159-181.

[3] Pearl, J. (1988). Pravděpodobnostní uvažování v inteligentních systémech: sítě pravděpodobného závěru (První vydání). San Mateo, Kalifornie: Morgan Kaufmann.

[1]

[2]

[3]