Erwartungswert Gruppengröße

17.08.2024, 09:25	Mattheo	Auf diesen Beitrag antworten »
Erwartungswert Gruppengröße Meine Frage: Auf einer Party sind 50 Gäste und sie bilden Gruppen für ein Spiel. Dazu schreibt jeder seinen Namen auf einen Zettel und legt ihn in einen Hut. Einer nach dem anderen zieht jeder Gast einen Namen aus dem Hut. Jeder Gast wird mit dem Gast, dessen Namen er aus dem Hut gezogen hat, in eine Gruppe eingeteilt. Zieht ein Gast seinen eigenen Namen, ist er ganz allein in einer Gruppe. Wenn Gast A den Namen von Gast B zieht, Gast B den Namen von Gast C zieht und Gast C den Namen von Gast A zieht, sind sie alle Teil derselben geschlossenen Gruppe und niemand sonst kann sich ihnen anschließen. Was ist die durchschnittliche Größe einer Gruppe? Meine Ideen: Die Formel die ich mir zusammengebastelt habe $\begin{eqnarray} \sum\limits_{k=1}^{50} k\binom{50}{k}(k-1)!\prod\limits_{i=50-(k-1)}^{50} \frac{1}{i}=50 \end{eqnarray}$ kann ja sicherlich nicht korrekt sein. Dabei war mein Gedankengang, dass eine Gruppe der Größe k dargestellt werden kann als ein Zykel. Hiervon gibt es jeweils $\begin{eqnarray} \binom{50}{k}(k-1)! \end{eqnarray}$ viele. Für den Erwartungswert multipliziert man das noch mit k und der dazugehörigen Wahrscheinlichkeit, aber das Ergebnis 50 kann einfach nicht stimmen. Edit by IfindU: Fehlerhaften Term entfernt
17.08.2024, 09:28	Mattheo	Auf diesen Beitrag antworten »
die $\begin{eqnarray} +\frac{50!}{50!} \end{eqnarray}$ in der Formel gehört nicht mehr dazu. Ich hatte es erst anders und dann vergessen diesen Term mit zu entfernen
17.08.2024, 15:11	HAL 9000	Auf diesen Beitrag antworten »
Man kann sich ja die Frage für allgemeines $\begin{eqnarray} n \end{eqnarray}$ stellen. Es geht um Zykel der Länge $\begin{eqnarray} k \end{eqnarray}$ mit möglichen Werten 1 bis $\begin{eqnarray} n \end{eqnarray}$ . Was genau meinst du nun aber mit "durchschnittliche Größe dieser Zykellänge"? Am Beispiel $\begin{eqnarray} n=3 \end{eqnarray}$ , da haben wir die 6 Permutationen (1)(2)(3) (12)(3) (13)(2) (1)(23) (123) (132) Da haben wir summa summarum 6x Länge 1, 3x Länge 2 und 2x Länge 3, daher eine mittlere Zykellänge $\begin{eqnarray} \frac{18}{11} \end{eqnarray}$ . Vielleicht meinst du aber auch was anderes: Man kann für jedes Element das Zykel betrachten in dem es drin ist, und nach der durchschnittlichen Länge dieser Zykel fragen - die ist hier gleich 2. Letzterer Zugang für allgemeines $\begin{eqnarray} n \end{eqnarray}$ : Betrachten wir exemplarisch die 1 und zählen, wieviele Permutationen von $\begin{eqnarray} 1,\ldots,n \end{eqnarray}$ es gibt, wo diese 1 in einem Zykel der Länge $\begin{eqnarray} k \end{eqnarray}$ liegt. Da haben wir neben der 1 weitere $\begin{eqnarray} k-1 \end{eqnarray}$ aus den $\begin{eqnarray} n-1 \end{eqnarray}$ Elementen $\begin{eqnarray} 2,\ldots,n \end{eqnarray}$ in diesem Zykel, deren Anordnung in der Auswahl entscheidend ist, d.h. dafür gibt es $\begin{eqnarray} \frac{(n-1)!}{((n-1)-(k-1))!} = \frac{(n-1)!}{(n-k)!} \end{eqnarray}$ Variationen. Nun müssen aber auch noch die restlichen $\begin{eqnarray} (n-k) \end{eqnarray}$ Elemente angeordnet werden, das geschieht vollkommen frei, d.h. das sind $\begin{eqnarray} (n-k)! \end{eqnarray}$ mögliche Permutationen. Damit ergeben sich genau $\begin{eqnarray} \frac{(n-1)!}{(n-k)!}\cdot (n-k)! = (n-1)! \end{eqnarray}$ Permutationen, wo sich 1 in einem $\begin{eqnarray} k \end{eqnarray}$ -Zykel befindet, d.h., überraschenderweise ist diese Anzahl gar nicht von $\begin{eqnarray} k \end{eqnarray}$ abhängig, oder anders formuliert: Die Zykelgröße $\begin{eqnarray} k \end{eqnarray}$ ist diskret gleichverteilt auf $\begin{eqnarray} \{1,2,\ldots,n\} \end{eqnarray}$ . Somit bekommt man einfach als Erwartungswert $\begin{eqnarray} \frac{1}{n}\sum_{k=1}^n k = \frac{1}{n}\cdot \frac{n(n+1)}{2} = \frac{n+1}{2} \end{eqnarray}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »