Optimal logarithmic mixing of the Thorp shuffle

1 · The essentials

How many times must the Thorp shuffle be repeated before a deck is nearly random? For decks whose size is a power of two, this family of manuscripts gives matching answers for how that number grows. The required number of shuffles grows in proportion to the logarithm of the number of cards, rather than to the number of cards itself. The result concerns the order of the entire deck, not merely where each card might end up. It also holds regardless of the starting order. The main manuscript shows that, for a deck of $2^{d}$ cards, $1600 d$ shuffles make the difference from a perfectly random ordering tend to zero as $d$ grows. A complementary lower bound establishes that the logarithmic growth rate cannot be improved, and the main optimal-order result has a Lean formalization.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine checking a seating lottery: each guest having a plausible seat does not by itself guarantee that the whole seating plan is random. These results assess the whole plan at once, rather than checking guests one by one.

Why it matters

The family establishes the optimal growth order of the Thorp shuffle’s mixing time for power-of-two deck sizes. Its guarantee is strong in two respects: it covers the complete ordering and the worst starting deck. The companion manuscripts also describe ways to turn information about only part of a permutation into control of the whole permutation.

2 · Going further

Write the deck size as $N = 2^{d}$ . The problem is to determine how many physical Thorp shuffles are needed for the full permutation law to approach the uniform law in total variation, uniformly over initial orderings. The main manuscript shows convergence after $1600 d$ complete shuffles as $d \to \infty$ , while a support count gives a lower bound of $2 d - O (1)$ . Together these establish the optimal order $Θ (d) = Θ (lo g N)$ ; they do not identify an exact leading constant.

A recurring route in the abstracts is to control partially observed permutations and then transfer that control to the full law. Manuscript 2 uses random coordinate frames and gives a $32800 d$ bound, improved to $512 d$ when its fixed-list estimate is combined with the companion Fourier transfer. Manuscript 3 supplies a precise transfer statement: as $n$ tends to infinity through multiples of eight, if the images of a uniformly chosen $7 n /8$ labels approach the uniform injection law in average total variation, and the sign mean tends to zero, then the product of two independent permutations with that law approaches uniform on $S_{n}$ .

Other companions condition on revealed card paths. Manuscript 4 controls the endpoints of further cards, averaged over observed paths, provided a fixed positive fraction of labels lies outside both lists; with a Fourier transfer, it yields a $2048 d$ bound. Manuscript 5 reveals the trajectories of half the labels and shows that the conditional permutation of the remaining labels approaches uniform after an absolute number of coordinate sweeps. Across the family, a fixed number of sweeps yields a constant multiple of $d$ physical shuffles.

The remaining companions develop contraction, moment, and density estimates for sweeps. Manuscript 8 shows a total-variation bound of $\frac{1}{2} n^{- 5}$ after an absolute number of sweeps, while Manuscript 10 shows convergence in squared $L^{2}$ distance. Manuscript 12 uses a permanent inequality for laws on $S_{4}$ sufficiently close to uniform and with exactly uniform coordinate marginals. Manuscripts 6, 9, and 11 are marked Lean-formalized; the last passes from a conditional Schatten-moment bound for suitable coordinate sweeps to binary sweeps by analytic transfer.

Useful notions

Powers of two and logarithms
Permutations and uniform randomness
Probability distributions
Conditioning on observed information
Asymptotic upper and lower bounds

What was known before / what is new

Before

The supplied source does not give a historical sequence of earlier mixing bounds or identify a previously posed open problem. It does identify the support-count lower bound against which the upper bounds are compared. The partial-information transfer and conditional-sweep estimates are presented as results of companion manuscripts, not as an account of prior literature.

New

The central result is optimal-order full-permutation mixing in $Θ (lo g N)$ physical shuffles for $N = 2^{d}$ , from the worst initial ordering. The family provides several routes to that conclusion, including partial-permutation transfer, conditioning on trajectories, and sweep contraction estimates. It also includes explicit upper bounds and, in Manuscript 8, a quantitative error bound tending to zero.

Limits and assumptions

The Thorp results stated here concern power-of-two deck sizes; the source supplies no extension to arbitrary sizes. Optimal order does not mean an exact optimal constant, and the stated convergence guarantees are asymptotic as the deck size grows. The transfer in Manuscript 3 requires both its partial-image hypothesis and vanishing sign mean, and applies to a product of two independent permutations. Other intermediate results have their own restrictions, including unobserved-label fractions, near-uniform line laws, or exactly uniform coordinate marginals. The main optimal-order result has a Lean formalization, and Manuscripts 6, 9, and 11 are explicitly marked Lean-formalized; this does not establish formal verification of every companion claim or numerical constant. The source does not specify further open problems.

Mini glossary

Full permutation law: The probability distribution of the entire ordering of the labeled deck.
Total-variation distance: A measure of the difference between two probability laws, with distance tending to zero expressing convergence here.
Mixing time: The number of shuffle steps needed for the deck’s ordering law to become close to uniform.
Optimal order: A growth rate supported by matching upper and lower bounds up to constant factors.
Uniform injection law: The law that assigns equal probability to each placement of the selected labels into distinct positions.
Conditional permutation law: The distribution of a permutation after specified information, such as some card trajectories, has been revealed.

Keywords : Thorp shuffle · Mixing time · Total variation

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Proves that the Thorp shuffle randomizes $N = 2^{d}$ labeled cards in $Θ (lo g 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.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/238.md

Manuscripts in this family

★

Optimal-order mixing of the Thorp shuffle

26/09/2026

To be verified

We prove that the Thorp shuffle on $2^{d}$ cards mixes in $Θ (d)$ complete shuffles. The full permutation law after $1600 d$ shuffles converges to uniform in total variation as $d \to \infty$ , uniformly over the initial deck, while a support count gives a lower bound of $2 d - O (1)$ .

PDF GitHub folder

Random coordinate frames and partial permutation laws

26/09/2026

To be verified

For the Thorp shuffle on $2^{d}$ cards, we prove that the worst-start total-variation distance after $32800 d$ physical shuffles tends to zero as $d \to \infty$ . Combining our fixed-list estimate with the companion Fourier transfer improves this bound to $512 d$ shuffles. These results follow from bounds on partially observed permutation laws in random coordinate frames.

PDF GitHub folder

From partial permutation information to Fourier bounds

26/09/2026

To be verified

We show how information about partial permutations controls full permutation laws. Let n tend to infinity through multiples of eight. If the images of a uniformly chosen $7 n /8$ labels approach the uniform injection law in average total variation, and the sign mean tends to zero, then the product of two independent permutations with the given law converges to uniform on S_n.

PDF GitHub folder

Conditional information under deterministic coordinate sweeps

26/09/2026

To be verified

We bound the information remaining after paths of specified cards in the Thorp shuffle on $n = 2^{d}$ cards have been observed. After a fixed number of deterministic coordinate sweeps, the joint endpoint law of further cards is close to uniform on the available positions, on average over the observed paths, provided a fixed positive fraction of labels lies outside both lists. Combined with a Fourier transfer, these bounds give full-deck mixing after $2048 d$ physical shuffles.

PDF GitHub folder

Conditional permutations in a revealed switching environment

26/09/2026

To be verified

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.

PDF GitHub folder

Routing densities and representation contraction for Thorp sweeps

26/09/2026

Verified by Lean

For $N = 2^{d}$ cards, we prove that an absolute number of coordinate sweeps of the Thorp shuffle brings the full permutation law to total-variation distance tending to zero from uniform. The mixing time therefore has optimal order $Θ (lo g N)$ in physical shuffles.

PDF GitHub folder Lean formalization

Row–column symmetry and contraction of coordinate sweeps

26/09/2026

To be verified

We prove that the Thorp shuffle on $N = 2^{d}$ labeled cards has full-permutation total-variation mixing time $Θ (lo g N)$ in physical shuffles. An absolute number of coordinate sweeps suffices for the upper bound.

PDF GitHub folder

Random-subspace tests and trace smoothing for coordinate sweeps

26/09/2026

To be verified

We prove that an absolute number of coordinate sweeps of the Thorp shuffle on $n = 2^{d}$ positions brings the full permutation to total-variation distance at most $\frac{1}{2} n^{- 5}$ from uniform, uniformly over the initial deck. Thus $O (d)$ physical shuffles suffice, which is optimal in order.

PDF GitHub folder

Compatibility entropy and the spectrum of a Thorp sweep

26/09/2026

Verified by Lean

We prove that the Thorp shuffle on $n = 2^{d}$ cards mixes in $Θ (d)$ physical shuffles. After a sufficiently large fixed number of coordinate sweeps, the total-variation distance of the full permutation from uniform tends to zero as $d \to \infty$ .

PDF GitHub folder Lean formalization

10.

Signed tensor densities and diagram budgets for the Thorp shuffle

26/09/2026

To be verified

We prove that a fixed number of coordinate sweeps of the Thorp shuffle on $2^{d}$ cards makes the squared L² distance of the full permutation density from uniform tend to zero as $d \to \infty$ . In particular, the total-variation mixing time is $Θ (d)$ physical shuffles.

PDF GitHub folder

11.

Conditional coordinate sweeps and analytic transfer

26/09/2026

Verified by Lean

For coordinate sweeps with near-uniform line laws and line sizes among powers of two in a suitable fixed interval, we prove a Schatten-moment bound after conditioning on any feasible collection of prescribed card trajectories. An analytic transfer to binary sweeps then shows that a fixed number of sweeps mixes the Thorp shuffle on $2^{d}$ cards in $O (d)$ physical steps, matching the order of the support lower bound.

PDF GitHub folder Lean formalization

12.

A strict four-row permanent inequality and permutation moments

26/09/2026

To be verified

We prove a permanent inequality with exponent strictly below two for laws on S₄ 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 (lo g N)$ in physical shuffles.

PDF GitHub folder