Monty-Hall und andere Probleme (Linux-Magazin, September 1999)

Die bekannte Statistikaufgabe, mit der man selbst Kenner der Szene aufs Kreuz legen kann, läßt sich schnell mit einem Perl-Skript simulieren.

Ich erinnere mich noch genau an jenen Abend: Mehrere Stunden vertrat ich die Auffassung, alle am Tisch -- mich ausgenommen -- seien verrückt geworden. Jemand hatte eine von diesen mathematischen Spielereien erzählt und damit hitzige Debatte ausgelöst. Am Morgen danach sah ich endlich ein, daß die anderen Recht hatten.

``Let's make a deal!''

Dabei ist die Aufgabe ganz einfach: In der amerkanischen Spielshow ``Let's make a deal'' mit dem Moderator Monty Hall gibt's ein Auto zu gewinnen, das hinter einer von insgesamt drei verschlossenen Türen der Showbühne steht. Der Kandidat wählt spontan eine der drei Türen aus, diese wird aber noch nicht aufgemacht, denn der Moderator hat eine Überraschung parat: ``Ich zeig' Ihnen mal was'', sagt er und öffnet eine andere Tür -- und dahinter steht kein Preis sondern eine frech blökende Ziege. Im Spiel bleiben also zwei Türen: Die, auf die der Kandidat ursprünglich deutete, und die andere, die auch der Moderator nicht wählte. Hinter einer von beiden muß das Auto stehen, hinter der anderen steht noch eine Ziege. Nun gibt der Moderator dem Kandidaten noch eine Wahlmöglichkeit: ``Möchten Sie wirklich bei der von Ihnen ausgewählten Tür bleiben, oder doch lieber zu der anderen, noch freien Tür wechseln?'' Und die Frage für den Statistiker lautet: Welches Verfahren bringt die höheren Gewinnchancen -- stur bleiben oder wechseln?

Abb.1: Wechseln oder bei der gewählten Tür bleiben?

Die Antwort vorweg: Wer wechselt, gewinnt mit 66%, wer bei der ursprünglich ausgewählten Tür bleibt, mit 33%. Ein Aufschrei geht durchs Publikum. Ersten Linux-Magazin-Lesern fällt das Blatt aus der Hand. ``Quatsch, es macht keinen Unterschied, ob Du wechselst oder nicht, Du gewinnst immer mit 50%!''. Es ist ja auch wirklich verblüffend: Man steht vor zwei Türen und weiß nur, daß hinter einer von beiden das Auto steht, und da soll die Auswahl der einen eine Zwei-Drittel-Gewinnchance bringen?

Wenn der Verstand bei statistischen Problemen stillsteht, hilft oft ein Perlskript weiter, das das Spiel simuliert und Gewinne und Verluste zählt. Listing monty.pl spielt das Monty-Hall-Problem 10.000 mal und kommt zu folgendem Ergebnis:

    Stubborn: Won=33.51% Lost=66.49%
    Switch  : Won=67.23% Lost=32.77%

Der ``sture'' (stubborn) Kandidat, der bei der ursprünglich ausgewählten Tür bleibt, gewinnt also tatsächlich in 33% aller Fälle, während der Türen wechselnde Kandidat mit einer 2/3-Chance das Auto mit nach Hause nimmt.

Simulation vs. Verstand

Das Script monty.pl legt in Zeile 7 die Anzahl der Spieldurchgänge fest, bei 10000 erhält man schon recht brauchbare Ergebnisse, und die Berechnung dauert nur wenige Sekunden.

Die foreach-Schleife ab Zeile 9 führt das Spiel einmal mit und einmal ohne 'Switch' durch, erst kommt der sture Kandidat dran, dann der, der immer wechselt. Die Variable $switch gibt an, um welchen Durchgang es sich handelt. Die foreach-Schleife ab Zeile 10 iteriert über alle Spieldurchgänge.

Die Spiele selber wickelt die Monty-Klasse ab. Sie verfügt außer über einen Konstruktor new, der ein neues Spiel aufstellt und das Auto versteckt, noch über die folgende Methoden:

pick
trifft eine zufällige Auswahl des Kandidaten und öffnet die Tür, die der Moderator vorzeigt

switch
wechselt die Tür des Kandidaten zu der freibleibenden Möglichkeit

call
öffnet die Tür des Kandidaten und sieht nach, ob er gewonnen oder verloren hat und gibt dementsprechend 1 oder 0 zurück.

Die Monty-Klasse ist ab Zeile 23 definiert. Der Konstruktor new ab Zeile 25 legt zunächst eine Referenz auf einen Array mit drei Türen in der Instanzvariablen doors an, ein Wert von 0 gibt an, daß hinter der Tür kein Preis steht, ein 1 steht dafür, daß dort das Auto wartet. new wählt dann mit

    int rand 3;

einen zufälligen Index im Bereich [0,1,2] aus und hängt so das Auto zufällig hinter eine der drei Türen des Arrays.

Die pick-Methode ab Zeile 31 simuliert sowohl den Spieler, der eine Tür auswählt, als auch den Moderator, der anschließend vor der Aufgabe steht, eine der verbliebenen Türen ohne Preis zu öffnen. In der Instanzvariablen picked legt pick den Index einer zufällig ausgewählten Tür fest. Die foreach-Schleife ab Zeile 38 nimmt sich Tür für Tür vor und sucht eine aus, die a) noch nicht vom Kandidaten gewählt und b) nicht den Preis enthält, denn das würde der Moderator auch nicht tun. Der Index dieser Tür wird in der Instanzvariablen opened festgehalten.

Die Methode switch iteriert über alle Türen und sucht die, die weder der Moderator noch der Spieler auswählten und ordnet diese wieder dem Spieler zu, indem sie der Instanzvariablen picked den Türenindex zuweist.

Die call-Methode schließlich, die ab Zeile 58 definiert ist, muß nur den in picked gespeicherten Index hernehmen und den zugehörigen Wert aus dem Türen-Array hervorholen und zurückliefern. Ist dieser 1, stand das Auto hinter der ausgewählten Tür und der Spieler hat gewonnen, ist er 0 , war's diesmal nichts.

Zeile 16 in der Hauptroutine gibt nach vollendetem Spielverlauf Gewinne und Verluste schön formatiert in Prozentzahlen aus, der Hash %outcome enthält die Anzahl der gewonnenen Spiele unter dem Schlüssel 1 und die Anzahl der verlorenen Spiele unter 0 , da Zeile 14 die Werte jeweils fleißig hochgezählt hat.

Noch Zweifler?

Für die letzten verbliebenen Zweifler nun die Lösung der Aufgabe: Der Trick dabei ist, daß man den Fall, letztendlich vor zwei geschloßenen Türen zu stehen, von denen man nichts weiß, nicht von dem Vorgang trennen darf, der zu dieser Situtation führte: Daß nämlich der Moderator mit dem Öffnen der anderen Tür in 2/3 aller Fälle das Geheimnis des Autos indirekt preisgibt.

In 2/3 aller Fälle nämlich wählt der Kandidat ursprünglich eine Tür, hinter der kein Auto steht. Ist dies der Fall, hat der Moderator keine Auswahlmöglichkeit, was das Öffnen seiner Tür betrifft: es steht nur noch eine Tür ohne Preis zur Verfügung, die er öffnen muß, hinter der anderen steht der Preis. Tippt der Kandidat beim ersten Zug also auf eine Tür ohne Preis (was in 2/3 aller Fälle geschieht), führt das Wechseln der Türen automatisch zum Auto.

Noch'n Problem

