Formel vereinfachen

24.04.2009, 14:00

alle

Formel vereinfachen

Hallo zusammen.

Ich habe mühsam eine Formel für folgenden Erwartungswert ermittelt:
Gegeben seien n unterscheidbare Elemente die zufällig mit gleicher Wahrscheinlichkeit (1/n) gewählt werden. Der Erwartungswert sei nun die minimale Anzahl der Wahlvorgänge die notwendig sind, bis jedes Element mindestens einmal gewählt wurde.

Mein Ergebnis (stimmt empirisch):

$\begin{eqnarray*} \frac{1}{n^{n-2}} \sum_{r=1}^{n-1}r^{n-1}(-1)^{n-1+r}\binom{n-1}{r}\frac{n\cdot(n-r)+r}{(n-r)^2} \end{eqnarray*}$

Kann der Ausdruck vereinfacht werden?

Vielen Dank schon mal.

07.05.2009, 17:59

Auf diesen Beitrag antworten »

Schade, dass du den inhaltlichen Hintergrund nicht im anderen Thread genannt hast (eigentlich war es sowieso überflüssig, zwei Threads dazu aufzumachen).

Zitat:

Original von alle
Der Erwartungswert sei nun die minimale Anzahl der Wahlvorgänge die notwendig sind, bis jedes Element mindestens einmal gewählt wurde.

Bei solchen Sätzen verschlucke ich mich erstmal. Du meinst wohl eher

Zitat:

Gesucht ist der Erwartungswert der minimal notwendigen Anzahl von Wahlvorgängen, bis jedes Element mindestens einmal gewählt wurde.

Das rechnet man besser so:

$\begin{eqnarray*} T_k \end{eqnarray*}$ ... Zeitdauer von der Erstwahl des $\begin{eqnarray*} (k-1) \end{eqnarray*}$ -ten Elements bis zur Erstwahl des $\begin{eqnarray*} k \end{eqnarray*}$ -ten Elements (k=1..n)

Dabei ist die hier gewählte Numerierung nicht etwa eine vorher festgelegte Elementnumerierung, sondern eine fortlaufende Numerierung der Erstwahlen, wie sie eben kommen.

Klar ist $\begin{eqnarray*} T_1=1 \end{eqnarray*}$ sowie $\begin{eqnarray*} T = \sum_{k=1}^n T_k \end{eqnarray*}$ die zufällige Gesamtdauer, bis alle Elemente mindestens einmal gewählt wurden. Offenbar ist $\begin{eqnarray*} T_k \end{eqnarray*}$ geometrisch verteilt (Variante A) mit Erfolgswahrscheinlichkeit $\begin{eqnarray*} p_k=\frac{n-k+1}{n} \end{eqnarray*}$ , es gibt nämlich noch genau $\begin{eqnarray*} (n-k+1) \end{eqnarray*}$ noch nicht aufgetretene Elemente. Es folgt $\begin{eqnarray*} E(T_k) = \frac{1}{p_k} = \frac{n}{n-k+1} \end{eqnarray*}$ und somit

$\begin{eqnarray*} E(T) = \sum_{k=1}^n E(T_k) = \sum_{k=1}^n \frac{n}{n-k+1} = n\cdot \sum_{j=1}^n \frac{1}{j} \end{eqnarray*}$ .

P.S.: Ab in die Stochastik! Augenzwinkern

24.05.2009, 16:05

alle

Auf diesen Beitrag antworten »

Vielen Dank allen die sich beteiligt haben, vor allem Arthur Dent für den eleganten Beweis. Ich habe noch etwas recheriert und herausgefunden, dass dieses Problem auch als Sammlerproblem / Problem der vollständigen Serie / [URL=http://en.wikipedia.org/wiki/Coupon_collector's_problem]Coupon collector's problem[/URL]bekannt ist.

Direkt vereinfachen lässt sich meine Formel wohl nicht. Die Äquivalenz mit der Formel von Arthur Dent versuche ich noch nachweisen.

Neue Frage »

Antworten »

Formel vereinfachen

Verwandte Themen