Optimal-order mixing of the Thorp shuffle

← All digests

Family 238 · Probability and statistical mechanics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Split a deck into equal halves. Pair cards in corresponding positions, independently toss a fair coin to decide the order of each pair, and interleave the pairs. This is one complete Thorp shuffle.

For a deck of $n=2^d$ cards, a single card is uniformly distributed after $d$ shuffles. Does this mean the whole deck is random? No: different cards share switches, so their positions can retain joint information even when every individual position looks uniform.

Family 238 contains twelve manuscripts claiming that a constant multiple of $d$ complete shuffles suffices to randomize the full permutation. Since a simple counting obstruction already requires order $d$, this gives the optimal order $\Theta(\log n)$ for decks whose sizes are powers of two.

The family develops several arguments and additional conditional statements. Its constants are bounds, not an identification of the precise number of shuffles needed in the leading asymptotic term.

2. Background and essential definitions

Measuring the full deck

A deck ordering is a permutation in the symmetric group $S_n$, the set of all $n!$ bijections from card labels to positions. Let $U_n$ be the uniform distribution on this group, and $q_d$ the permutation law of one physical shuffle.

Independent successive shuffles compose permutations. Their $t$-step law is denoted by $q_d^{*t}$, where the asterisk means convolution. For two probability laws,

$$\|\mu-\nu\|_{\mathrm{TV}} =\frac12\sum_{\pi\in S_n}|\mu(\pi)-\nu(\pi)|$$

is their total-variation distance. Equivalently, it is the largest difference in probability they assign to the same event. Small full-deck distance therefore controls every statistic of the deck, including joint positions of any selected cards.

The mixing time here is the first integer $t$ for which this distance is at most $1/4$. Starting from a different deterministic deck translates the permutation law and leaves its distance from uniform unchanged.

Binary coordinates and sweeps

Label positions by binary strings $(x_1,\ldots,x_d)$. A physical Thorp shuffle can be written

$$(x_1,u)\longmapsto(u,x_1+\xi_u),$$

where addition is modulo two, $u$ contains the other bits, and the $\xi_u$ are independent fair bits.

Removing the deterministic cyclic rotation turns successive shuffles into switch layers along successive coordinate directions of the binary cube. One coordinate sweep visits all $d$ directions once. It costs $d$ physical shuffles, not one.

A card has each coordinate refreshed once during a sweep, explaining its uniform marginal. The other cards still constrain which collective routes are possible.

Partial observations miss global information

Even observing nearly every card can miss something. A uniformly random even permutation has exactly uniform joint images for any chosen list of at most $n-2$ labels, yet its full law has total-variation distance $1/2$ from uniform on $S_n$. Its parity is fixed.

This example explains why a proof based on partial decks must separately control the information omitted by those observations. Parity is one obstruction; representation theory organizes all such modes of dependence.

3. Development history and previous partial results

Thorp introduced the shuffle in his 1973 study of nonrandom shuffling and Faro. Its simple mechanism became a difficult mixing-time problem because local randomness spreads through a highly structured switching network. Original paper.

Morris obtained the first upper bound polynomial in $d$, of order $d^{44}$, using evolving sets and a chameleon process describing conditional card probabilities. Montenegro and Tetali improved the exponent to $29$ through spectral-profile and evolving-set methods. Morris’s first bound, Montenegro–Tetali analysis.

Entropy methods brought further progress. Morris proved an $O((\log n)^4)$ bound for arbitrary even deck sizes, then an $O(d^3)$ bound for $n=2^d$. The optimal logarithmic order remained beyond those estimates. General even decks, dyadic cubic-logarithmic bound.

Partial decks have their own history. Morris, Rogaway and Stegers studied ordered lists of cards in connection with enciphering on small domains. Czumaj and Vöcking showed that order $(\log n)^2$ shuffles mix any fixed fraction of the deck strictly below one. Such marginal statements are useful, but they leave a separate passage to the full permutation law. Enciphering application, partial-deck result.

The new family builds on these conditional-flow ideas and on finite-group Fourier analysis, classically used by Diaconis and Shahshahani for shuffling problems. Its claimed improvement is to control the remaining collective information after only a constant number of coordinate sweeps. Fourier method for shuffles.

4. What the new manuscripts claim

The headline mixing law

M1 claims the explicit asymptotic bound

$$\|q_d^{*(1600d)}-U_n\|_{\mathrm{TV}}\longrightarrow0 \qquad(d\to\infty).$$

Its proof is given independently of the companion transfer theorems. M2 gives a separate $32800d$ construction and, combining its stronger fixed-list estimate with M3’s Fourier transfer, states convergence after $512d$ physical shuffles. These different constants describe different arguments for the same logarithmic order.

Every physical shuffle uses $n/2$ independent fair bits. After $t$ shuffles there are at most $2^{tn/2}$ possible outcomes, so

$$\|q_d^{*t}-U_n\|_{\mathrm{TV}} \geq1-\frac{2^{tn/2}}{n!}.$$

Hence

$$t_{\mathrm{mix}}(d) \geq\left\lceil\frac2n\log_2\!\left(\frac{3n!}{4}\right)\right\rceil =2d-O(1).$$

Together, the claimed upper bounds and this support obstruction give $t_{\mathrm{mix}}(d)=\Theta(d)$. They do not show that $2d$ is the correct leading mixing time.

Partial and conditional laws

M2 and M4 claim that after $256d$ shuffles, the joint images of every specified ordered list of at most $7n/8$ cards approach the uniform law on distinct positions, uniformly over the list. M1 instead uses an averaged estimate for a uniformly sampled list after $200d$ shuffles. These are different inputs.

M3 proves an abstract transfer: if the images of a uniformly chosen $7n/8$ labels approach uniform in average total variation, and the mean permutation sign tends to zero, then the product of two independent permutations with that law approaches uniform on $S_n$. Its general statement assumes $n$ tends to infinity through multiples of eight. The parity condition cannot be dropped, as the even-permutation example shows.

M4 retains observed trajectories of base cards while estimating additional cards on the remaining positions, provided a fixed positive fraction of labels is left outside both lists. Its conditional error is averaged over the actual observed paths, not bounded for every possible path history.

M5 goes further: reveal the complete trajectories of half the labels and ask for the entire remaining assignment to be uniform conditional on that environment. After an explicit constant number of sweeps, it claims

$$\mathbb E_{\mathcal E} \|\nu_{\mathcal E}-U_{n/2}\|_{\mathrm{TV}}\longrightarrow0,$$

where $\nu_{\mathcal E}$ is the conditional permutation law of the remaining slots. This expresses near-independence from the revealed environment in the joint law. It permits rare exceptional environments. Its separate full-deck consequence uses $16\,040\,400d$ physical shuffles; the large constant accompanies a stronger conditional construction, rather than improving the headline numerical bound.

Spectral and stronger-distance statements

M6–M12 develop several representation and moment methods. M8 claims that an absolute number of sweeps gives total-variation distance at most $\tfrac12n^{-5}$, uniformly over initial decks. M10 claims convergence of the full density in squared $L^2$ distance after a fixed number $L$ of sweeps:

$$\mathbb E_{U_n}|f_{d,L}-1|^2\longrightarrow0, \qquad f_{d,L}(\pi)=n!\,q_d^{*(Ld)}(\pi).$$

This controls a stronger discrepancy than total variation. The number of sweeps is an absolute constant, independent of deck size.

The roles of the twelve manuscripts are:

Manuscript	Main route or additional information
M1	Conditional flow, averaged partial decks and an explicit $1600d$ full-deck bound
M2	Random coordinate frames, uniform fixed-list bounds and the combined $512d$ consequence
M3	General transfer from complementary partial permutations to Fourier bounds
M4	Specified lists and conditional information after observing base trajectories
M5	The full remaining permutation in a revealed half-deck environment
M6	Routing densities and dimension-dependent representation contraction
M7	Row–column symmetry and weighted sweep moments
M8	Random-subspace tests and a regular-trace smoothing bound
M9	Compatibility entropy controlling a fixed spectral moment
M10	Signed tensor representations and full-density $L^2$ convergence
M11	Conditional coordinate sweeps followed by analytic transfer to binary sweeps
M12	A robust four-row permanent inequality driving a recursive moment estimate

These are overlapping approaches and extensions within one result family, with their dependencies stated in the individual papers.

5. Why the advance matters

Importance: 4/5. If correct, the family resolves the optimal order of mixing for a longstanding, highly structured shuffle on dyadic decks. It improves the earlier cubic power of $\log n$ to the smallest possible order.

The full-law conclusion is considerably stronger than randomizing a few cards. It implies that every event defined by the final permutation has almost the same probability as under a uniform deck. The shuffle then generates approximate uniform permutations using $O(n\log n)$ fair bits, the same order suggested by the $\log_2(n!)$ information content of a uniform permutation.

The general partial-information transfer and conditional-environment results may also be useful in other random switching systems. That methodological breadth supports the rating, without implying cryptographic security for a particular finite implementation or a sharp practical round count.

6. The main idea

Expose cards and track the remaining flow