Im Magazin der Freitagsausgabe der Süddeutschen (kaufe ich immer, obwohl's in San Francisco $4.50 kostet) stand neulich noch ein weiteres Problem mitsamt Lösung -- und fast wäre ich wieder darauf hereingefallen. Die Aufgabe geht so: Gegeben ist ein Zylinder, in dem drei Karten liegen: Die erste ist vorne und hinten schwarz, die zweite vorne und hinten rot, und die dritte auf der einen Seite schwarz und auf der anderen rot. Eine Karte wird gezogen. Man sieht die Vorderseite, und die ist rot. Wie hoch ist die Wahrscheinlichkeit daß auch die Rückseite der gezogenen Karte rot ist? 50% hätte ich vermutet, da es entweder die rot-rote oder die rot-schwarze Karte sein könnte -- aber weit gefehlt.

Listing cards.pl simuliert das Spiel und zeigt, daß tatsächlich in 66% aller Fälle auch die Rückseite der Karte rot ist:

    Red: 6655 Black: 3229

Zeile 8 legt den Array @CARDS an, der die Spielkarten enthält, die wiederum als Unterarrays der Kartenseiten repräsentiert sind: ``r'' steht für red, ``b'' für black. Zeile 11 wählt eine zufällige Karte, Zeile 12 eine Kartenseite. Da nur rote Kartenseiten interessieren, verwirft Zeile 13 den Test, falls eine schwarze Seite auftaucht. Der Unter-Array führt unter dem Index 0 die Vorderseite der Karte und unter 1 die Rückseite -- der Index der entgegengesetzte Seite läßt sich also leicht durch $side ? 0 : 1 bestimmen, falls $side auf 0 oder 1 gesetzt ist. Der Hash %flipcolor zählt, wie oft die Kehrseite rot oder schwarz war, indem es die Einträge unter den Schlüsseln r bzw. b hochzählt, Zeile 17 gibt das Ergebnis aus.

Warum ist das Ergebnis nicht 50%? Wie auch im Monty-Hall-Rätsel spielt der Vorgang, der zum Entscheidungspunkt führte, eine wesentliche Rolle: Die rote Seite der schwarz/roten Karte wird einfach nur halb so oft gezogen wie die rote Karte ...

Und wer's immer noch nicht glaubt -- im Biergarten lassen sich derlei Probleme herrlich ausdiskutieren! Oans - zwoa - gsuffa!

Referenzen

[1]
Beschreibung des Monty-Hall-Problems und Simulation: http://mgw.dinet.de/physik/Quiz/Ziegenproblem/Ziegen.html

Listing monty.pl

    01 #!/usr/bin/perl -w
    02 ##################################################
    03 # Monty-Hall simulation
    04 # mschilli@perlmeister.com 1999
    05 ##################################################
    06 
    07 my $NOF_GAMES = 10000;
    08 
    09 foreach $switch (0..1) {
    10     for (1..$NOF_GAMES) {
    11         my $monty = Monty->new();
    12         $monty->pick();
    13         $monty->switch() if $switch;
    14         $outcome{$monty->call()}++;
    15     }
    16     printf "%-8s: Won=%4.2f%% Lost=%4.2f%%\n", 
    17            $switch ? "Switch" : "Stubborn",
    18            $outcome{1}*100/$NOF_GAMES,
    19            $outcome{0}*100/$NOF_GAMES;
    20     %outcome = ();
    21 }
    22 
    23 package Monty;
    24 
    25 sub new {
    26     my $self = { doors => [qw(0 0 0)] };
    27     $self->{doors}->[int rand 3] = 1;
    28     bless $self, shift;
    29 }
    30 
    31 sub pick {
    32     my $self = shift;
    33 
    34     # Player's pick
    35     $self->{picked} = int rand 3;
    36 
    37     # Monty's pick
    38     foreach $door (0..2) {
    39         if($door != $self->{picked} &&
    40            !$self->{doors}->[$door]) { 
    41             $self->{opened} = $door;
    42             last;
    43         }
    44     }
    45 }
    46 
    47 sub switch {
    48     my $self = shift;
    49     foreach $door (0..2) {
    50         if($door != $self->{picked} && 
    51            $door != $self->{opened}) {
    52             $self->{picked} = $door;
    53             last;
    54         }
    55     }
    56 }
    57     
    58 sub call {
    59     my $self = shift;
    60     return($self->{doors}->[$self->{picked}]);
    61 }

Listing cards.pl

    01 #!/usr/bin/perl -w
    02 ##################################################
    03 # Cards simulation
    04 # mschilli@perlmeister.com 1999
    05 ##################################################
    06 
    07 my $NOF_GAMES = 20000;
    08 my @CARDS = ([qw(r r)], [qw(b b)], [qw(r b)]);
    09 
    10 foreach (1..$NOF_GAMES) {
    11     my $card = $CARDS[rand @CARDS];
    12     my $side = int rand @$card;
    13     next if $card->[$side] ne "r";
    14     $flipcolor{$card->[$side ? 0 : 1]}++;
    15 }
    16 
    17 print "Red: $flipcolor{r} Black: $flipcolor{b}\n";

Michael Schilli

arbeitet als Software-Engineer bei Yahoo! in Sunnyvale, Kalifornien. Er hat "Goto Perl 5" (deutsch) und "Perl Power" (englisch) für Addison-Wesley geschrieben und ist unter mschilli@perlmeister.com zu erreichen. Seine Homepage: http://perlmeister.com.