Gefangenenparadoxon

Das Gefangenenparadoxon, im Englischen auch als Three Prisoners Problem bezeichnet, erschien 1959 in Martin Gardners Kolumne Mathematical Games im Scientific American und ist ein Paradoxon über bedingte Wahrscheinlichkeiten und den Satz von Bayes. Es ist nicht zu verwechseln mit dem Gefangenendilemma der Spieltheorie.

Formulierung des Problems

Drei zum Tode verurteilte Gefangene – Anton, Bernd und Clemens – befinden sich in Einzelzellen, als der Gouverneur entscheidet, einen von ihnen zu begnadigen. Er schreibt ihre Namen auf drei Papierzettel, schüttelt die Zettel in einem Hut durcheinander, zieht einen heraus und teilt den Namen des Glücklichen dem Gefängniswärter telefonisch mit, diesen darum bittend, diese Information noch mehrere Tage geheim zu halten. Gerüchte davon erreichen Anton. Als der Wärter seine morgendliche Runde macht, versucht Anton ihn zu überreden, ihm mitzuteilen, wer begnadigt wird. Der Wärter weigert sich.

„Dann nenne mir“, sagt Anton, „den Namen eines der anderen, der hingerichtet wird. Wenn Bernd begnadigt wird, nenne mir Clemens; falls Clemens begnadigt wird, nenne mir Bernd. Wenn ich begnadigt werde, dann wirf eine Münze, um zwischen Bernds und Clemens’ Nennung zu entscheiden.“

„Aber wenn du siehst, wie ich eine Münze werfe“, erwidert der Wärter, „wirst du wissen, dass du der Begnadigte bist. Und wenn du siehst, dass ich keine Münze werfe, dann weißt du, dass der Nichtgenannte begnadigt wird.“

„Dann teile es mir nicht jetzt“, sagt Anton, „sondern morgen mit.“

Der Wärter, der wenig über Wahrscheinlichkeitstheorie weiß, denkt in der Nacht darüber nach und entscheidet, der von Anton vorgeschlagenen Prozedur zu folgen, in der Annahme, er würde ihm keine Hilfe zur Abschätzung seiner Überlebenschancen geben, wenn Anton nicht wisse, ob er die Münze geworfen habe. Am nächsten Morgen teilt er Anton mit, dass Bernd hingerichtet wird.

Nachdem der Wärter verschwunden ist, lächelt Anton über dessen Dummheit: Entweder Clemens wird begnadigt oder er selbst, sodass seine Überlebenschance von ¹⁄₃ auf ¹⁄₂ gestiegen sei.

Der Wärter weiß nicht, dass Anton mit Clemens, der in der Nachbarzelle sitzt, kommunizieren kann, indem er Klopfzeichen über eine Wasserleitung gibt. Er teilt ihm alles haargenau mit, was er mit dem Wärter besprochen hat. Clemens ist gleichermaßen erfreut über die Neuigkeiten, weil er aus den gleichen Gründen wie Anton daraus schließt, dass seine Überlebenschancen ebenfalls auf ¹⁄₂ gestiegen sei.

Schätzen die beiden Gefangenen ihre Chancen korrekt ein? Falls nicht, wie sollte jeder seine Chancen, begnadigt zu werden, berechnen?

Die Lösung

Zu Anfang werden die in der Problemformulierung genannten Informationen in einen mathematischen Formalismus übersetzt. Dabei ist im Allgemeinen streng zu unterscheiden zwischen der Ebene der im Text handelnden Personen (z. B. Anton) und der Ebene des Lesers (Metaebene). Das den verschiedenen Ebenen zugängliche Vorwissen kann nämlich durchaus unterschiedlich sein.

Zunächst setzt man ${\mathcal {X}}=\{A,B,C\}$ nach den Anfangsbuchstaben der Akteure, und hierauf die Zufallsvariable $L$, die den Losentscheid darstellt und auf ${\mathcal {X}}$ abbildet. Weil der Name zufällig ausgewählt wurde, kann man ansetzen:

$P(L=A)=P(L=B)=P(L=C)={\frac {1}{3}}$

Das heißt, $L$ ist gleichverteilt.

Weiterhin sei $G$ eine Zufallsvariable, die angibt, wen der Wärter nennt. Man könnte für die bedingten Wahrscheinlichkeiten der Nennungen des Wärters (fälschlicherweise) folgern:

$P(G=B|L=A)=P(G=C|L=A)={\frac {1}{2}}$

$P(G=B|L=B)=0$

$P(G=B|L=C)=1$

