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 das Bayestheorem. 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 ihn Anton 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 Ü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 Ω = {A,B,C} nach den Anfangsbuchstaben der Akteure, und hierauf die Zufallsvariable L, die den Losentscheid darstellt und auf Ω 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 ex post-Überlebenswahrscheinlichkeit für Anton ist dann nach dem Bayestheorem:

$\!\,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 noch immer 1/3 ist, obwohl jetzt nur noch er und Clemens begnadigt werden können. Die Überlebenswahrscheinlichkeit von Clemens ist jedoch auf 2/3 gestiegen.

Ä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.

Anschauliche Lösung

Etwas verständlicher wird dies, wenn man 100 Gefangene betrachtet, von denen einer begnadigt werden soll. 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, hat sich an seiner Überlebenschance nichts geändert. Und weil Clemens als einziger nicht genannt wurde, ist es sehr wahrscheinlich, dass er begnadigt wurde. Die Überlebenswahrscheinlichkeit von Anton beträgt weiterhin 1%, die von Clemens erhöht sich auf 99%.

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 dessen steigen, der nicht gefragt hat. Natürlich bleiben die Überlebenschancen unabhängig der Fragerei gleich, nämlich bei 1/3. (Die Antwort auf die Frage erhöht nur die Information zu den Überlebenschancen der Gefangenen in der Restmenge.)

Betrachten wir 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 haben wir zwei Lösungen, die sich scheinbar widersprechen. Was ist der Grund dafür?

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

Literatur

• Frederick Mosteller: Fifty Challenging Problems in Probability. Dover 1987 (Nachdruck), ISBN 0-486-65355-2, S. 28-29 (eingeschränkte Online-Version in der Google Buchsuche-USA)
• Richard Isaac: Pleasures of Probability. Springer 1995, ISBN 9780387944159, S. 24-27 (eingeschränkte Online-Version in der Google Buchsuche-USA)
• Jason Rosenhouse: The Monty Hall Problem. Oxford University Press 2009, ISBN 978-0-19-536789-8, S. 16-19 (Online-Kopie des 1. Kapitels, Preprint, dort S. 27-32)

Einzelnachweise

1. ↑ Gardner, Martin (1959a). "Mathematical Games" column, Scientific American, October 1959, pp. 180–182.
2. ↑ Gardner, Martin (1959b). "Mathematical Games" column, Scientific American, November 1959, p. 188.

Weblinks

• The Three Prisoners Problem Revisited: issues in the use of Bayesian networks for security applications (pdf)