Seiten

  • Startseite
  • Impressum
  • Inhalt
  • MINT
  • Sprache
  • Soziales
  • Geist
  • Kunst
  • Gemischtes
  • Gedichte

Sonntag, 3. April 2016

Auf Fehlersuche im Heiratsspiel


Deutsch

Viele Stun­den hat mich ein Pro­blem be­schäftigt und damit mei­ne Mühen nicht vergebens ge­wesen sein sol­len, will ich im heutigen Bei­trag davon berich­ten. Es geht um Kar­ten­legen, gutes Mi­schen, Zufalls- und Gleichver­teilun­gen, die Su­che nach der Nadel im Heuhau­fen sowie noch un­gelöste Fra­gen.

Das Spiel

..., von dem die Rede ist, existiert si­cherlich in un­ter­schiedli­chen Versionen und so muss es zuerst einmal erklärt wer­den. Das Un­terhal­tungs­spiel soll dem Spie­ler dabei behilf­lich sein, den späte­ren Ehe­partner zu ermit­teln. Man benötigt ein Romméblatt mit 104 Spielkar­ten. Vier ver­schiede­ne Damen (oder Bu­ben) wer­den nebenein­an­der abgelegt und der Spie­ler ver­bindet sie mit vier Namen von für ihn in Fra­ge kommen­den Ehe­partnern. Im ers­ten Durch­lauf bekommt jede der Damen zehn Kar­ten vom Stapel, dabei sind die Far­ben Herz, Karo, Pik und Kreuz Maße für Liebe, Kinderwunsch, Ge­halt und Treue (ge­nauer: die Kar­ten­anzahl steht jeweils für die Zu­neigung zum Spie­ler auf ei­ner Ska­la von sie mag ihn bis sie liebt ihn bis ins Unendli­che[1], die Anzahl der gewüns­ch­ten Kin­der, das Ge­halt in 1.000 € und die Seiten­sprünge der zuge­ordne­ten Person). Der Spie­ler sucht sich ei­ne Person aus, die ihm am we­nigs­ten zusagt, und der Vor­gang wird mit den ver­bliebe­nen Damen (und neuen Kar­ten) wieder­holt, bis nur noch ei­ne Dame üb­rig ist. Wer mitgezählt hat, weiß, dass jetzt noch 10 Kar­ten üb­rig sind. 9 davon wer­den benutzt, um herauszufin­den, ob es wirk­lich zur Heirat kommen wird. Ne­ben die ver­bliebe­ne Dame wird ein be­liebi­ger Bube gelegt (mög­li­cherweise ist sogar noch ei­ner un­ter den 10 Kar­ten, dann geht es ge­nau auf), der den Spie­ler symbolisiert. Dann wer­den pro Person vier Kar­ten, wel­che jeweils die Mei­nung der Person, ih­rer Fa­milie, ih­rer Freun­de und ih­res Pfar­rers wiederge­ben (Rot bedeu­tet dafür, Schwarz bedeu­tet dagegen), und ei­ne Kar­te in der Mitte, wel­che die Mei­nung Got­tes wiedergibt, auf­gedeckt. Ist die Anzahl der ro­ten Kar­ten größer als die der schwar­zen, kommt es zur Heirat.[2]

Die Wahr­scheinlichkeit

..., geheira­tet zu wer­den, sollte für jede Dame gleich groß sein, nämlich 12,5%. Im weite­ren Verlauf nenne ich die fünf mögli­chen Spiel­ausgänge A, B, C, D und N für ei­ne der vier Damen oder nieman­den als Ehe­partner. P(N) = 50%, da es gleich viele Möglichkei­ten für die letz­ten 9 Kar­ten gibt, mehr rote oder mehr schwarze zu ent­hal­ten. Teilt man die restli­chen 50% durch vier, bekommt man die Wahr­scheinlichkei­ten P(A, B, C, D, N) = (12,5%, 12,5%, 12,5%, 12,5%, 50%). Umso überrasch­ter war ich, als das Pro­gramm, das ich ge­schrie­ben hatte, um das Spiel zu simulie­ren, die Wahr­scheinlichkei­ten P(A, B, C, D, N) = (8%, 14%, 14%, 14%, 50%) ermit­telte. Das konnte ja wohl nicht sein! – Oder doch?

Das Pro­gramm

... arbeite­te auf ei­ner Liste mit vier Namen [A, B, C, D] wie folgt:

  • mi­sche die 100 Kar­ten
  • für jede der 3 Run­den:
    • zie­he für jede Dame 10 Kar­ten
    • sortie­re die Damen nach Präferenz
    • lö­sche den der Dame mit der kleins­ten Präferenz zuge­ordne­ten Namen aus der Liste
  • zie­he die letz­ten 9 Kar­ten
  • falls mehr rote als schwarze Kar­ten dar­un­ter sind:
    • gib den einzigen Namen der Liste zurück
  • sonst:
    • gib niemand zurück
Zwei Anmerkun­gen dazu:
  1. Die Kar­ten wur­den mit folgendem Verfah­ren gemischt: es wer­den 4 Stapel zu je 25 Kar­ten gebildet, die jeweils nur Kar­ten ei­ner Farbe ent­hal­ten. Dann wird 100-mal ei­ne Kar­te von ei­nem zufällig aus­gewähl­ten Stapel genommen und auf den neuen Stapel gelegt. Jedes Mal, wenn im späte­ren Verlauf ei­ne Kar­te vom Stapel benötigt wurde, wurde die oberste Kar­te des Stapels gezogen.
  2. Für jede Farbe gibt es 11 mögli­che Anzah­len, die un­ter den 10 für ei­ne Dame gezogenen Kar­ten dabei sein können. Die Anzah­len kann man auf­stei­gend nach Präferenz sortie­ren: bei Herz (Liebe) und Pik (Ge­halt) sind die Zah­len auf­stei­gend und bei Karo (Kinderwunsch) und Kreuz (Treue) ab­stei­gend sortiert.[3] Hat man dann die 10 Kar­ten gezogen, kann man jeder Farbe ei­ne Pro­z­entzahl (Index + 1)/11 zwi­schen 9% und 100% zu­ordnen. Von diesen vier Pro­z­entzah­len kann man das harmoni­sche Mit­tel bilden und bekommt so ei­nen Wert für die Dame, den man mit den Wer­ten der an­de­ren Damen ver­glei­chen kann:
    x_harm=411x+11x+11x+11x mit x=Index+1
    Die Dame mit dem kleins­ten Wert wird aus­sortiert. Gibt es meh­re­re mit dem kleins­ten Wert, wird zufällig ei­ne (r)aus­gewählt.

Der Feh­ler

... musste ent­weder im Spiel selbst liegen (d. h. es handelt sich wirk­lich um ei­ne Un­gleichver­teilung) oder in mei­nem Pro­gramm zu fin­den sein. Dass kei­ne Un­gleichver­teilung vorliegt, kann schnell bewiesen wer­den: Einzige Vor­aus­setzung sei ei­ne echt zufällige Ver­teilung der Kar­ten im Stapel. Die 100 Kar­ten wer­den nun in 10 10er-Blöcke ge­teilt. Die ers­ten vier Blöcke sind für die ers­te Run­de, die nächs­ten drei für die zweite, die nächs­ten zwei für die dritte sowie der letzte für das Fi­nale. Wir können die Blöcke für jede Run­de nun nach der Präferenz des Spielers sortie­ren. Dann ist die Wahr­scheinlichkeit dafür, dass es ei­ne Dame es bis ins Fi­nale schafft und dieses über­steht, gleich der Wahr­scheinlichkeit, dass der ihr zuge­ordne­te Block in jeder Run­de nicht der mit kleins­ter Präferenz ist, mal die Wahr­scheinlichkeit, dass bei den letz­ten neun Kar­ten mehr rote als schwarze dabei sind, also P(X ∈ {A, B, C, D}) = 18/24*4/6*1/2*1/2 = 12,5%. Also musste der Feh­ler im Pro­gramm liegen.

Die Feh­lersu­che

... dau­er­te sehr lange. Nach­dem ich das kurze Pro­gramm mehrmals Zeile für Zeile durch­gegan­gen war, war klar, dass es kei­nen direk­ten Feh­ler ent­hielt. Mir blieb also nichts an­de­res üb­rig, als ver­schiede­ne Me­thoden durch scheinbar glei­che Me­thoden zu erset­zen, um zu se­hen, ob sich etwas ändert. Und sie­he da: Als ich die Kar­ten­ziehme­thode dahingehend änder­te, dass nicht mehr die oberste, sondern irgend­ei­ne zufällig be­stimmte Kar­te vom Stapel genommen wird, änder­ten sich die (8%, 14%, 14%, 14%, 50%) in die gewüns­ch­ten (12,5%, 12,5%, 12,5%, 12,5%, 50%). Die Kar­ten wa­ren also vom Pro­gramm irgendwie so gemischt wor­den, dass ei­ne Be­nach­teiligung für die erste Dame ent­stand.