Der Wärter wird Bernd oder Clemens mit gleicher Wahrscheinlichkeit nennen, sollte der Losentscheid auf Anton gefallen sein. Er wird nicht Bernd nennen, wenn Bernd ausgelost wurde, und er wird sicher Bernd nennen, sollte Clemens ausgelost worden sein. Die A-posteriori-Überlebenswahrscheinlichkeit für Anton ist dann nach dem Satz von Bayes:

$P(L=A|G=B)=$

$={P(L=A)P(G=B|L=A) \over P(L=A)P(G=B|L=A)+P(L=B)P(G=B|L=B)+P(L=C)P(G=B|L=C)}=$

$={\frac {{\frac {1}{3}}\cdot {\frac {1}{2}}}{{\frac {1}{3}}\cdot {\frac {1}{2}}+{\frac {1}{3}}\cdot 0+{\frac {1}{3}}\cdot 1}}={\frac {1}{3}}$

Die Gefangenen schätzen ihre Überlebenschancen falsch ein. Die Wahrscheinlichkeit dafür, dass Anton überlebt, bleibt ¹⁄₃. Die Wahrscheinlichkeit, dass Clemens überlebt, ist auf ²⁄₃ gestiegen.

Das Paradoxon

Das Paradoxe an dem Ergebnis ist, dass Antons Überlebenschance in der neuen Situation, also seine bedingte Überlebenschance $P(L=A|G=B)$, immer noch ¹⁄₃ ist, während Clemens’ Überlebenswahrscheinlichkeit sich von ¹⁄₃ auf ²⁄₃ verdoppelt. Obwohl jetzt nur noch er oder Clemens begnadigt werden können, ist sie also genauso groß wie seine Überlebenschance $P(L=A)$ am Anfang.

Das Paradoxon lässt sich auflösen, indem man sich klarmacht, dass die Aussage des Wärters keine Auswirkung auf die Wahrscheinlichkeit von Antons Schicksal hat. Da Anton auf keinen Fall genannt werden würde, ergibt sich aus seiner Nichtnennung keine zusätzliche Information. Da andererseits Bernd oder Clemens genannt werden können, verteilt sich der gesamte Informationsgewinn aus der Nennung oder Nichtnennung eines der beiden Namen antisymmetrisch auf genau diese beiden Personen. Sobald bekannt ist, dass Bernd sterben wird, sinkt Bernds Überlebenswahrscheinlichkeit von ¹⁄₃ auf 0, und Clemens’ Überlebenswahrscheinlichkeit steigt von ¹⁄₃ auf ²⁄₃. Die Gesamtwahrscheinlichkeit, dass Bernd oder Clemens überleben wird, bleibt unverändert bei ²⁄₃.

Äquivalenz mit dem Ziegenproblem

Es liegt dem Gefangenenparadoxon derselbe Sachverhalt zugrunde wie bei der Standardvariante des Ziegenproblems. Dabei ist das Ereignis der Begnadigung mit dem der Existenz des Gewinns hinter einem Tor zu identifizieren, weiter das Öffnen eines Tors mit der Nennung eines Opfers und der Wärter mit dem Moderator. Wissen und Verhalten des Wärters ist, zusammen mit dem Münzwurf, mit dem des Moderators äquivalent. Im Moderator oder Wärter wird bloß das Verhalten der Wahrscheinlichkeiten subsumiert.

Lösung mit größerer Grundmenge

Bei der Betrachtung von 100 Gefangenen, von denen einer begnadigt werden soll, verhalten sich die Wahrscheinlichkeiten entsprechend zu denen bei drei Personen. Antons Überlebenschancen als einer der hundert liegen bei 1 %, und die Wahrscheinlichkeit, dass jemand anderes überlebt, beträgt 99 %. Anton bittet den Wärter, ihm 98 seiner Mitgefangenen zu nennen, die sterben müssen. Nach Abschluss der Aufzählung bleiben Clemens und Anton selbst übrig. Da Anton von vornherein bei der Aufzählung ausgeschlossen war, ist Antons Überlebenschance in der neuen Situation, also seine bedingte Überlebenschance, nach wie vor 1 %. Und weil Clemens als einziger nicht genannt wurde, ist es sehr wahrscheinlich, und zwar 99 %, dass er begnadigt wurde.

Durch die Nennung eines Opfers gewährt der Wärter dem Fragenden neue Informationen. Jedoch betrifft diese Information nicht die Überlebenswahrscheinlichkeit des Fragenden. Der Wärter nennt einen vom Fragenden und vom Begnadigten verschiedenen Gefangenen. Damit sind die Gefangenen in zwei Gruppen zu unterteilen, in die Gruppe des Fragenden und in eine Restgruppe. Die Informationsgebung des Wärters betrifft nur die Restmenge. Mit jedem genannten Namen fällt dessen Überlebenswahrscheinlichkeit auf null und die Überlebenswahrscheinlichkeit der Übrigen steigt entsprechend an, während die des Fragenden gleich bleibt.

