4Wie oft muss im Schnitt neu gezogen werden?

Wir haben uns schon überlegt, wie wir Wichteln mathematisch beschreiben können: Gesucht ist eine fixpunktfreie Permutation der Mitspieler, also eine bijektive Abbildung $\sigma\colon\left\{1,\ldots,n\right\}\to\left\{1,\ldots,n\right\}$ ohne Fixpunkte. Das heißt, es soll $\sigma\left(k\right)\ne k$ für alle $k\in\left\{1,\ldots,n\right\}$ gelten. Üblicherweise versucht man, eine Permutation durch Ziehen von Namenszetteln aus einem Hut zu erzeugen: Das entspricht genau einer bijektiven Zuordnung zwischen Wichteln (das sind die Personen $\left\{1,\ldots,n\right\}$) und Co-Wichteln (ebenfalls die Personen $\left\{1,\ldots,n\right\}$). Die so entstandene Permutation ist aber nicht fixpunktfrei, wenn eine Person ihren eigenen Namen zieht. In diesem Fall muss man neu ziehen. Aber wie wahrscheinlich ist es eigentlich, dass das passiert?

Wir gehen davon aus, dass die Namenszettel im Hut gut gemischt sind. Dann liefert jede Ziehung von Namen aus dem Hut mit gleicher Wahrscheinlichkeit eine der $n!$ möglichen Permutationen. Es handelt sich hier also um ein Urnenmodell: Aus den $n!$ möglichen Permutationen wird durch eine Ziehung gleichverteilt eine ausgewählt. Wenn wir wissen wollen, wie wahrscheinlich es ist, dass die durch die Ziehung bestimmte Permutation fixpunktfrei ist, müssen wir uns zunächst überlegen, wie viele fixpunktfreie Permutationen von $\left\{1,\ldots,n\right\}$ es gibt.

Beispiel. Für $n=1$ ist die einzig mögliche Permutation die Abbildung $\sigma:\left\{1\right\}\to\left\{1\right\}$, welche $1$ auf $1$ abbildet. Diese ist nicht fixpunktfrei. Für $n=2$ gibt es zwei mögliche Permutationen: Erstens die Permutation $\sigma_1:\left\{1{,}2\right\}\to\left\{1{,}2\right\}$ mit $\sigma_1\left(1\right)=1$ und $\sigma_1\left(2\right)=2$, und zweitens die Permutation $\sigma_2:\left\{1{,}2\right\}\to\left\{1{,}2\right\}$ mit $\sigma_2\left(1\right)=2$ und $\sigma_2\left(2\right)=1$. Von diesen ist die zweite fixpunktfrei, die erste nicht. Es gibt also genau eine fixpunktfreie Permutation. Von den sechs möglichen Permutationen im Fall $n=3$ sind nur zwei Permutationen $\sigma_1,\sigma_2$ fixpunktfrei, wobei $\sigma_1\left(1\right)=2$, $\sigma_1\left(2\right)=3$, $\sigma_1\left(3\right)=1$ bzw. $\sigma_2\left(1\right)=3$, $\sigma_2\left(2\right)=1$, $\sigma_2\left(3\right)=2$.

Allgemein gilt: Die Anzahl $d_n$ der fixpunktfreien Permutationen von $\left\{1,\ldots,n\right\}$ ist

Das kann man mithilfe des sogenannten Einschluss-Ausschluss-Prinzips berechnen, wie du zum Beispiel auf Wikipedia nachlesen kannst. Weil es insgesamt $n!$ Permutationen von $\left\{1,\ldots,n\right\}$ gibt, beträgt der Anteil der fixpunktfreien Permutationen somit

Da beim Ziehen aus dem Hut jede Permutation mit der gleichen Wahrscheinlichkeit herauskommen kann, ist die Wahrscheinlichkeit $p_n$, dass die zufällig gezogene Permutation von $\left\{1,\ldots,n\right\}$ fixpunktfrei ist, genau der Anteil der fixpunktfreien Permutationen. Es gilt also $p_n=\frac{d_n}{n!}$.

Beispiel. Für die Menge $\left\{1,\ldots,n\right\}$, $n\le10$, zeigt die Tabelle die Anzahl $d_n$ der fixpunktfreien Permutationen, die Anzahl $n!$ aller möglichen Permutationen und den Anteil $p_n=\frac{d_n}{n!}$ der fixpunktfreien Permutationen (Quelle: Wikipedia):

Nun können wir für eine gegebene feste Teilnehmerzahl $n$ berechnen, was die erwartete Anzahl an Ziehungen ist, die notwendig sind, um eine fixpunktfreie Permutation zu erwischen. Die Wahrscheinlichkeit, eine fixpunktfreie Permutation zu erwischen, bleibt in jeder Ziehung gleich und beträgt $p_n$. Mithilfe der sogenannten geometrischen Verteilung kann man sich überlegen, dass die erwartete Anzahl an benötigten Ziehungen gleich $\frac{1}{p_n}$ ist. Intuitiv ergibt das Sinn: Wenn beispielsweise die Wahrscheinlichkeit für das Eintreten eines bestimmten Ergebnisses $\frac{1}{3}$ beträgt, dann erwarten wir, dass „im Durchschnitt“ drei, also $\frac{1}{\frac{1}{3}}$ Versuche nötig sind, um dieses Ergebnis zu erzielen.

Beispiel. Aufbauend auf der vorherigen Tabelle, können wir für $n\le10$ die erwartete Anzahl $\frac{1}{p_n}=\frac{n!}{d_n}$ an benötigten Ziehungen angeben. Den Fall $n=1$ müssen wir natürlich weglassen, da ja die Wahrscheinlichkeit $p_1$, eine fixpunktfreie Permutation von $\left\{1\right\}$ zu ziehen, gleich null ist.

Wenn wir die Werte für $\frac{1}{p_n}$ auf eine ganze Zahl runden, erhalten wir, dass im Schnitt etwa drei Ziehungen nötig sind, bis man eine fixpunktfreie Permutation erwischt! Wir wollen uns nun eine Methode überlegen, mit der man garantiert nur eine Ziehung braucht, um jedem Wichtel seinen Co-Wichtel zuzuordnen.