Zwei-Zettel-Spiel

Eine gesichtete Version dieser Seite, die am 21. Dezember 2015 freigegeben wurde, basiert auf dieser Version.

Das Zwei-Zettel-Spiel oder auch Zwei-Umschläge-Problem untersucht die Frage, mit welcher Strategie man die größere von zwei Zahlen finden kann, wenn von diesen beiden Zahlen eine Zahl unbekannt ist und man zudem nur weiß, dass beide Zahlen voneinander verschieden sind.

Intuitiv würde man vermuten, dass die Wahrscheinlichkeit, unter diesen Voraussetzungen die größere Zahl korrekt zu bestimmen, bei 50 Prozent liegt. Tatsächlich zeigt sich aber, dass sich mit einer geeigneten Strategie die Wahrscheinlichkeit auf einen Wert echt größer als 50 Prozent steigern lässt.

Problemstellung

Die Problemstellung wurde 1987 von Thomas M. Cover folgendermaßen beschrieben:

„Spieler 1 schreibt zwei beliebige, verschiedene Zahlen auf Zettel. Spieler 2 wählt zufällig einen davon aus, wobei beide Zettel gleich wahrscheinlich sind, und sieht sich die Zahl an. Spieler 2 muss nun entscheiden, ob die gewählte Zahl die größere ist. Besser als mit der Wahrscheinlichkeit 1/2 zu raten, scheint nicht möglich zu sein.“

Eine allgemeinere Formulierung von Franz Thomas Bruss aus dem Jahr 1998 lautet:

„Man muss sich zwischen zwei Alternativen entscheiden und weiß fast nichts darüber, welche günstiger sein könnte. Dann kann man auch gleich eine Münze werfen, oder? Nein: Es geht besser.“

Im täglichen Leben treten solche Situationen immer dann auf, wenn man sich für oder gegen eine Alternative entscheiden muss, ohne zu wissen, ob nicht noch eine bessere Gelegenheit kommt. Beispiele dafür sind etwa ein Sonderangebot im Supermarkt, die Suche nach einer neuen Wohnung oder Arbeitsstelle, der Partner fürs Leben etc. Ein weiteres praktisches Beispiel ist der Hausverkauf mit zwei Interessenten, wobei man bei Ablehnung des Angebotes nicht mehr auf den Interessenten zurückkommen kann.

Lösungsstrategie

Beispielimplementierung in Python

#!/usr/bin/env python
import random

wiederholungen = 1000000
zahlenbereich = 1000
treffer1 = 0
treffer2 = 0

for i in range(wiederholungen):
  # Zwei zufaellige, aber unter- 
  # schiedliche Zahlen erzeugen
  while True:
    x = random.randrange(zahlenbereich)
    y = random.randrange(zahlenbereich)
    if x != y:
      break

  # Algorithmus 1 
  # (Zufaellige Wahl von z)
  z = random.randrange(zahlenbereich)
  if x <= z and x < y:
    treffer1 = treffer1 + 1
  elif x > z and x > y:
    treffer1 = treffer1 + 1

  # Algorithmus 2 
  # (Feste Wahl von z)
  z = zahlenbereich / 2
  if x <= z and x < y:
    treffer2 = treffer2 + 1
  elif x > z and x > y:
    treffer2 = treffer2 + 1

# Ausgabe
print(treffer1)
print(treffer2)

Wir bezeichnen mit $X$ die zuerst gewählte und damit bekannte Zahl, mit $Y$ hingegen die zweite, unbekannte Zahl. Auf dieser Basis soll nun eine Entscheidung getroffen werden, ob die Zahl $X$ größer ist als die Zahl $Y$ oder ob der umgekehrte Fall gilt. Obwohl über beide Zahlen $X$ und $Y$ keinerlei weitere Informationen vorliegen, existiert eine Lösungsstrategie, die im Mittel bessere Resultate liefert als reines Raten des Ergebnisses.

Dazu wählen wir zunächst mit irgendeiner Wahrscheinlichkeitsverteilung, deren Dichtefunktion auf den reellen Zahlen nirgends verschwindet (etwa einer Normalverteilung), eine zufällige und von den anderen beiden Zahlen unabhängige dritte Zahl $Z$ .

Unsere Lösungsstrategie laute nun folgendermaßen:

Ist die bekannte Zahl $X$ kleiner oder gleich der zufälligen Zahl $Z$ , so gehen wir davon aus, dass die bekannte Zahl $X$ kleiner ist als die unbekannte Zahl $Y$ .
Ist die bekannte Zahl $X$ hingegen größer als die zufällige Zahl $Z$ , so gehen wir davon aus, dass die bekannte Zahl $X$ größer ist als die unbekannte Zahl $Y$ .

Die nebenstehende Abbildung zeigt eine beispielhafte Implementierung dieser Lösungsstrategie und einer davon leicht abweichenden Variante in der Programmiersprache Python. Die beiden Zahlen $X$ und $Y$ werden als natürliche Zahlen aus dem Zahlenbereich von 0 bis 1000 gewählt und es wird sichergestellt, dass beide Zahlen voneinander verschieden sind. Der erste Algorithmus implementiert die obige Lösungsstrategie für ein zufällig gewähltes $Z$ aus dem genannten Zahlenbereich, der zweite Algorithmus benutzt eine modifizierte Strategie und wählt die Zahl $Z$ konstant in der Mitte des betrachteten Zahlenbereiches. Die von den jeweiligen Algorithmen erzielten Treffer werden aufsummiert und am Ende ausgegeben. Für eine hinreichend große Anzahl von Wiederholungen ergeben sich numerische Trefferwahrscheinlichkeiten von ca. 66,7 % für den ersten und ca. 75,0 % für den zweiten Algorithmus.

Wieso die hier vorgestellte Lösungsstrategie zu einem besseren Ergebnis führt als reines Raten, wird im folgenden Abschnitt untersucht.

Mathematische Betrachtung

Die Zahlen auf den Zetteln seien $R$ und $S$ . Die Lösungsstrategie beruht auf den folgenden drei Annahmen:

Einer der beiden Zettel wird ausgewählt, die Zahl darauf wird mit $X$ bezeichnet, die Zahl auf dem anderen Zettel mit $Y$ . Diese Auswahl ist unabhängig von $R$ und $S$ und beide Zettel werden gleich wahrscheinlich gewählt: $P(X=R)=P(X=S)={\tfrac {1}{2}}$ .
Die Zufallsvariable $Z$ muss eine Dichtefunktion besitzen, die auf der gesamten reellen Achse positiv ist.
Die Zufallsvariable $Z$ ist unabhängig von $R$ , $S$ und der Auswahl in Schritt 1.

Bei Durchführung der obigen Lösungsstrategie können folgende drei Fälle eintreten:

Fall A: Sowohl $R$ wie auch $S$ sind kleiner oder gleich $Z$ : Hier fällt die Wahl wegen $X\leq Z$ auf $Y$ .

Fall B: Die Zahl $Z$ liegt zwischen $R$ und $S$ : Für $X=\min(R,S)$ gilt $X\leq Z<Y$ und die Wahl fällt auf $Y=\max(R,S)$ . Für $X=\max(R,S)$ gilt $Y\leq Z<X$ und die Wahl fällt auf $X$ , also wieder auf $\max(R,S)$ .

Fall C: Sowohl $R$ wie auch $S$ sind größer als $Z$ : Hier fällt die Wahl wegen $X>Z$ auf $X$ .

Da immer genau einer der Fälle A, B oder C eintritt, ist $P(A)+P(B)+P(C)=1$ . In den Fällen A und C ist die Wahrscheinlichkeit $P(G)$ , die größere der beiden Zahlen, also $\max(R,S)$ zu wählen, gleich ${\tfrac {1}{2}}$ . Im entscheidenden Fall B wählt man jedoch mit Sicherheit, also mit der Wahrscheinlichkeit 1, $\max(R,S)$ , die größere der beiden Zahlen. Die Wahrscheinlichkeit $P(G)$ , die größere Zahl $\max(R,S)$ zu treffen, ist daher

P(G)={\tfrac {1}{2}}\ P(A)+1\ P(B)+{\tfrac {1}{2}}\ P(C)={\tfrac {1}{2}}\left[P(A)+P(B)+P(C)\right]+{\tfrac {1}{2}}P(B)={\tfrac {1}{2}}+{\tfrac {1}{2}}P(B).

$P(G)$ ist somit größer als ${\tfrac {1}{2}}$ , falls $P(B)$ größer als Null ist. $P(B)$ ist tatsächlich größer als 0, weil $Z$ laut Voraussetzung eine Dichtefunktion besitzt, die auf der gesamten reellen Achse positiv ist. Die oben angeführte Lösungsstrategie ist also besser als reines Raten der Lösung.

Im Spezialfall, dass $R$ und $S$ selbst als unabhängige Realisierungen einer stetigen Zufallsvariable mit identischer Verteilungsfunktion $F$ gegeben sind, lässt sich die Erfolgswahrscheinlichkeit quantifizieren: Wenn $g$ die Dichte von $Z$ bezeichnet, so folgt

P(G)={\tfrac {1}{2}}+\int F(z)(1-F(z))g(z)dz

.

Die Wahl von Z

Es stellt sich die Frage, wie man $Z$ geeignet wählt.

Die Wahrscheinlichkeit $P(G)$ , die größte Zahl zu treffen, ist

P(G)={\tfrac {1}{2}}+{\tfrac {1}{2}}P(B).

Wenn die Dichte von $Z$ überall positiv ist, ist $P(B)>0$ und daher $P(G)>{\tfrac {1}{2}}$ , also die Lösungsstrategie auf alle Fälle besser als ein blindes Raten. Für jede andere Wahl von $Z$ ist aber $P(B)\geq 0$ und daher $P(G)\geq {\tfrac {1}{2}}$ , also die Lösungsstrategie zumindest nicht schlechter als ein blindes Raten. Sind beispielsweise sowohl positive als auch negative Werte für $X$ und $Y$ möglich, so kann auch eine fixe Wahl $Z=0$ sinnvoll sein. Sind für $X$ und $Y$ nur positive Werte möglich, so ist es sinnvoll, dass auch $Z$ nur positiv sein kann. Für die genaue Wahl der Verteilung von $Z$ lassen sich keine allgemeinen Regeln angeben, eine gute Wahl hängt von der konkreten Situation ab.

Beim Eingangsbeispiel des Hauskaufs beispielsweise gibt es eine Spannbreite, innerhalb deren die Zahlen sinnvoll erscheinen, allerdings sind – bei einem normalen Haus – beispielsweise Zahlen von kleiner als 10.000 oder von größer als 10 Millionen äußerst unwahrscheinlich. Sinnvollerweise sollte man den Erwartungswert von $Z$ in der Nähe des Marktwerts des Hauses ansiedeln; die Varianz von $Z$ sollte man umso kleiner wählen, je genauer man den Marktwert abschätzen kann.

Lösungsstrategie bei Vorwissen

Je nach Vorwissen kann eine andere Strategie als die obige zweckmäßiger sein, beispielsweise bei einem Einkauf im Supermarkt: Wenn eine Kundin erkennt, dass ein Produkt zu einem Preis angeboten wird, der nie zuvor unterboten worden ist, wird sie die Wahrscheinlichkeit, dass dieses Produkt in einem anderen Laden günstiger angeboten wird, als sehr gering einschätzen, eine Anwendung der obigen Strategie wäre widersinnig. Ein Kunde hingegen, der dieses Produkt noch nie gekauft hat und der auch sonst keine Vorinformationen hat, kann sehr wohl nach obiger Methode vorgehen.

Literatur

Franz Thomas Bruss: Der Ungewissheit ein Schnippchen schlagen. In: Spektrum der Wissenschaft, 2000, Heft 6, S. 106, ISSN 0170-2971.
Thomas M. Cover: Problem 5.1: Pick the largest number. Ders.: Open Problems in Communication and Computation. Springer Verlag, Berlin 1987, ISBN 3-540-96621-8.