Lustiges Münzzeichen-Abzählen
Original geschrieben von Dieter Taube
Also mußt Du 16 Münzen kaufen. Habe ich irgendwo einen Denkfehler gemacht ?
Das ist natürlich eine sehr unelegante Lösung, eher ein stumpfsinniger Computeralgorithmus. Die fortgesetzt gemachte Annahme, daß nur eine Münze fehlt, bewirkt jedenfalls keinen großen Fehler. Zu diesem Zustand kommt es sehr schnell; das sieht man ohne Rechnung.
Hallo Dieter,
das war schon ein guter Ansatz, aber genau die fortgesetzte Annahme, dass nur eine Münze fehlt, bewirkt leider doch einen relevanten Fehler - jedenfalls wenn man zu früh mit der Annahme beginnt. Tatsächlich hat man bei fünf Münzen in mehr als der Hälfte der Fälle noch nicht einmal vier Münzzeichen beisammen; in knapp 10% aller Fälle sogar erst zwei!!!
Einen Computeralgorithmus kann man wie folgt basteln:
Wir legen fünf Variablen P1, P2, P3, P4, P5 an, die angeben sollen, wie hoch die Wahrscheinlichkeit ist, bislang ein, zwei, ..., fünf verschiedene Münzzeichen bekommen zu haben. Dann laufen wir in einer Schleife mit Schleifenzähler n, der für die Anzahl unserer Münzen steht, und berechnen die neuen Werte jeweils aus dem vorherigen Durchgang. Wir starten bei n=1 natürlich mit der Vorbelegung P1 = 1 (100%), P2=P3=P4=P5=0.
Wie berechnen sich die neuen Werte?
Damit wir immer noch nur ein Münzzeichen haben, müssen wir vorher nur eines gehabt haben (P1) und erneut dieses bekommen (Wahrscheinlichkeit 1/5). Also ergibt sich das neue P1 aus 1/5 * P1_alt. Zwei Münzzeichen (P2) kann ich erhalten, wenn ich vorher zwei hatte und dann erneut eines der beiden bekomme (2/5 * P2_alt) oder wenn ich vorher nur eines hatte und nun einen Treffer lande (4/5 * P1_alt), also
P2_neu = 2/5 * P2_alt + 4/5 * P1_alt.
Ebenso P3_neu = 3/5 * P3_alt + 3/5 * P2_alt.
Und P4_neu = 4/5 * P4_alt + 2/5 * P3_alt.
Schließlich das interessanteste: P5_neu = P5_alt + 1/5 * P4_alt.
Wenn wir das nun bis n=5 durchrechnen, ergibt sich:
P1 = 1/625 = 0,16 %
P2 = 60/625 = 9,6 %
P3 = 300/625 = 48 %
P4 = 240/625 = 38,4 %
P5 = 24/625 = 3,84 %
Aber, wie Dieter schon erwähnte, ist dies ein uneleganter Computeralgorithmus und keine "schöne" Lösung.
Versuchen wir es jetzt einmal mit systematischem Zählen (diskrete Wahrscheinlichkeitsrechnung ist eigentlich nichts anderes). Wenn wir n Münzen erhalten, sie nebeneinander auf den Tisch legen und die Münzzeichen notieren, so gibt es 5^n (soll heißen 5 "hoch" n) Möglichkeiten. Ich möchte jetzt "zählen", wie häufig wir <b>nicht</b> alle fünf Münzzeichen beisammen haben. Wie viele Anordnungen gibt es, in denen uns das Münzzeichen "A" fehlt? Das ist leicht: Es müssen alle Münzen ungleich "A" sein, also gibt es 4^n Fälle. Dito für "D", "F", "G" und "J". Nicht alle Münzzeichen erhalten zu haben, bedeutet, dass uns irgendeines fehlt, also addieren wir die fünf berechneten Anordnungen und erhalten 5*(4^n). Leider ist Wahrscheinlichkeitsrechnung nicht sooo einfach. Denn wir müssen schon sorgfältig zählen! Was ist mit den Fällen, in denen wir weder "A" noch "D" bekommen haben? Die haben wir doppelt gezählt. Nun gut, ziehen wir sie wieder ab:
Weder "A" noch "D" bedeutet, dass alle Münzen "F", "G" oder "J" sein müssen - macht also 3^n Fälle. Nun haben wir nicht nur die Kombination "A" und "D", sondern auch "AF", "AG", "AJ", "DF", "DG", "DJ", "FG", "FJ", "GJ", also zehn Stück. Mithin ziehen wir also 10*(3^n) ab. Fertig!?!?! Nee, leider immer noch nicht :-(
Denn die Fälle, in denen wir weder "A" noch "D" noch "F" erhalten haben, haben wir ursprünglich 3x gezählt und nun wieder 3x abgezogen (AD, AF, DF). Mist! Die müssen wir also wieder dazurechnen: Kein ADF bedeutet also nur noch "G" oder "J" bei allen Münzen, somit 2^n Anordnungen. Und Dreierkombinationen haben wir wieder 10 Stück. Somit also flugs nochmal 10*(2^n) dazugerechnet. Aber, ihr ahnt es, wir sind immer noch nicht fertig, denn es könnte ja auch sein, dass wir vier Münzzeichen nicht bekommen haben (also immer dasselbe erhalten haben). Ich wünsche dies natürlich keinem, aber wenn wir richtig rechnen wollen, müssen wir das einkalkulieren. Diese Viererkombination haben wir anfangs 4x mitgerechnet, dann 6x abgezogen (AD, AF, AG, DF, DG, FG) und danach wieder 4x addiert (ADF, ADG, AFG, DFG). also bislang 4-6+4 = 2x eingerechnet, wir müssen sie also einmal abziehen. Es gibt fünf Viererkombinationen und natürlich jeweils nur eine Anordnung (man hat ja immer das gleiche Münzzeichen erhalten), also müssen wir 5 abziehen.
Zusammengesetzt ergibt unsere Formel:
5*(4^n) - 10*(3^n) + 10*(2^n) - 5
Teilen wir dies durch die Anzahl aller Anordnungen 5^n , so erhalten wir die Wahrscheinlichkeit, dass uns bei n Münzen mindestens ein Münzzeichen fehlt.
Die Wahrscheinlichkeit, dass wir alle Münzzeichen zugeteilt bekommen haben, ist also:
P(n) = 1 - (1/(5^n)) * (5*(4^n) - 10*(3^n) + 10*(2^n) - 5)
n muss natürlich mindestens 5 sein.
Nun eine Tabelle dazu:
P(5) = 3,84 %
P(6) = 11,52 %
P(7) = 21,50 %
P(8) = 32,26 %
P(9) = 42,71 %
P(10) = 52,25 %
P(11) = 60,64 %
P(12) = 67,80 %
P(13) = 73,81 %
P(14) = 78,79 %
P(15) = 82,88 %
P(16) = 86,21 %
P(17) = 88,91 %
P(18) = 91,10 %
Es sieht so aus, als ob die Buchstaben-Tauschbörse wieder einen Ansturm erleben wird ;-)
Und nun zuallerletzt noch eine Ernüchterung: auch obige Rechnung ist nicht hunderprozentig korrekt, denn es wird nicht berücksichtigt, dass z.B. nachdem wir ein "A" bekommen haben, es noch 80.000 mal "D", "F", "G" oder "J" gibt, aber "nur" noch 79.999 mal "A". Aber dies würde erstens die Berechnung wahnsinnig verkomplizieren (es nennt sich "hypergeometrische Verteilung") und zweitens bei derartigen Größenverhältnissen das Ergebnis tatsächlich nur unbedeutend verändern.