Der Misch­algorithmus

... wurde dar­aufhin ge­nauer an­ge­schaut. Wenn man ihn komplett weg­lässt, die Kar­ten sortiert stapelt (erst nur Kreuz, dann Pik, dann Herz, dann Karo) und dann beim Zie­hen im­mer zufällig ei­ne aus­wählt, kam man eben­falls auf Gleichver­teilung der Damen bei den Heira­ten. Das bedeu­te­te, dass in ei­nem der 10 Blöcke, die der ers­ten Dame zuge­ordnet wa­ren (also Block 1, 5 oder 8), mit deutlich höhe­rer Wahr­scheinlichkeit schlech­te Kar­ten la­gen, als bei den an­de­ren Blö­cken. Als ich mir den Stapel dann mehrmals aus­ge­ben ließ, bemerk­te ich, dass im ers­ten Block erstaunlich viele Kar­ten dersel­ben Farbe la­gen. Die Farbe war dabei nicht im­mer dieselbe, aber die Kar­ten­anzahl von ihr überdurch­schnittlich hoch. Im Nach­hin­ein be­trach­tet ist das auch logisch, da beim Mi­schen nach oben beschriebe­nem Verfah­ren die 4 Stapel ver­schieden schnell alle wer­den und die Kar­ten vom als Letztes alle wer­den­den Stapel im ers­ten (d. h. obers­ten) Block lan­den. Somit liegt im Stapel bzw. nur im ers­ten 10er-Block kei­ne Zufallsver­teilung, sondern ei­ne Häufung an Kar­ten ei­ner be­stimm­ten Farbe vor und das hat offenbar ei­nen der­art negativen Einfluss auf die Präferenz dieses Blocks, dass die Dame nur mit 8% Wahr­scheinlichkeit bis ins Fi­nale kommt und dieses über­steht. Da wir davon aus­gehen können, dass bei Block 5 und 8 kei­ne Be­nach­teiligung gegenüber den an­de­ren Blö­cken der jeweiligen Run­de vorherrscht, können wir davon aus­gehen, dass die­se Wahr­scheinlichkei­ten sich nicht geändert ha­ben, also: P(A) = X/24*4/6*1/2*1/2 = 8%. Stel­len wir die­se Glei­chung nach X um, so erhal­ten wir X ≈ 11,5 (< 18).

Die Pro­z­entzahl

... scheint trotz des nun beho­be­nen Feh­lers etwas merkwürdig. – Wa­rum ge­rade 8%? Die Antwort dar­auf glaube ich im Limes des harmoni­schen Mit­tels gefun­den zu ha­ben. Lan­den viele Kar­ten ei­ner Farbe im ers­ten 10er-Block, gibt es zwei Fälle: Die Farbe ist Herz oder Pik, dann geht der Index der jeweils an­de­ren die­ser bei­den Far­ben gegen 0 und die Indizes der üb­rigen drei Far­ben gehen gegen 10; oder die Farbe ist Karo oder Kreuz, dann geht der Index der jeweils an­de­ren die­ser bei­den Far­ben gegen 10 und die Indizes der üb­rigen drei Far­ben gehen gegen 0:

limx/1141111-x/+3·11x/ = 0% oder limx/141111-x/+3·11x/ ≈ 12%
Da Indizes im­mer ganzzah­lig sind, musste hier mit 11 und 1 als Grenze ge­rech­net wer­den. Der Erwar­tungs­wert kann aber auch gebro­chen sein und rech­net man mit 10,77 und 0,67, so erhält man die gesuch­ten 8%.

Die Misch­tech­nik

... meines ur­sprüngl­ich verwende­ten Algorithmus findet in der Praxis wohl kaum ei­ne Anwendung, dennoch kann man auch bei per Hand gemisch­ten Kar­ten­stapeln nicht von ei­ner Zufallsver­teilung aus­gehen, so­fern man die Kar­ten nicht auf den Tisch legt, durch­mischt und sie dann wieder zu­sammenführt (wobei auch hierbei Kar­ten­pake­te zu­sammenblei­ben können). Drei beim Mi­schen per Hand verwende­te Me­thoden sind:[4]

  1. Im­mer nach vor­ne mi­schen
  2. Wech­selnd nach vor­ne und hin­ten mi­schen
  3. Riffeln