Man nimmt an, dass die Auswahlwahrscheinlichkeit eines jeden Gefangenen zunächst gleich sei. Die Wahrscheinlichkeit, dass der Begnadigte Element der Fragenden oder der Restmenge ist, steht durch die Verteilung der Zufallsvariablen fest.

Zusatz zu den obigen Überlegungen

„Nachdem also Anton die Antwort des Wärters bekommen hat, besucht der Wärter Clemens. Clemens fragt den Wärter, was dieser bei Anton gemacht habe. Der Wärter erzählt ihm die Geschichte, worauf nun Clemens antwortet: ‚Gott sei Dank habe ich nicht zuerst gefragt!‘“

Tatsächlich wäre bei der gleichen Antwort „Bernd“ die Gewinnchancen von Anton auf ²⁄₃ gestiegen, während sie beim fragenden Clemens bei ¹⁄₃ geblieben wäre.

Das Paradoxon liegt darin, dass scheinbar die Überlebenschancen desjenigen steigen, der nicht gefragt hat. Jedoch bleiben die Überlebenschancen unabhängig von der Frage gleich, nämlich bei ¹⁄₃ (die Antwort auf die Frage erhöht nur die Information zu den Überlebenschancen der Gefangenen in der Restmenge).

Betrachtet man noch die Frage: „Wie hoch ist die Wahrscheinlichkeit dafür, dass Anton begnadigt wurde, unter der Bedingung, dass Bernd nicht begnadigt wurde?“

Zunächst gelten die folgenden Wahrscheinlichkeiten:

$P\left({\overline {B}}\mid A\right)=P\left({\text{Bernd nicht begnadigt}}\mid {\text{Anton begnadigt}}\right)=1$ (Wenn Anton begnadigt ist, kann Bernd nicht begnadigt sein)

$P(A)=P({\text{Anton begnadigt}})={\frac {1}{3}}$

$P\left({\overline {B}}\right)=P({\text{Bernd nicht begnadigt}})={\frac {2}{3}}$

Das Ergebnis folgt dann unmittelbar aus der Definition der bedingten Wahrscheinlichkeit:

$P(A|{\overline {B}})={\frac {P(A\cap {\overline {B}})}{P({\overline {B}})}}={\frac {P({\overline {B}}|A)\cdot P(A)}{P({\overline {B}})}}={\frac {1\cdot {\frac {1}{3}}}{\frac {2}{3}}}={\frac {1}{2}}$

Nun hat man zwei Lösungen, die einander anscheinend widersprechen.

Der Grund ist, dass die Antworten unter unterschiedlichen Bedingungen gegeben werden. In der Fragestellung wird die Antwort des Wärters von der vorher vorgenommenen Auswahl (oben in der Trennung in Fragenden und Restmenge) beeinflusst. Wird dieser Einfluss nicht mitberücksichtigt, gehen Informationen verloren, und das spiegelt sich in der Verschiebung der Wahrscheinlichkeit wider (in der letzten Frage wird keine Trennung der Gruppen vorgenommen, so kommt der Verlust der Überlebenschance von Bernd den Überlebenschancen von Anton und Clemens gleichermaßen zugute).

Siehe auch

• Gefangenenparadoxon - Artikel in der deutschen Wikipedia

Verwandte Themen, bei denen man aus Teilinformation die optimale Entscheidung des Restproblems treffen kann:

• Odds-Strategie - Artikel in der deutschen Wikipedia
• Sekretärinnenproblem - Artikel in der deutschen Wikipedia
• Umtauschparadoxon - Artikel in der deutschen Wikipedia
• Ziegenproblem - Artikel in der deutschen Wikipedia
• Zwei-Zettel-Spiel - Artikel in der deutschen Wikipedia

Literatur

• Frederick Mosteller: Fifty Challenging Problems in Probability. Dover 1987 (Nachdruck), ISBN 0-486-65355-2, S. 28–29 (Auszug (Google)).
• Richard Isaac: Pleasures of Probability. Springer 1995, ISBN 9780387944159, S. 24–27 (Auszug (Google)).
• Jason Rosenhouse: The Monty Hall Problem. Oxford University Press 2009, ISBN 978-0-19-536789-8, S. 16–19 (Online-Kopie des 1. Kapitels. (Memento vom 30. April 2011 im Internet Archive). (PDF; 275 kB), Preprint, dort S. 27–32).

Weblinks

• The Three Prisoners Problem Revisited: issues in the use of Bayesian networks for security applications. (PDF; 184 kB).