Erwartete Anzahl von "Runden" um n Zufalls-Integer zu generieren

01.09.2014, 10:09	daniel-hamburg	Auf diesen Beitrag antworten »
Erwartete Anzahl von "Runden" um n Zufalls-Integer zu generieren Meine Frage: Hallo Zusammen, Die folgende Frage beschäfigt mich mehr privat, hat also keinen Hintergrund in der Uni. Die orginale Fragestellung war die folgende: Wenn ich n Folgen einer Serie habe und in jeder Runde eine Zufallsfolge auswähle, wie lange brauche ich um alle Folgen gesehen zu haben? Mathematisch formuliert habe ich also eine Menge M = {1,..,n} und wähle in jeder Runde ein Element mit p = 1/n aus. Wie lange brauche ich bis ich n verschiedene n Elemente ausgewählt habe? Meine Ideen: Um die erwartete Anzahl von Runden zu berechnen, muss ich also zunächst die Wahrscheinlichkeiten berechnen, alle Elemente in n,n+1,..,n+i,.... zu finden - richtig? Für n Elemente könnte ich ja $\begin{eqnarray} \mathbb{P}\{ \text{Wir brauchen genau n Runden}\} = \prod_{i=0}^n \mathbb{P}\{\text{Wir wählen in Runde i in neues Element aus}\}<br /> \end{eqnarray}$ berechnen, richtig? Die Wahrscheinlichkeit in dem Produkt könnte man ja dann als Bedingte Wahrscheinlichkeit ausdrücken: Ich wähle in Runde i ein neues Element aus unter der Bedienungen, dass in den vorherigen Runden i-1 verschiedene Elemente ausgewählt wurden. Intuitiv währe diese bedingte Wahrscheinlichkeit ja: $\begin{eqnarray} \frac{n-i}{n} \end{eqnarray}$ - richtig? Allerdings fehlt hier gefühlt noch die Bedienung das in den vorherigen i-1 Runden auch i-1 Elemente ausgewählt wurden. $\begin{eqnarray} \prod_{i=0}^n \frac{n-i}{n} = (\frac{n}{n})(\frac{n-1}{n})(\frac{n-2}{n})..(\frac{1}{n}) = \frac{n!}{n^n} \end{eqnarray}$ Seht ihr die Argumentation für die Wahrscheinlichkeit in n Runden alle Stichproben zu finden als richtig an? Vielen Dank schonmal im vorraus für die Antwort Viele Grüße, Daniel
01.09.2014, 10:34	Steffen Bühler	Auf diesen Beitrag antworten »
RE: Erwartete Anzahl von "Runden" um n Zufalls-Integer zu genieren. Deine Frage ist in der Mathematik als Sammelbilderproblem bekannt. Viele Grüße Steffen
01.09.2014, 11:33	daniel-hamburg	Auf diesen Beitrag antworten »
Hallo steffen, Vielen Dank! Das beantwortet meine Frage.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »