Hallo Herr Althöfer,
über diese Frage habe ich mir auch schon Gedanken gemacht.
Also nochmal das Problem:
Wieviel Tage dauert es im Durchschnitt bis dass jeder Gefangene einmal in den kleinen Raum kommt ?
Schnellstenfalls kann es nach 100 Tagen geschehen, längstenfalls kann es beliebig lange dauern.
Es ist sehr einfach den Durchnitt mit einem Computerprogramm zu berechnen indem man 1 Millionen solche Szenarien durchläuft und den Erwartungswert empirisch berechnet:
Machen wir es der Einfachheit halber am Beispiel n = 100 Menschen.
Es dauert rund 518 Tage im Durchschnitt bis alle 100 Menschen Einmal in den kleinen Raum waren.Das ist der Mittelwert von ca 1 Mio duchläufe
Aber wie kann man es mathematisch bestimmen ?
Ich würde mich schon interessieren wie Sie auf n * ln (n) gekommen sind.
Ich habe es kombinatorisch versucht:
Der Erwartungswert der Anzahl der Tagen die erforderlich sind damit alle einmal in den kleinen Raum ausgewählt wurden ergibt sich durch folgende Summation:
Code:
Durchschnittliche_Anzahl_an_Tagen :=
100 * wahrscheinlichkeit dass mit dem 100sten Tag jeder einmal im Raum war +
101 * wahrscheinlichkeit dass mit dem 101sten Tag jeder einmal im Raum war +
102 * wahrscheinlichkeit dass mit dem 102sten Tag jeder einmal im Raum war + .....
3000 * W'keit dass mit dem 3000sten Tag jeder Einmal im Raum war
Normalerweise muss man bis unendlich addieren. Aber bereits bei 3000 Tagen addiert man an den 518,... Tagen nur noch an der 6ten Nachkommastelle.
Das Teilproblem besteht jetzt darin die einzelnen Summanden auszurechnen.
Hier kann ich leider keine geschlossene Formel angeben aber zumindestens eine Rekursive die sich recht schnell berechnen lässt:
Angenommen wir wollen ausrechnen wie hoch die W'keit ist, dass nach 600 Tagen jeder Mensch einmal in den kleinen Raum gekommen ist:
Die Wahrscheinlichkeit ist ein Bruch mit Zähler und Nenner.
Es gibt 100 ^ 600 verschiedene Möglichkeiten in den 600 Tagen einen Gefangenen auszuwählen.
Diese (grosse) Zahl mit 1200 Stellen kommt in den Nenner.
In den Zähler kommt eine etwas kleinere Zahl, und zwar die Anzahl an Möglichkeiten nach 600 Tagen Gefangene auszuwählen unter der Nebenbedingung dass
jeder der 100 Menschen mindestens einmal ausgewählt worden ist.
Hier ist mir dann eine Rekursive Formel eingefallen die einigermaßen flott die Möglichkeiten exakt zählt, wenn man Zwischenergebnisse Speichert.
Code:
anzahl_gute_möglichkeiten ( 1 Mensch, n Tage) := 1
anzahl_gute_möglichkeiten ( anz>1 Menschen, n Tage) :=
anz ^ n - anzahl_schlechte_möglichkeiten ( anz, n)
Tatsächlich war es für mich einfacher die schlechten Möglichkeiten zu zählen, also wo nach 600 Tagen noch mindestens ein Mensch dabei ist der nicht ausgewählt wurde:
Code:
anzahl_schlechte_möglichkeiten ( anz Menschen, n Tage ) :=
Summe_von_i=1_bis_anz-1 (anz über i ) * anzahl_gute_möglichkeiten ( i, n )
Wenn man auf diese Weise für 100 Mensche und 600 Tagen die Wahrscheinlichkeit berechnet dass nach 600 Tagen jeder einmal gewählt wurde so lautet die exakte Wahrscheinlichkeit dafür, also der ausgewertete Bruch:
78.46475909348281..... Prozent.
Der Zähler sowie der Nenner ist natürlich sehr groß. Die Zahlenwerte haben 1200 Stellen. Den Zähler+Nenner hier aufzuschreiben wäre sinnlos, also schreibe ich den Quotienten auf und breche nach einigen Nachkommastellen ab. Dann erhalten wir die Verständlichen Werte.
Nach 601 Tagen beträgt die Wahrscheinlichkeit
78.6566611717 ..... Prozent
Um die Ursprüngliche Summation zu berechnen,
Muss man also folgendes addieren
[CODE]
Durchschnittliche_Anzahl_an_Tagen := 599 Tage x ...
+ 601 Tage x ( 0,7865.. - 0,78464)
+ 602 Tage x ...
[\CODE]
Insgesamt ist es mühsehlig das zu Programmieren, wenn man es exakt aurechnen möchte muss man mit 6000 stellen langen Zahlen rechnen, was dann doch lange dauert.
Tricky - aber nicht mehr 100% genau - ist es wenn man nicht mit den reellen zahlen rechnet sondern mit den logarithmen von reellen zahlen.
Will man zb die Fakultät von 1 Mio berechnen, so kann man stattdessen die zehnerlogarithmen von 1,2,3, .... bis 1 Mio addieren.
Die so erhaltende Summe enthält in den Vorkommazahlen den Exponenten und die Mantisse bekommt man indem man 10 hoch (0,nachkommastellen) ausrechnet.
Ich würde aber auch gerne wissen wie man adhoc auf n*ln(n) kommt, denn das ist zwar vielleicht nicht auf die einerstelle genau aber dafür übersichtlicher.
beste Grüße
Frank Brenner