9Die verbesserte Konjugations-Methode

Wir haben zwei Ausgangspermutationen $\sigma$ und $\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 $p$ die Konjugations-Methode mit $\sigma$ anwenden und mit Wahrscheinlichkeit $1-p$ die Konjugations-Methode mit $\varphi$ anwenden.

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

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

Wenn unsere Methode funktioniert, müssen die anderen Wahrscheinlichkeiten ebenfalls passen: Bei $\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}$. Bei $\varphi$ ist diese Wahrscheinlichkeit $\frac{1}{n}$. Somit haben wir bei unserer Kombination die Wahrscheinlichkeit $p\cdot \frac{1}{n-2} + (1-p)\cdot \frac 1n = \frac{1}{n-1}$. Das heißt, diese Mischung liefert eine geheime Wichtelzuordnung.

Wenn bekannt ist, ob die Konjugations-Methode mit $\sigma$ oder $\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$ oder $\varphi$ anwenden ohne zu wissen, ob wir sie mit $\sigma$ oder $\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 $n$ Versionen von $\sigma$ haben und $n-2$ Versionen von $\varphi$. In den Umschlägen können aber nicht immer die gleichen Permutationen $\sigma$ bzw. $\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 $n$ Briefumschläge mit der Konjugations-Methode mit $\sigma$ und $n-2$ Briefumschläge mit der Konjugations-Methode mit $\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-2$ Briefumschläge erstellen müssen und jeder Umschlag $n$ Karten enthält, müssen wir $n\cdot (2n-2)$ Karten erstellen und die Konjugations-Methode $2n-2$ Mal anwenden. Dies werden ziemlich schnell ziemlich viele Karten:

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