Zum Inhalt
Anmelden
Alle Apps

Thorp-Mischen: wie oft, bis das Deck zufällig ist?

Über diese App

Deck halbieren, je Paar eine Münze: Nach log₂ N Runden ist jede einzelne Karte gleichverteilt, das ganze Deck noch lange nicht. Animiertes Mischen, exakter Abstand für 8 Karten über alle 40 320 Reihenfolgen, Zählschranke, Riffle-Vergleich, Wachstum über d. Ergebnis aus openai/math (Familie 238, Lean-formalisiert): Θ(log N) Runden genügen.

Worum es geht

Beim Thorp-Mischen (Edward Thorp, 1973) halbiert man das Deck; Karten an gleicher Stelle der beiden Hälften bilden Paare, und für jedes Paar entscheidet eine faire Münze, welche Karte zuerst kommt. Nach d = log₂ N Runden ist jede einzelne Karte exakt gleichverteilt. Wann aber ist die ganze Reihenfolge zufällig? Die bekannten Schranken waren Potenzen von d, vermutet war O(d). Ein KI-erzeugtes Preprint aus github.com/openai/math (Familie 238) zeigt nach eigener Darstellung: Für N = 2^d Karten genügen Θ(log N) Runden. Laut Katalog ist der Hauptsatz in Lean formalisiert, begutachtet ist das Preprint nicht. Das Thorp-Mischen wird in der formaterhaltenden Verschlüsselung als Baustein genutzt.

Was die App zeigt

Ein Deck wird animiert gemischt, Runde für Runde; Karte 1 lässt sich verfolgen, und ein Zähler zeigt, an wie vielen Plätzen sie nach t Runden liegen kann. Das Abstand-Panel misst die Entfernung zur Gleichverteilung: für eine einzelne Karte, für das ganze Deck exakt bei 4 und 8 Karten über alle 40 320 Reihenfolgen, dazu die Zählschranke und den exakten Riffle-Wert nach Bayer–Diaconis. Ein Wachstums-Panel trägt die nötigen Runden über d auf und listet die oberen Schranken aus der Literatur.

Worauf achten

Mische 8 Karten und vergleiche die Kurven: Die Kurve einer einzelnen Karte ist bei t = d schon null, die des ganzen Decks noch nicht. Für 16 Karten und mehr kennt niemand den exakten Abstand des Decks; sichtbar ist dann nur eine untere Schranke. Bewiesen sind mindestens 2d − O(1) nötige Runden und höchstens 1600·d; die 1600 ist eine Konstante des Beweises, kein Messwert. Eine Riffle-Runde verbraucht N Zufallsbits, eine Thorp-Runde nur N/2.

Häufige Fragen

Was ist das Thorp-Mischen?
Das Thorp-Mischen ist ein Kartenmischverfahren von Edward Thorp (1973): Das Deck wird in zwei gleiche Hälften geteilt, und für jedes Paar von Karten an gleicher Position entscheidet ein Münzwurf, welche zuerst kommt. Es braucht pro Runde nur N/2 Zufallsbits. Deshalb dient es in der Kryptografie als Baustein für Verschlüsselung kleiner Wertebereiche.
Wie oft muss man ein Kartendeck mischen?
Das hängt vom Mischverfahren ab. Für das übliche Riffle-Mischen zeigten Bayer und Diaconis, dass etwa 3/2·log₂ N Runden nötig sind, bei 52 Karten rund sieben. Beim Thorp-Mischen ist die genaue Mischzeit schwerer zu bestimmen; jede einzelne Karte ist schon nach log₂ N Runden gleichverteilt, das ganze Deck erst später.
Ist die Mischzeit des Thorp-Mischens bewiesen?
Vermutet war, dass O(log N) Runden reichen; bewiesen waren nur höhere Potenzen von log N. Ein KI-erzeugtes Preprint aus dem Katalog github.com/openai/math (Familie 238) beweist nach eigener Darstellung Θ(log N) Runden für N = 2^d Karten. Laut Katalog ist der Hauptsatz in Lean formalisiert; begutachtet ist das Preprint noch nicht.
Was kann ich in dieser App ausprobieren?
Du mischst ein Deck animiert, Runde für Runde, und verfolgst eine Karte. Für 4 und 8 Karten siehst du den exakten Abstand des ganzen Decks zur Gleichverteilung, für größere Decks eine untere Schranke. Ein Vergleich mit dem Riffle-Mischen und eine Übersicht der Schranken ordnen das Ergebnis ein.

Fach: Offene Probleme, gelöst von KI

Mehr aus Offene Probleme, gelöst von KI

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps