Das 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 und dem Problem der 100 Gefangenen aus der Kombinatorik.

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, die hingerichtet werden. 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. 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, so dass seine Überlebenschance von 1⁄3 auf 1⁄2 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, denkt er doch jetzt im Unterschied zu Anton, dass seine eigene Überlebenschance von 1⁄3 auf 2⁄3 gestiegen sei.

Wer von beiden Gefangenen schätzt seine Chancen korrekt ein?[1][2]
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 (Meta-Ebene). 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 Gouverneur den Namen zufällig aus drei Namenszetteln ausgewählt und Anton gerüchteweise von diesem Verfahren gehört hat, kann dieser ansetzen:

P(L=A) = P(L=B) = P(L=C) = \tfrac13\,,

das heißt: L ist gleichverteilt.

Weiterhin sei G eine Zufallsvariable, die angibt, wen der Wärter nennt. Obwohl Anton, im Unterschied zum Leser, nicht weiß, ob der Wärter sich an die vorgeschlagene Prozedur gehalten hat, vertraut er dem Wärter und folgert dann für die bedingten Wahrscheinlichkeiten der Nennungen des Wärters:

P(G=B|L=A) = P(G=C|L=A) = \tfrac 12
\!\,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} = \tfrac{1}{3}


Die Wahrscheinlichkeit dafür, dass Anton überlebt, bleibt also 1⁄3.
Das Paradoxon

Das Paradoxe an dem Ergebnis ist, dass Antons Überlebenschance in der neuen Situation, also seine bedingte Überlebenschance P(L=A|G=B), ebenfalls 1⁄3 ist. 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 nichts mit Antons Schicksal zu tun hat. Der Wärter wird entweder Bernd oder Clemens nennen. Nachdem bekannt ist, dass Bernd sterben wird, sinkt Bernds Überlebenswahrscheinlichkeit von 1⁄3 auf 0, und Clemens’ Überlebenswahrscheinlichkeit steigt von 1⁄3 auf 2⁄3.
Äquivalenz mit dem Ziegenproblem

Es liegt dem Gefangenenparadoxon derselbe Sachverhalt zugrunde wie dem ausgeglichenen Moderator beim Ziegenproblem. 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 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, ebenfalls 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 Auswahl-Wahrscheinlichkeit 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 2⁄3 gestiegen, während sie beim fragenden Clemens bei 1⁄3 geblieben wäre.

Das Paradoxon liegt darin, dass scheinbar die Überlebenschancen desjenigen steigen, der nicht gefragt hat. Jedoch bleiben die Überlebenschancen unabhängig der Frage gleich, nämlich bei 1⁄3 (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 sich anscheinend widersprechen.

Der Grund ist, dass die Antworten unter unterschiedlichen Bedingungen stattfinden. In der Fragestellung wird die Antwort des Wärters von der vorher stattgefundenen 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 Fragestellung 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

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

Odds-Strategie
Sekretärinnenproblem
Umtauschparadoxon
Ziegenproblem
Zwei-Zettel-Spiel

Quelle - Literatur & einzelnachweise