Geht man von ei­nem sortier­ten Kar­ten­stapel aus und modelliert das Mi­schen ver­einfacht mit Kar­ten­pake­ten der Größe 1, so kann man die erwarte­te Ver­teilung auf die Damen statistisch ermit­teln:
P(A)P(B)P(C)P(D)P(N)
Zufallsver­teilung13%13%13%13%50%
Pro­gramm8%14%14%14%50%
Me­thode I17%17%17%0%50%
Me­thode II (nmax = 33)18%14%12%11%45%
Me­thode III (nmax = 100)14%10%10%16%50%
Me­thode II (nmax = 10)14%22%7%7%50%
Me­thode III (nmax = 10)24%12%7%7%50%

Die Me­thoden II und III tau­chen zwei mal auf, da die maximale Anzahl der Mischvor­gänge einmal auf die Laufzeit[5] des Mischverfah­rens und einmal auf 10 gesetzt wurde.

Das Ergebnis

... die­ser klei­nen Un­tersu­chung ist zweifels­ohne noch etwas vage. Si­cher ist jedoch, dass das Ergebnis ei­nes Spiel­durch­laufs fast aus­schließlich von der Gemischheit des Stapels abhängt, da dem Spie­ler selbst nicht viele Möglichkei­ten blei­ben, das Spiel zu beeinflus­sen. Natürlich hat er scheinbar in jeder der drei Run­den die Qu­al der Wahl, allerdings wird er die Damen im­mer auf Grundla­ge irgend­eines inne­ren Algorithmus ordnen und auch, wenn die­ser nicht dem harmoni­schen Mit­tel ent­spricht, wird er höchstwahr­scheinlich für zwei glei­che Ein­ga­ben auch zwei glei­che Aus­ga­ben liefern. Da der Spie­ler kei­nen Einfluss auf die Abfolge der Kar­ten im Stapel nehmen kann, kann der Kar­ten­geber den Spielverlauf im Vor­aus ge­schickt beeinflus­sen, indem er die Kar­ten sortiert. Auch kann der Spie­ler sich bewusst gegen sei­ne Präferenz­ord­nung ent­schei­den (mög­li­cherweise tut er dies auf Grundla­ge obi­ger Be­rech­nun­gen), um am En­de die Dame zu bekommen, die er ei­gentlich ha­ben will. Aber wa­rum sollte er das tun? Immerhin dient das Spiel doch ge­rade dazu, ei­nem die Zukunft zu offenba­ren.

Der Anhang

... be­steht aus mei­nem JavaScript-Pro­gramm (mit beho­be­nem Feh­ler). Die Ent­scheidung wird hier dem Spie­ler durch die Rech­nung mit dem harmoni­schen Mit­tel abgenommen. Es können also lediglich vier Namen ein­gege­ben und auf den Button geklickt wer­den.

Whom will you marry?

Whom will you marry?

Enter the names of four persons you can imagine a marriage with.


[1]Alle Stu­fen sind: sie mag ihn, sie mag ihn sehr, sie liebt ihn, sie liebt ihn sehr, sie liebt ihn bis in den Tod, sie liebt ihn bis ins Grab, sie liebt ihn bis in die Hölle, sie liebt ihn bis in den Himmel (die letz­ten bei­den mög­li­cherweise in umgekehr­ter Reihenfolge), sie liebt ihn bis [weiß ich grad nicht], sie liebt ihn bis ins Unendli­che.
[2]Für diesen Bei­trag soll hier Schluss sein, aber das ei­gentli­che Spiel kann noch weiter­gehen: Kommt es zur Heirat, aber der Spie­ler möch­te sich schei­den las­sen, kann man den letz­ten Schritt mit weite­ren 9 Kar­ten wieder­holen. Diesmal wird ermit­telt, ob es zur Scheidung kommt.
[3]Beim Kinderwunsch sind die letz­ten Zah­len aber nicht [5, 4, 3, 2, 1, 0], sondern [5, 4, 0, 3, 1, 2] (basierend auf der durch­schnittli­chen Kinderzahl pro Frau in Deutsch­land, nämlich 1,55).
[4]Quel­le: O. Telschow: Wer mischt am bes­ten? – 3 Kar­ten­mischverfah­ren im theoreti­schen und prakti­schen Ver­gleich
[5]Die Laufzeit gibt die theoreti­sche Min­dest­anzahl an Mischvor­gän­gen an bis der Kar­ten­stapel sei­ne Aus­gangssortierung erneut erreicht. – Quel­le: ebenda.

Keine Kommentare:

Kommentar veröffentlichen