oai-math-revised beta

Browse › Probability and statistical mechanics › 238 Optimal logarithmic mixing of the Thorp shuffle

Conditional permutations in a revealed switching environment

OpenAI · September 26, 2026

Lean

Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion

Edit NOTES.md · Existing issues · Source on GitHub

Abstract

Fix half the labels in a Thorp shuffle on $2^d$ positions and reveal their complete trajectories. We prove that, after an explicit absolute number of coordinate sweeps, the conditional permutation of the remaining labels approaches uniform in expected total variation as $d\to\infty$, uniformly in the initial layout. The resulting constructions give full-deck mixing in a constant multiple of d physical shuffles.

If the PDF does not display here, open it directly: Open PDF.

Notes

No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.

Automatically collected notes (unreviewed)

work in progress

Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.

Formalization

  • OpenAI math release, Lean scope notes for family 238 (lean/docs/238.md, 2026). States that the formalization gives averaged conditional mixing for half-permutations in the revealed-path model and full-deck mixing after $16040400d$ steps; the conditional estimate is averaged over the outside-path law, not stated per environment. [family-level]

Possibly relevant literature (found by the agent, not checked)

Digests and expositions

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Conditional-permutations-in-a-revealed-switching-environment-September-26-2026,
  author = {{OpenAI}},
  title = {{Conditional permutations in a revealed switching environment}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Conditional-permutations-in-a-revealed-switching-environment-September-26-2026/paper.pdf}{OAI:Conditional-permutations-in-a-revealed-switching-environment-September-26-2026}},
  year = {2026}
}

Lean formalization

OpenAI provides Lean files for this family: lean/docs/238.md. The Lean statements have not been checked by people against the paper's claims.

Family 238: Optimal logarithmic mixing of the Thorp shuffle

Proves that the Thorp shuffle randomizes $N=2^d$ labeled cards in $\Theta(\log N)$ physical shuffles, settling its optimal mixing order for power-of-two deck sizes. Convergence is in total variation from the worst initial ordering and concerns the entire permutation, not just individual card positions.

Other papers in this family: