Zwei-Zettel-Spiel

aus Wikipedia, der freien Enzyklopädie

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 Erfolgswahrscheinlichkeit auf einen Wert größer als 50 Prozent steigern lässt. Ohne weitere Nebenbedingungen geht die Abweichung, bei guter Auswahl der beiden Zahlen, jedoch gegen null und ist in der Praxis bedeutungslos.

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)

Wähle einen Schätzwert für die erwarteten Zahlen. Ist die bekannte Zahl größer als dieser, akzeptiere sie. Wähle andernfalls die unbekannte Zahl.

Analyse

Es ergeben sich drei Fälle:

  1. Ist der Schätzwert kleiner als beide Zahlen, wird stets die bekannte Zahl gewählt. Die Erfolgswahrscheinlichkeit beträgt somit 50 Prozent und entspricht zufälligem Raten.
  2. Ist der Schätzwert größer als beide Zahlen, wird stets die unbekannte Zahl gewählt. Die Erfolgswahrscheinlichkeit beträgt weiterhin 50 Prozent.
  3. Liegt der Schätzwert zwischen den beiden Zahlen, führt die obige Lösungsstrategie deterministisch zur Wahl der größeren Zahl. Die Erfolgswahrscheinlichkeit steigt auf 100 Prozent.

Sei P(T) die Wahrscheinlichkeit einen „Treffer“ zu landen, also einen Schätzwert zwischen den Werten beider Zettel zu wählen, so berechnet sich die Erfolgswahrscheinlichkeit P(E) zu:

Unabhängig von der Wahl des Schätzwertes beträgt die Erfolgswahrscheinlichkeit mindestens 50 Prozent. Die Strategie schneidet also in keinem Fall schlechter ab als zufälliges Raten. Ist die Trefferwahrscheinlichkeit echt größer null, ist auch die Erfolgswahrscheinlichkeit echt größer 50 Prozent. Weniger offensichtlich ist, dass dies bei geeigneter Wahl des Schätzwertes immer gegeben ist.

Wahl des Schätzwertes

Eine Trefferwahrscheinlichkeit echt größer null kann selbst dann gewährleistet werden, wenn nichts über die Verteilung der Zahlen auf den Zetteln bekannt ist. Der Schätzwert darf dazu nicht vom Spieler festgelegt werden; er wird stattdessen in einem Zufallsexperiment aus einer geeigneten Wahrscheinlichkeitsverteilung gezogen. Dazu eignen sich alle Verteilungen, deren Wahrscheinlichkeitsdichte auf dem gesamten Bereich der reellen Zahlen nicht verschwindet, etwa die Normalverteilung.

Beschränken sich die Zettel auf einen dem Spieler bekannten Wertebereich, genügt eine Wahrscheinlichkeitsverteilung, deren Dichte in diesem Bereich nicht verschwindet. In der Praxis ist das häufig der Fall. So ist beim eingangs erwähnten Hausverkauf eine Abschätzung des Marktpreises nach oben und unten zuverlässig möglich.

Ist dem Spieler die Wahrscheinlichkeitsverteilung der Zahlen auf den Zetteln exakt bekannt, so kann er einen festen Schätzwert bestimmen, der die Trefferwahrscheinlichkeit maximiert.

Annahmen und Einschränkungen

Welcher der beiden Zettel zuerst aufgedeckt wird, muss zufällig, gleich wahrscheinlich und unabhängig von der Wahl des Schätzwertes entschieden werden. Andernfalls ist die Annahme verletzt, stets die (un-)bekannte Zahl zu wählen entspreche einer Zufallswahl.

Die Zahlen auf beiden Zetteln müssen voneinander verschieden sein. Eine größere Zahl existiert sonst nicht und kann auch nicht gewählt werden. Die Erfolgswahrscheinlichkeit ist dann grundsätzlich gleich null und lässt sich durch die beschriebene Lösungsstrategie auch nicht verbessern. In der Praxis ist diese Einschränkung irrelevant, da bei gleichen Alternativen eine beliebige gewählt werden kann.

Implementierung in Python

Die nebenstehende Abbildung zeigt eine beispielhafte Implementierung der Lösungsstrategie in der Programmiersprache Python. Die beiden Zahlen werden als natürliche Zahlen aus dem Zahlenbereich von 0 bis 1000 gewählt und es wird sichergestellt, dass sie voneinander verschieden sind. Der erste Algorithmus implementiert die obige Lösungsstrategie für einen zufällig gewählten Schätzwert aus dem genannten Zahlenbereich, der zweite Algorithmus benutzt eine modifizierte Strategie und wählt den Schätzwert konstant in der Mitte des betrachteten Intervalls. 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 Prozent für den ersten und ca. 75,0 Prozent für den zweiten Algorithmus.

Verwandte Themen

Das Zwei-Zettel-Spiel hat eine gewisse Ähnlichkeit mit dem Umtauschparadoxon. Während aber beim Zwei-Zettel-Spiel die Überraschung darin besteht, dass es eine sinnvolle Tauschstrategie gibt, kommt das Umtauschparadoxon zur paradoxen Lösung, dass man immer tauschen soll. Das Umtauschparadoxon wird gelöst, indem man den Widerspruch in der Schlussfolgerung aufdeckt, und wäre auch gelöst, wenn es egal wäre, welchen Umschlag man nimmt; das Zwei-Zettel-Spiel zeigt darüber hinaus, dass es tatsächlich sinnvolle Tauschstrategien gibt, die sich aber von der Strategie „tausche immer“ unterscheiden.

Andere verwandte Themen, bei denen man aus einer Teilinformation die optimale Entscheidung des Restproblems treffen kann, sind:

Weblinks

Abgerufen von „https://de.wikiup.org/index.php?title=Zwei-Zettel-Spiel&oldid=210281725“