Optimal heißt in diesem Zusammenhang, dass jede mögliche Kartenverteilung nach dem Mischen auftreten kann
Für die Darstellung werden mathematischen Symbole mittels Latex verwendet
Als Misch-Methode kommt die sog. Profi-Shuffle zum Einsatz. Die Frage ist nun, wie oft muss ein Kartenspiel, bestehend aus 52 Karten, gemischt werden, damit jede beliebige Karten-Verteilung möglich ist?
Optimal heißt in diesem Zusammenhang, dass jede mögliche Kartenverteilung nach dem Mischen auftreten kann; als Misch-Methode kommt die sog. Profi-Shuffle zum Einsatz.
Die Frage ist nun, wie oft muss ein Kartenspiel, bestehend aus 52 Karten, gemischt werden, damit jede beliebige Karten-Verteilung möglich ist?
Diese Frage ist nicht so einfach zu beantworten. Es lässt sich jedoch leicht zeigen, dass fünfmaliges Mischen nicht ausreicht.
Satz
n-maliges Mischen eines 52er Kartenspiels ist nicht optimal, n ≤ 5
Vorbereitung
Man denke sich die Karten von 1 bis 52 durchnummeriert.
Definitionen
K-Sequenz-Beispiele
Misch-Beispiel (6 Karten)
Beweis
qed.
Vor dem Mischen hat man eine Permutation \(\pi_{vorher}\), nach n-maligem Mischen die Permutation \(\pi_{nachher}\).
das Mischen ist also eine Wahrscheinlichkeitsverteilung \(Q\) über die Permutationen: \(Q(\pi_{nachher}\)), wobei für jede Permutation gilt:
\(0 \le Q(\pi_{nachher}) \le 1\), sowie \(\sum_{\pi_{nachher} \in S_{52}} = 1\), \( S_{52} = \{1,\ldots ,52\}\), Anzahl aller Permutationen = \(52!\)
Ein perfektes mischen bedeutet, dass alle Permutationen gleich wahrscheinlich sind, d.h.
\(Q_{perfekt}(\pi_{nachher}) = \frac{1}{52!} \forall \pi_{nachher}\)
Die Funktion \(Q\) ist dabei für die Profi-Shuffle recht kompliziert. Sicherlich ist die Wahrscheinlichkeit abhängig von der Anzahl der Mischvorgänge.
Es wird also ein gutes (mathematisches) Modell mit einer Wahrscheinlichkeitsverteilung \(Q_n\) für nacheinander ausgeführte \(n\) Profi-Shuffles gesucht. Anschließend kann dann die Güte der Mischvorgänge analysiert werden.
Ein solches Modell hat die Verteilung:
\(Q_n(\pi_{nachher}) = \Bigg\{ \begin{array} \frac{\binom{2^n+52-r}{52}}\big/{2^{52n}},\; falls\; \pi_{nachher}\; r \le 2^n\;K-Sequenzen\; besitzt\\0,\; falls\; \pi_{nachher}\; r > 2^n\; K-Sequenzen\; besitzt \end{array} \)
Der Abstand zweier Verteilungen kann mit einer sog. “Total Variation Distance (TV)” gemessen werden. Die TV ist wie folgt definiert:
\(\delta(Q_n,Q_{perfekt}):=\frac{1}{2}\sum_{\pi}|Q_n(\pi) - \frac{1}{52!}|\)
Weil die Summe mit /(52!/) Summanden nicht berechenbar ist, führt die Überlegung, dass die meisten Summanden gleich sind, mit:
\(A_{m,r} = \sum_{i=0}^{r-1}(-1)^i\binom{m+1}{i}(r-i)^m \) zu:
\(\delta(Q_n,Q_{perfekt})=\frac{1}{2}\sum_{r=1}^{52}A_{52,r}|\binom{2^n+52-r}{52}\big/2^{52n} - \frac{1}{52!}|\)
Die entsprechende Grafik sieht folgendermaßen aus:
Hieraus folgt, dass 7 eine angemessene Anzahl von Profi-Suffles ist!
Anmerkung: Ausführliche Informationen über alle Aspekt des Mischens von Karten findet man in folgenden Buch:
The Mathematics of Shuffling Cards von Persi Diaconics und Jason Fulman.
So spielt z. B. die Art des Karten-Gebens ebenfalls eine Rolle bzgl. der Anzahl der Mischvorgänge:
Am schlechtesten ist es, jeweils die Anzahl benötigter Karten „am Stück“ reihum zu verteilen.
Am besten ist es, 16 Karten abzuheben und anschließend einzeln 1 Karte, dann rückwärts einzeln, wieder vorwärts einzeln usw.
Letzte Änderung: 2024-04-07