oai-math-revised beta

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

A strict four-row permanent inequality and permutation moments

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

We prove a permanent inequality with exponent strictly below two for laws on S4 sufficiently close to uniform and with exactly uniform coordinate marginals. Applied to a four-row recursion, it shows that an absolute number of coordinate sweeps brings the full permutation of the Thorp shuffle on $N=2^d$ cards to total-variation distance tending to zero from uniform as $N\to\infty$. Thus the mixing time has the optimal order $O(\log N)$ in 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.

Follow-up works

Formalization

  • OpenAI math release, Lean scope notes for family 238 (lean/docs/238.md, 2026). States that the strict four-row permanent inequality (some 4/3<p<2 and ε>0, laws on S₄ ε-close to uniform with uniform marginals) is formalized in FourRowPermanent.lean; the Thorp mixing consequence is outside the scope. [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:A-strict-four-row-permanent-inequality-and-permutation-moments-September-26-2026,
  author = {{OpenAI}},
  title = {{A strict four-row permanent inequality and permutation moments}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/A-strict-four-row-permanent-inequality-and-permutation-moments-September-26-2026/main.pdf}{OAI:A-strict-four-row-permanent-inequality-and-permutation-moments-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: