8Erste Ansätze mit der Konjugations-Methode

Um die Konjugationsmethode zu verwenden, benötigen wir eine fixpunktfreie Permutation $\sigma$. Eine einfache fixpunktfreie Permutation ist die Abbildung, welche die Elemente von $\left\{1,\ldots,n\right\}$ „zyklisch“ um eine Position verschiebt, d.h. die Abbildung $\sigma\colon \{1, \dots, n\} \to \{1, \dots, n\}$, die der Tabelle

entspricht.

Erinnern wir uns an das Ziel, das wir mit unserer Wichtelmethode erreichen wollen: Wir wollen, dass die bedingte Wahrscheinlichkeit $P(\sigma'(i)=k\mid\sigma'(k)=k')=\frac{1}{n-1}$ für jedes $i \ne k$ ist. Mit anderen Worten, die Wahrscheinlichkeit, dass man von einem gewissen Mitspieler beschenkt wird, soll für alle Mitspieler gleich groß sein, gegeben, dass man weiß, wer der eigene Co-Wichtel ist. Haben wir dieses Ziel erreicht, wenn wir $\sigma$ mit der Konjugationsmethode zu einer Permutation $\sigma'$ zufällig ändern?

Wenn wir $\sigma$ auf eine Karte $k$ anwenden und die Karte $k'$ erhalten, kann $k'$ durch $\sigma$ nicht auf $k$ geschickt werden. Zumindest, wenn wir mit mindestens $3$ Karten arbeiten. Damit ist für $n \ge 3$ die Wahrscheinlichkeit $P(\sigma'(k')=k\mid\sigma'(k)=k')=0$ und $k'$ nie der Wichtel von $k$. Weil wir mischen, kann aber jede andere Person, die nicht $k$ oder $k'$ entspricht, der Wichtel von $k$ sein. Von diesen gibt es $n-2$ viele. Wir erhalten also

Damit stimmen die Wahrscheinlichkeiten nicht mit den gewünschten überein: Die Wahrscheinlichkeit, dass man von einer bestimmten anderen Person beschenkt wird, ist mit $0$ zu klein, wenn man ihr Wichtel ist, und mit $\frac{1}{n-2}$ zu groß, wenn man nicht ihr Wichtel ist.

Eine andere Permutation

Wenn die Wahrscheinlichkeit, jemandes Co-Wichtel zu sein, für alle Personen (außer einem selbst) gleich sein soll, müssen wir also eine andere Permutation ausprobieren. Das Problem ist, dass $\sigma$ es nicht zulässt, von seinem eigenen Co-Wichtel als Co-Wichtel gezogen zu werden. Wir benötigen also eine Permutation, auf die das zutrifft. Was muss eine solche Permutation $\varphi$ erfüllen? Es soll eine Person $i$ geben, deren Co-Wichtel $\varphi\left(i\right)$ der Wichtel von $i$ selbst ist. Es soll also ein $i$ geben, sodass $\varphi(\varphi(i)) = i$ gilt.

Eine einfache solche Permutation $\varphi\colon\{1,\dots, n\} \to \{1,\dots, n\}$ können wir für $n \ge 4$ durch die folgende Tabelle bauen:

Wie sehen die Wahrscheinlichkeiten für diese Permutation aus? Wir haben durch die Konjugationsmethode mit $\varphi$ eine Permutation $\varphi'$ erhalten und diese hat $\varphi'(k) = k'$. Wenn die Karte $k$ beim Mischen zur ersten oder zweiten Karte wird, ist der Wichtel von $k$ sicher $k'$. Dies passiert mit der Wahrscheinlichkeit $\frac 2n$. Wenn $k$ beim Mischen zu irgendeiner anderen Karte wird, ist $k'$ nie der Wichtel von $k$. Somit haben wir $P(\varphi'(k') = k\mid \varphi'(k) = k') = \frac 2n$. Im anderen Fall, wo $k$ durchmischen nicht zur ersten oder zweiten Karte wird, ist jeder andere Person, die nicht $k$ oder $k'$ ist, als Wichtel gleich wahrscheinlich. Das sind noch $n-2$ Personen. Diese müssen sich die Restwahrscheinlichkeit damit gleichmäßig aufteilen und wir erhalten $P(\varphi'(i) = k \mid \varphi'(k) = k') = (1-\frac 2n) \cdot \frac{1}{n-2} = \frac 1n$. Zusammengefasst hat $\varphi'$ die Wahrscheinlichkeiten

Hier ist die Wahrscheinlichkeit, dass man der Co-Wichtel seines Co-Wichtels ist, mit $\frac{2}{n}$ zu hoch, und die Wahrscheinlichkeit, jemand anderes als Wichtel zu haben, mit $\frac{1}{n}$ zu gering. Für unsere Rechnung müssen wir auf ein Detail aufpassen: Sie funktioniert nur, wenn $n \ge 5$.

Wir haben jetzt eine Permutation gefunden, bei der die Wahrscheinlichkeiten jeweils zu hoch und eine, wo sie jeweils zu niedrig sind. Können wir dies kombinieren, sodass die Wahrscheinlichkeiten passen?