Zwei Briefumschläge und ein probabilistisches Wunder

Zur Abwechslung kommt heute einmal wieder etwas Mathematisches. Rom Pinchasi hat bei uns zum Abschied heute eine Vorlesung über mathematische Puzzles gehalten, und ein besonders Schönes und Überraschendes möchte ich hier kurz vorstellen.

Wir sind Teilnehmer in einer Quiz-Show. Der Quiz-Master zeigt zwei verschlossene Briefumschläge, A und B. In beiden steckt jeweils ein Papier mit einer Zahl darauf. Wir wissen, dass die beiden Zahlen verschieden sind, aber darüber hinaus haben haben wir keinerlei weitere Informationen. Nun müssen wir ansagen, in welchem Briefumschlag die größere Zahl steckt. Wenn unsere Ansage richtig war, kommen wir in die nächste Runde des Wettbewerbs, andernfalls scheiden wir aus.

Was ist das Beste, das wir in dieser Situation können?

Die naheliegende Strategie ist, zufällig einen der beiden Briefumschläge auszuwählen. Dann kommen wir mit Wahrscheinlichkeit 1/2 in die nächste Runde.

Gibt es eine bessere Strategie? Die Intuition sagt Nein. Aber können wir das auch beweisen?

Für einen richtigen Beweis muss das Szenario richtig formalisiert werden. Vor allem müssen wir uns überlegen, was eigentlich zu beweisen ist. Es könnte zum Beispiel sein, dass immer der Umschlag A die größere Zahl enthält. Dann gibt es natürlich eine bessere Strategie. Dies wird auch nicht dadurch ausgeschlossen, dass wir nicht wissen, dass der Umschlag A immer die richtige Antwort ist. Aussagen über Wissen sind notorisch schwer handzuhaben.

Die Lösung besteht darin, den Quiz-Master als Gegenspieler zu verstehen. Wir wollen Folgendes beweisen: Der Quiz-Master kann sich so verhalten, dass wir höchstens mit Wahrscheinlichkeit 1/2 in die nächste Runde kommen können, egal welche Strategie wir verwenden. Also: es existiert eine Strategie für den Quiz-Master, so dass für alle möglichen Strategien, die wir verwenden können, gilt: wir kommen höchstens mit Wahrscheinlichkeit 1/2 weiter.

Und das ist ganz einfach. Der Quiz-Master schreibt die beiden Zahlen auf, und wählt dann zufällig aus, welche Zahl er in welchen Umschlag steckt. Das macht er im Geheimen, so dass unsere Ansage, in welchem Briefumschlag die höhere Zahl steckt, stochastisch unabhängig von der zufälligen Wahl des Quiz-Masters ist.

Um unsere Erfolgswahrscheinlichkeit zu analysieren, sollten wir zuerst ein paar Wahrscheinlichkeitsereignisse definieren. Sei QA das Ereignis, dass der Quiz-Master die höhere Zahl in den Umschlag A steckt, und QB das entsprechende Ereignis für den Umschlag B. Sei WA das Ereignis, dass wir ansagen, die höhere Zahl stecke im Umschlag A, und WB entsprechend für Umschlag B. Aus dem Verhalten des Quiz-Master folgt Pr[QA] = Pr[QB] = 1/2. Die Wahrscheinlichkeiten für WA und WB hängen dagegen davon ab, welche Strategie wir verwenden, aber darauf will ich mich in dem Beweis nicht festlegen (siehe oben!).

Die stochastische Unabhängigkeit bedeutet, dass Pr[QA und WA] = Pr[QA] * Pr[WA] gilt, und so weiter. Das kann man im Beweis gewinnbringend verwenden. Was ist denn die Wahrscheinlichkeit, dass wir weiterkommen? Nun, entweder wir sagen Umschlag A an (WA) und das ist tatsächlich richtig (QA) oder wir sagen Umschlag B an (WB) und das ist richtig (QB). Die Wahrscheinlichkeit ist also:

Pr[QA und WA] + Pr[QB und WB] = Pr[QA] * Pr[WA] + Pr[QB] * Pr[WB] = Pr[WA] / 2 + Pr[WB] / 2 = (Pr[WA] + Pr[WB])/2 = 1/2

Mit anderen Worten: wenn der Quiz-Master sich wie beschrieben verhält, dann kommen wir immer mit Wahrscheinlichkeit 1/2 weiter, egal was wir tun! Und das ist der ganze Beweis.


Variationen

Bis jetzt ist nichts Überraschendes passiert. Deswegen wollen wir die Quiz-Show nun ein wenig abändern, und zwar auf zwei leicht verschiedene Weisen:

1. Bevor wir uns festlegen, öffnet der Quiz-Master einen Umschlag seiner Wahl und zeigt uns, welche Zahl darin enthalten ist.


2. Bevor wir uns festlegen, dürfen wir einen Umschlag unserer Wahl öffnen und uns ansehen, welche Zahl darin enthalten ist.

Was ist in diesen beiden Fällen die beste Strategie für uns? Da ich angekündigt habe, dass etwas Überraschendes passiert, ist klar: in mindestens einem der Fälle gibt es eine Strategie, bei der wir in jedem Fall mit einer Wahrscheinlichkeit von mehr als 1/2 in die nächste Runde kommen.

Aber wie genau soll das gehen? Ich lasse den geneigten Leser darüber nun selbst ein wenig nachdenken, und werde die Lösung in ein paar Tagen hier aufschreiben.