WANN VERGISST EIN ÜBERHANDMISCHEN DAS KARTENSPIEL?

Kartenmischen ist eine konkrete Version einer Grundfrage der Wahrscheinlichkeitstheorie: Wie lange braucht ein Zufallsprozess, um zu vergessen, wo er begonnen hat? Ein frisch geöffnetes Kartenspiel ist geordnet. Jedes Mischen bringt es ein wenig mehr durcheinander, bis keine Spur der ursprünglichen Ordnung mehr nachweisbar ist.

Mathematiker unterscheiden zwei Ebenen der Antwort. Die Mischzeit gibt die Größenordnung an. Ein Cutoff sagt viel mehr: Um einen genauen Zeitpunkt herum wechselt das Kartenspiel fast schlagartig von „deutlich nicht gemischt“ zu „gründlich gemischt“. Mischt man etwas weniger lange, kann man es noch erkennen; mischt man etwas länger, nicht mehr.

Das Mischen, wie ein Mathematiker es sieht

Beim Überhandmischen hält man das Kartenspiel in einer Hand und lässt kleine Kartenpäckchen in die andere fallen. Das Paper modelliert das so: Jede der n − 1 Lücken zwischen benachbarten Karten wird unabhängig mit Wahrscheinlichkeit p geteilt, und die Reihenfolge der entstehenden Päckchen wird umgekehrt. Ein vollständiger Durchgang durch das Kartenspiel zählt als ein Mischvorgang.

Laut dem Paper hatten frühere Arbeiten die Größenordnung bereits festgelegt. Pemantle grenzte die Mischzeit zwischen n² und n² log n ein; Jonasson zeigte dann, dass n² log n die richtige Ordnung ist. Doch die genaue Konstante, und ob überhaupt ein scharfer Cutoff auftritt, blieben offen: Diaconis und Pal führten den Cutoff des Überhandmischens 2022 als offenes Problem auf.

Das Ergebnis

Yunjiang Jiang beweist, dass der Cutoff existiert, und lokalisiert ihn.

Satz. Für eine feste Teilungswahrscheinlichkeit p mischt das Überhandmischen in erster Ordnung nach

p² / (2(1 − p)π²) × n² log n

Mischvorgängen. Kurz davor ist das Kartenspiel noch weit vom Zufall entfernt; kurz danach ist es nahe am Zufall.

Für p = 1/2 — im Schnitt wird jede zweite Lücke geteilt — wird die Formel zu n² log n / (4π²).

Wie der Beweis funktioniert

Der Beweis besteht aus drei unabhängigen Teilen.

1. Die untere Schranke verfolgt eine einzelne Karte. Ihre Position entwickelt sich auf bemerkenswert saubere Weise: Exakte kosinusförmige Muster klingen mit bekannter Rate ab, sogar bei einem endlichen Kartenspiel. Über das ganze Kartenspiel summiert, bewahren sie bis zum vorhergesagten Zeitpunkt eine nachweisbare Spur der Anfangsordnung.
2. Die obere Schranke vergleicht zwei Kartenspiele, die sich nur durch die Vertauschung zweier Karten unterscheiden. Mit denselben zufälligen Teilungen gemischt, verhält sich der Unterschied wie zwei markierte Positionen, die durch das Kartenspiel wandern, bis sie Nachbarn werden und verschmelzen können. Die Rate, mit der das geschieht, passt zur unteren Schranke.
3. Eine statische Ungleichung über Permutationen, die nichts mit Mischen zu tun hat, verwandelt diesen Vergleich in eine Aussage über das ganze Kartenspiel. Es ist der technischste Teil des Papers, rekursiv aufgebaut auf Tabellen, die zählen, wie Karten über Blöcke verteilt sind.

Das Paper beweist außerdem einen Cutoff für ein anderes Maß der Unordnung, die relative Entropie, ohne dessen genaue Lage zu bestimmen.

Was die Formel über ein echtes Kartenspiel sagt

Setzt man ein Kartenspiel mit 52 Karten und p = 1/2 in die Formel ein, erhält man 52² × ln 52 / (4π²), etwa 270 Mischvorgänge. Das ist unsere eigene Rechnung, kein Wert aus dem Paper, und sie sollte als grober Anhaltspunkt gelesen werden: Der Satz beschreibt das Verhalten sehr großer Kartenspiele, und der Korrekturterm ist nicht beziffert. Zum Vergleich zitiert das Paper die von Bayer und Diaconis für das Riffle-Mischen (riffle shuffle) ermittelte Größenordnung (3/2) log₂ n — etwa 8,6 für 52 Karten, mit demselben Vorbehalt. Der Abstand zwischen n² log n und log n ist es, der das Überhandmischen so langsam macht.

Erste Ordnung, idealisierte Hände

Das Ergebnis gilt in erster Ordnung: Es liefert weder die Breite des Übergangsfensters noch seine genaue Form. Die Teilungswahrscheinlichkeit wird festgehalten, und die Teilungen werden als unabhängig angenommen, eine Idealisierung echter Hände. In einer Fußnote gibt der Autor an, dass das KI-System GPT-6 Astra „bei der Entwicklung von Argumenten, der Überprüfung von Rechnungen und der Vorbereitung der Darstellung verwendet“ wurde und dass der Autor für den mathematischen Inhalt verantwortlich ist. Das Paper ist ein Preprint.