9Die verbesserte Konjugations-Methode

Wir haben zwei Ausgangspermutationen $\sigma \backslash sigma$ und $\phi \backslash varphi$ gefunden. Bei einer ist die Wahrscheinlichkeit zu klein, dass man der Co-Wichtel seines Co-Wichtels ist, und bei der anderen zu groß. Um dieses Problem zu beheben, wollen wir beide Permutationen kombinieren, um die korrekten Wahrscheinlichkeiten zu erhalten. Wir wollen also mit einer gewissen, noch zu bestimmenden Wahrscheinlichkeit $pp$ die Konjugations-Methode mit $\sigma \backslash sigma$ anwenden und mit Wahrscheinlichkeit $1-p1-p$ die Konjugations-Methode mit $\phi \backslash varphi$ anwenden.

Wie müsste die Wahrscheinlichkeit $pp$ sein, damit die Wahrscheinlichkeit, der Co-Wichtel seines Co-Wichtels zu sein, genau $\frac{1}{n-1}\backslash frac\{1\}\{n-1\}$ ist? Bei $\sigma \backslash sigma$ ist die Wahrscheinlichkeit null und bei $\phi \backslash varphi$ ist die Wahrscheinlichkeit $\frac{2}{n}\backslash frac\; 2n$. Wir wollen also, dass $\frac{1}{n-1}=0\cdot p+(1-p)\cdot \frac{2}{n}\backslash frac\{1\}\{n-1\}\; =\; 0\backslash cdot\; p\; +\; (1-p)\backslash cdot\; \backslash frac\{2\}\{n\}$. Damit können wir $pp$ berechnen:

Das heißt, wir müssen mit der Wahrscheinlichkeit $\frac{n-2}{2n-2}\backslash frac\{n-2\}\{2n-2\}$ die Konjugations-Methode mit $\phi \backslash varphi$ anwenden und mit Wahrscheinlichkeit $\frac{n}{2n-2}\backslash frac\{n\}\{2n-2\}$ mit $\sigma \backslash sigma$.

Wenn unsere Methode funktioniert, müssen die anderen Wahrscheinlichkeiten ebenfalls passen: Bei $\sigma \backslash sigma$ ist die Wahrscheinlichkeit, dass eine Person einen selbst als Co-Wichtel hat, die nicht der Co-Wichtel von einem ist, genau $\frac{1}{n-2}\backslash frac\{1\}\{n-2\}$. Bei $\phi \backslash varphi$ ist diese Wahrscheinlichkeit $\frac{1}{n}\backslash frac\{1\}\{n\}$. Somit haben wir bei unserer Kombination die Wahrscheinlichkeit $p\cdot \frac{1}{n-2}+(1-p)\cdot \frac{1}{n}=\frac{1}{n-1}p\backslash cdot\; \backslash frac\{1\}\{n-2\}\; +\; (1-p)\backslash cdot\; \backslash frac\; 1n\; =\; \backslash frac\{1\}\{n-1\}$. Das heißt, diese Mischung liefert eine geheime Wichtelzuordnung.

Wenn bekannt ist, ob die Konjugations-Methode mit $\sigma \backslash sigma$ oder $\phi \backslash varphi$ durchgeführt wurde, haben wir nichts gewonnen, da das Mischen der beiden Permutationen gerade davon ausgeht, dass diese Information unbekannt ist. Wir müssen also eine Methode finden, wie wir die Konjugations-Methode mit $\sigma \backslash sigma$ oder $\phi \backslash varphi$ anwenden ohne zu wissen, ob wir sie mit $\sigma \backslash sigma$ oder $\phi \backslash varphi$ anwenden.

Wir haben schon einmal gesehen, wie wir eine Permutation zufällig ziehen können, ohne zu wissen, welche wir gezogen haben: Mit der Briefumschlag-Methode. Wir können also versuchen, unser Problem mit dieser zu lösen. Dafür benötigen wir genug Umschläge, damit das Wahrscheinlichkeitsverhältnis stimmt.

Damit dieses Verhältnis stimmt, müssen wir $nn$ Versionen von $\sigma \backslash sigma$ haben und $n-2n-2$ Versionen von $\phi \backslash varphi$. In den Umschlägen können aber nicht immer die gleichen Permutationen $\sigma \backslash sigma$ bzw. $\phi \backslash varphi$ liegen, da wir auf diese dann erst die Konjugations-Methode anwenden müssten und wir dafür die gezogene Permutation aufdecken müssten. Damit müssen die Permutationen, die wir in die Umschläge gesteckt haben, schon aus der Konjugations-Methode stammen.

Wir machen also folgendes:

1. Wir präparieren $nn$ Briefumschläge mit der Konjugations-Methode mit $\sigma \backslash sigma$ und $n-2n-2$ Briefumschläge mit der Konjugations-Methode mit $\phi \backslash varphi$.

2. Wir werfen alle Umschläge in einen Hut (oder Ähnliches), mischen und ziehen einen Umschlag.

3. Die Karten dieses Umschlags werden nun wie bei der Briefumschlag-Methode ausgeteilt und verwendet.

Da diese Methode die Konjugations-Methode verbessert, werden wir sie die verbesserte Konjugations-Methode nennen.

Damit haben wir eine Methode gefunden, wie wir mathematisch korrekt wichteln können. Es stellt sich nur die Frage, wie viele Karten wir erstellen müssen: Wenn wir $2n-22n-2$ Briefumschläge erstellen müssen und jeder Umschlag $nn$ Karten enthält, müssen wir $n\cdot (2n-2)n\backslash cdot\; (2n-2)$ Karten erstellen und die Konjugations-Methode $2n-22n-2$ Mal anwenden. Dies werden ziemlich schnell ziemlich viele Karten:

Lohnt sich diese Methode trotzdem, bzw. können wir sie praktikabel machen?