In M1, reveal some card trajectories and track the conditional distribution of the next card over unoccupied positions. At a switch with two free positions, its conditional masses are averaged. At a switch with only one free position, the observed trajectory determines where that free mass must go.

Subtract the uniform distribution on the available positions. Pure averaging across all coordinate directions would annihilate this centered vector in one sweep. The actual update adds a mean-zero noise term arising from switches with one free position.

An exact energy identity records only the noise from the preceding sweep. Looking backward through the other coordinate directions separates the two opposite halves of the cube. Their remaining randomness is independent conditional on the appropriate earlier history, allowing the manuscript to bound the energy of the conditional flow. This yields the averaged large-list estimate.

Recover information hidden from partial decks

Partition the labels into eight blocks. The images outside one block describe a coset of the subgroup that permutes the omitted labels. Suitable complementary marginal bounds let the argument remove a small amount of probability and bound all eight coset densities under one common retained law.

A group representation assigns a matrix to every permutation, respecting composition. Averaging these matrices under the shuffle law gives its Fourier matrices. Repeating independent shuffle blocks multiplies the matrices, so contraction in every nonconstant mode leads to mixing. The sign representation records parity and is handled separately.

M3 controls whole matrix norms through the complementary observations, including multiplicities when a representation is restricted to block subgroups. This stronger transfer explains how two independent blocks can suffice once its marginal assumptions hold.

Other routes control collective modes directly

The later papers analyze the same dependence through routing densities, row–column decompositions, compatibility counts and matrix moments. Their estimates keep the dimension and multiplicity factors needed when all representation modes are summed.

M12 illustrates the role of a small finite inequality. For permutation laws on four elements that are sufficiently close to uniform and have exactly uniform coordinate marginals, it claims a product-function inequality with an exponent strictly below two. The uniform-law permanent inequality was already known; the additional ingredient is robustness under these marginal-preserving perturbations. This saving can be propagated through a four-row decomposition of larger decks. Earlier sharp permanent bound.

Across these approaches, a recurring issue is that a forward sweep is not generally a normal or reversible operator. Bounds for a forward sweep followed by its reverse require a separate matrix-norm argument before they imply bounds for repeated forward shuffles.

7. Scope, limitations, and open questions

The headline result is for $n=2^d$ cards. The cube-coordinate argument does not establish optimal-order mixing for every even deck size, despite earlier general-even-size bounds.

The explicit constants such as $1600$ and $512$ are sufficient asymptotic choices. The family does not determine a sharp leading constant, a cutoff location, or the width of a cutoff window. Those would describe the transition much more precisely than its order.

Conditional conclusions retain their stated mode of averaging. An expected small error over revealed environments does not assert a uniform bound for every feasible history. M11’s more general conditioned line-law estimates have their own near-uniformity and line-size hypotheses; they are not blanket statements about arbitrary conditioning of the physical shuffle.

One-card uniformity, fixed-list mixing, full-deck total variation and full-density $L^2$ convergence are distinct conclusions. The extra transfer and spectral arguments are what connect them here.

8. Sources and further reading

M1 gives a comparatively direct full-deck argument, while M2–M3 explain the stronger partial-information transfer and the $512d$ consequence. M4–M5 are the sources for conditional statements, and M6–M12 develop the alternate spectral routes summarized above.

Morris’s entropy-based dyadic bound is a useful predecessor. Diaconis and Shahshahani’s finite-group Fourier approach supplies background for converting matrix contraction into total variation. The binary coordinate description in Section 2 is enough to follow the present problem without prior representation theory.

Source manuscripts

• M1. OpenAI, Optimal-order mixing of the Thorp shuffle (September 26, 2026).
• M2. OpenAI, Random coordinate frames and partial permutation laws (September 26, 2026).
• M3. OpenAI, From partial permutation information to Fourier bounds (September 26, 2026).
• M4. OpenAI, Conditional information under deterministic coordinate sweeps (September 26, 2026).
• M5. OpenAI, Conditional permutations in a revealed switching environment (September 26, 2026).
• M6. OpenAI, Routing densities and representation contraction for Thorp sweeps (September 26, 2026).
• M7. OpenAI, Row–column symmetry and contraction of coordinate sweeps (September 26, 2026).
• M8. OpenAI, Random-subspace tests and trace smoothing for coordinate sweeps (September 26, 2026).
• M9. OpenAI, Compatibility entropy and the spectrum of a Thorp sweep (September 26, 2026).
• M10. OpenAI, Signed tensor densities and diagram budgets for the Thorp shuffle (September 26, 2026).
• M11. OpenAI, Conditional coordinate sweeps and analytic transfer (September 26, 2026).
• M12. OpenAI, A strict four-row permanent inequality and permutation moments (September 26, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.