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.
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.
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:
pickswitchcall1 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.
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.
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!
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 }
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 Schilliarbeitet 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. |