Optimal logarithmic mixing of the Thorp shuffle

Source and verification

This article explains family 238 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

Overview

A card can be uniform while the deck remains highly dependent. Family 238 collects twelve approaches and supporting estimates for optimal-order mixing of the Thorp shuffle. The common target is the law of the entire permutation, measured in physical shuffles.

🏷️ Preliminaries: one physical shuffle and a coordinate sweep

Let $N=2^d$. Split the deck into equal halves, pair corresponding cards, independently choose the order within each pair, and interleave. On binary position strings one physical Thorp shuffle has the form

$$\begin{array}{c}(x_1,\dots ,x_d)\\ ⟼(x_2,\dots ,x_d,x_1+{\xi }_{x_2,\dots ,x_d}),\end{array}$$

with addition modulo two and independent fair bits $\xi$.

Undoing the deterministic rotation turns successive steps into fair swaps along successive coordinate directions of the binary cube. A sweep visits all $d$ coordinates and costs exactly $d$ physical shuffles.

For permutation laws $\nu$ and uniform $U_N$, total variation is $\frac{1}{2}{\sum }_{\pi }|\nu (\pi )-U_N(\pi )|$. The mixing time uses the full permutation law, uniformly over deterministic starting decks. Uniformity of every one-card marginal is much weaker: one sweep already makes an individual card uniform.

🏷️ Main bounds and clock conventions

The main companion claims that after $1600d$ physical shuffles the total-variation distance tends to zero as $d\to \infty$, uniformly over starting decks. Together with a support lower bound $2d-O(1)$, this gives mixing time $\Theta (d)=\Theta (\log N)$. (OpenAI, 2026)

The random-frame companion gives $32800d$, improved to $512d$ using its fixed-list estimate with the analytic transfer companion. (OpenAI, 2026b) (OpenAI, 2026a) The deterministic-coordinate conditional-information paper gives $2048d$. (OpenAI, 2026a) These are alternative sufficient constants, not a claimed exact cutoff location.

Other companions prove an absolute number of sweeps sufficient, including one with total-variation error at most $\frac{1}{2}{N}^{-5}$, and one with vanishing squared $L^2$ density error. (OpenAI, 2026e) (OpenAI, 2026f) The common order is the important conclusion; a sweep should never be counted as a single physical shuffle.

🏷️ The support lower bound

Each physical shuffle uses $N/2$ fair bits, so after $t$ shuffles the law has support of size at most $2^{tN/2}$. For any law supported on $S$,

$$\Vert \nu -U_N{\Vert }_{\mathrm{TV}}\ge 1-\frac{|S|}{N!}.$$

To make this distance at most $1/4$, the support must contain at least $3N!/4$ permutations. Consequently,

$$t\ge \frac{2}{N}{\log }_2(3N!/4)=2d-O(1),$$

using Stirling’s estimate. This argument counts randomness available to the whole deck. It explains why uniform one-card marginals after one sweep cannot be enough.

🏷️ Conditional card paths and the upper bound

The main proof selects a random ordered list of $7N/8$ labels and reveals their paths successively. Conditional on previously exposed paths, the next card occupies the remaining slots. When both endpoints of a switch remain available, its probability masses average; when only one remains, its motion is forced.

Subtracting the uniform law on available slots gives a centered probability flow. A full coordinate sweep would annihilate a mean-zero vector under unrestricted averaging. Exposed paths introduce errors. The source writes the residual squared norm as accumulated noise and exploits independence between opposite coordinate halves over a controlled look-back interval.

The random-frame paper changes coordinates to obtain a related conditional estimate, but fixes the direction sequence before comparing laws. Conditioning on future directions as if they were fresh independent randomness would invalidate that comparison.

The revealed-environment companion exposes half the cards and proves conditional mixing of the remaining permutation, averaged over the actual exposed-path law. It does not assert uniform mixing for every possible revealed environment. (OpenAI, 2026b)

🏷️ From partial information to the full permutation

Knowing almost all sampled images are nearly a uniform injection still leaves global obstructions. For example, uniform measure on even permutations has many uniform small marginals but is not uniform on all permutations.

The partial-information companion adds a condition that the mean permutation sign tends to zero. Under its precise $7N/8$-label hypothesis, the product of two independent permutations with that law converges to uniform. (OpenAI, 2026c) This final transfer controls dependence not visible in individual-card estimates. Its harmonic-analysis machinery is used as an input here rather than developed as a group-theory topic.

The general inequality

$$\Vert \nu -U_N{\Vert }_{\mathrm{TV}}\le \frac{1}{2}{\Vert \frac{d\nu }{d{U}_N}-1\Vert }_{L^2(U_N)}$$

follows directly from Cauchy–Schwarz. It explains why the stronger density estimate in the signed-tensor companion also yields the desired total-variation conclusion.

🏷️ The remaining companion methods

The routing-density paper divides dense and sparse configurations to control contraction, and the row–column paper uses symmetry to organize the corresponding estimates. (OpenAI, 2026g) (OpenAI, 2026h) The compatibility-entropy paper retains the consistency costs between partially observed routes; the random-subspace paper turns its tests into a quantitative full-law bound. (OpenAI, 2026a) (OpenAI, 2026g)

The conditional analytic-transfer paper keeps the exact cost of assigning distinct available positions without replacement. It proves estimates for larger coordinate-line choices before transferring them back to binary sweeps. (OpenAI, 2026b) The four-row paper isolates a robust inequality for near-uniform laws on permutations of four objects with exactly uniform coordinate marginals. Its exponent is strictly below two, providing a contraction saving when the deck is recursively decomposed into four rows. (OpenAI, 2026a)

These arguments share a recurring obligation: conditioning changes the remaining switch law. Any estimate used after a reveal must retain that changed law and the dependence between cards. The companion collection offers several ways to quantify this obligation; it is not twelve independent empirical demonstrations.

🏷️ Key steps and proof outlines

Exact conditional laws come before contraction

A useful starting lemma is stronger than “unseen coins are fair.” Fix a feasible specification of the exposed cards’ entire paths. At each time, the specification fixes exactly the switches visited by those cards. Conversely, those fixed switch values force the specified paths by induction on time. The conditioning event is therefore a cylinder in the independent time-edge coin array; every other coordinate remains independent and fair. Future exposed path segments involve later time coordinates and do not reveal earlier unused coins. This justifies the adapted conditional flow in the main manuscript. (OpenAI, 2026g)

For the whole unexposed deck, let $F_s$ be its available positions at time $s$, with $m=|F_s|$, and let ${\iota }_s:[m]\to F_s$ list them in a fixed order. A completion of the unused coins gives a bijection $T_e:F_0\to F_T$. The random permutation

$$g_e={\iota }_T^{-1}{T}_e{\iota }_0$$

depends on the revealed environment $e$, but not on which free labels occupy the initial slots. Consecutive intervals compose because their intermediate indexing maps cancel. Their remaining coin arrays are conditionally independent. This is the revealed-environment paper’s essential passage from conditional one-card motion to a kernel for the entire remaining assignment. Its subsequent estimates average over the actual environment law; the cylinder lemma alone does not make each conditional kernel uniform. (OpenAI, 2026e)

flowchart TB
  A["Two available inputs: masses u and v"] --> B["Unrevealed fair switch"]
  B --> C["Both outputs: mass (u+v)/2"]
  D["One available input: mass u"] --> E["Exposed path fixes switch"]
  E --> F["Unique available output: mass u"]

A sweep erases the old mean-zero flow and leaves only recent noise

After revealing $\ell$ cards, write $B_s$ for the remaining positions and

$$w_s(x)=p_s(x)-\frac{1_{B_s}(x)}{N-\ell },$$

where $p_s$ is the next card’s conditional position law. Then ${\sum }_x{w}_s(x)=0$ and $\Vert w_s{\Vert }_2^2\le 1$. If $A_i$ averages across every coordinate-$i$ pair, the main paper writes

$$w_{s+1}=A_{i_s}{w}_s+{\xi }_s,\mathbb{E}({\xi }_s\mid {\mathcal{F}}_s)=0.$$

A mixed edge with just one available endpoint $x$ contributes noise $\pm w_s(x)({\delta }_x-{\delta }_{x+e_{i_s}})/2$; distinct mixed edges have conditionally independent signs. Define $E_s=\mathbb{E}\Vert w_s{\Vert }_2^2$, and let $b_s$ be the expected squared mass on available positions whose current matching partner is unavailable.

One-sweep memory identity

For $t\ge d$, the source proves

$$E_t=\sum _{j=1}^d{2}^{-j}{b}_{t-j}.$$

The product of all coordinate averages sends a vector to its spatial mean, so the old term vanishes. Cross terms between different noise times vanish by conditional mean zero; those on different edges vanish by independent signs. Noise from $j$ layers ago spreads over two disjoint subcubes of size $2^{j-1}$, yielding exactly the coefficient $2^{-j}$. This is an identity, not merely a spectral-gap estimate.

To bound $b_s$, look back $d-1$ layers from a coordinate update. Those intervening layers never cross the two halves defined by that coordinate. Conditional on the earlier configuration, the future switch arrays in the halves are independent. Squared flow in one half can therefore be multiplied by the expected availability at its matching site in the other half. No independence inside either half is asserted.

For a uniformly sampled initial list with at least $N/8$ labels remaining, each half has at least one-sixteenth of its sites available except on an event of probability at most $2e^{-N/256}$. This is an unconditional sampling-without-replacement estimate. Since energy is bounded by one, even a correlated exceptional event costs at most its probability. Hence

$$b_s\le \frac{15}{16}{E}_s+2e^{-N/256},E_t\le (31/32{)}^{t-2d}+32e^{-N/256}.$$

The last recurrence follows by summing the geometric memory weights: $(15/16){\sum }_{j\ge 1}(2\cdot 31/32{)}^{-j}=1$. Sequentially comparing each card’s conditional law with a uniform available slot, then using Cauchy–Schwarz, bounds the $k$-card endpoint error by $k\sqrt{N{E}_T}/2$. The final analytic transfer is still needed to turn that partial-list statement into full-deck mixing.

Random frames and deterministic blocks provide different balance estimates

The random-frame paper obtains the exact decrement

$${\Delta }_t-{\Delta }_{t+1}=\frac{1}{2}\sum _{\{x,y\}\text{ available matching edge}}(p_t(x)-p_t(y){)}^2.$$

When the next direction is uniform outside a known hyperplane, averaging this expression gives a complete bipartite energy. For a centered vector $z$ on sides of sizes $u,v$,

$$\sum _{x\in D^0,y\in D^1}(z_x-z_y{)}^2=v\sum _{D^0}{z}_x^2+u\sum _{D^1}{z}_y^2+2{\left(\sum _{D^0}{z}_x\right)}^2.$$

It is at least $\min (u,v)\Vert z{\Vert }_2^2$. The proof first establishes that the next direction’s conditional distribution is unchanged by the past observed paths. This is why replacing the online information field by one containing future directions would require a new argument. (OpenAI, 2026h)

The deterministic-coordinate companion instead uses completed-sweep symmetry. Independent suffix translations, conditional on the completed configuration, sample one position from each prefix fiber. This yields block-mass variance and available-count concentration without declaring the original entries independent. On a balanced first-sweep output, the second sweep has recurrence

$$F_{j+1}\le (1-\epsilon /4)F_j+2^{-j-1}\sum _{B\in {\mathcal{B}}_j}{M}_B^2,$$

where $M_B$ is the signed mass of a level-$j$ block. Its expected square sum is at most the initial energy. Start near level $d/2$, sum the geometric errors, and bound exceptional configurations by the initial energy. This gives a power-of-$N$ contraction in two sweeps, uniformly for deterministic signed inputs supported on at least $\epsilon N$ sites, so it can be iterated conditionally. (OpenAI, 2026d)

Routing cycles quantify the excess over a uniform injection

For a sweep followed by its reflection, route selected paths recursively into two half-sized networks. At a node, the constraint graph has one edge for a shared input switch and one for a shared output switch. It is the union of the input and output matchings, so its degree is at most two and every cycle alternates the two edge types. All cycles are therefore even, including any allowed parallel-edge two-cycle. If it has $s$ vertices, $a$ edges and $C$ cycles, there are $2^{s-a+C}$ proper two-colorings. Each coloring fixes $2s-a$ fair coins, so its combined factor is $2^{-s+C}$. Cycles are exactly the excess over the tree/path count. (OpenAI, 2026j)

Across the network, the density exponent includes

$$X=\sum _j{C}_j+{\log }_2\frac{(N{)}_k}{N^k},(N{)}_k=N(N-1)\cdots (N-k+1).$$

The falling factorial records sampling without replacement. Uniformly choosing legal child colorings is an auxiliary law; the actual switch law weights them differently. Truncating actual routing events at $X\le L$ gives a kernel bounded by $2^L/(N{)}_k$, with discarded mass measured under the actual network law.

The linear-algebra transfer is useful independently. If a symmetric stochastic kernel is $Q=A+E$, with $A,E\ge 0$, entries $A_{xy}\le B/M$, and all row and column sums of $E$ at most $p$, then $\Vert E\Vert \le p$ and $\Vert A{\Vert }_{\mathrm{HS}}^2\le B$. If a matrix block occurs in $m$ orthogonal equivalent copies, choose a maximizing unit vector in each copy. Their images under $A$ each have norm at least $\Vert Q_{\mathrm{block}}\Vert -p$, giving

$$\Vert Q_{\mathrm{block}}\Vert \le \sqrt{B/m}+p.$$

Keeping multiplicities is therefore a gain, not optional bookkeeping.

The compatibility-entropy paper gives a complementary sparse argument. Inclusion–exclusion replaces a $k$-path density by an alternating sum over subsets. It vanishes whenever the contact graph has an isolated path, because adding that path does not change the density. A surviving graph has components of size at least two. Rooted forests witness its connections; each required contact costs at most $2d/N$ under the source’s tilted sampling law. The deterministic bound of at most $(s/2){\log }_{2}s$ shared switches among $s$ paths bounds the remaining density factor componentwise. Summing these forest costs produces a small second moment. Its dense alternative retains marginal entropy deficits in the row–column compatibility inequality; dropping them would lose the weights needed in the spectral recursion. (OpenAI, 2026b)

Density, symmetry and smoothing control the analytic transfer

The remaining analytic methods can be read through three interfaces, without developing their representation-theory background.

First, partial-information transfer uses one common positive subprobability with capped masses on several complementary coset systems. For a block of dimension $D$, a subgroup-invariant subspace $W$ has average rotated projection $(\dim W/D)I$. Positivity and the mass cap bound the same average under the trimmed law. Cauchy–Schwarz then controls Fourier coefficients. The orbit of one vector in a type of dimension $a$, even with many copies, factors through the $a^2$-dimensional matrix space. A refined central-projection estimate keeps the whole Fourier matrix and yields the two-convolution result stated above. The sign component must be controlled separately. (OpenAI, 2026f)

Second, the row–column and signed-tensor papers quantify how transverse decompositions overlap. Their types are finite matrix blocks indexed by partitions. In the signed construction, an entropy quantity $F$ measures the distribution of even and odd occupancy counts, while $u$ is the dimension of the auxiliary unitary carrier. Averaging a density with eigenvalues proportional to those counts gives the positive-order domination

$$Q_{\mathrm{type}}⪯e^{F}u\mathbb{E}{R}^{\otimes p}.$$

Its proof uses the highest-weight eigenvalue $e^{-F}$ and averaging over unitary conjugates. Conversely, weighted arithmetic–geometric means bound a density’s action on the same type by $e^{-F}$. The opposite exponential factors cancel in overlap estimates, while carrier dimensions and missing-cell costs must remain explicit. The row–column method also chooses a subdiagram by minimizing a dimension-versus-deletion budget; the difference between parent and child budgets pays for restoring removed cells. (OpenAI, 2026k) (OpenAI, 2026l)

Third, random-subspace smoothing interpolates a local operator $Y=W|Y|$ through $Y(z)=W|Y{|}^{p_{0}z/2}$. One boundary of the complex strip has operator norm at most one; the other has entry bounds from both $Y^{\ast }Y$ and $Y{Y}^{\ast }$. Endpoint paths identify every intermediate placement. Only lines containing at least two selected cards pay an excess factor. Conditional on the full routing, selected paths form a uniform subset of a bounded-degree contact graph. Counting connected sets and using $(q{)}_v/(N{)}_v\le (q/N{)}^v$ bounds their exponential contact moment. Interpolation turns this into a Schatten-moment estimate, which multiplicities transfer to the full law. (OpenAI, 2026i)

Two local inequalities make recursive losses affordable

The conditional analytic-transfer paper assigns a cost to $h_L$ prescribed paths on a line of size $m$:

$${\varphi }_m(h_L)=\log \frac{m^{h_L}}{(m{)}_{h_L}},C(\mathcal{H})=\sum _L{\varphi }_{|L|}(h_L).$$

Adding $v$ paths to that line has uniform probability $(m-h_L{)}_v^{-1}=m^{-v}{e}^{{\varphi }_m(h_L+v)-{\varphi }_m(h_L)}$. For its small-parameter line law, comparison with uniform costs at most four per used line. Thus the path probability contains the difference $C({\mathcal{H}}^{+})-C(\mathcal{H})$. The conditional moment induction retains $-C(\mathcal{H})$, so revealing further paths restores the original budget rather than repeatedly charging the whole cost. A separate analytic continuation argument transfers the small-parameter estimate to binary sweeps. (OpenAI, 2026c)

Finally, the four-row inequality supplies a strict exponent $p_0<2$. Near constant functions write $f_i=1+g_i$, with uniform mean zero and $V={\sum }_i\Vert g_i{\Vert }_2^2$. Under a uniform four-point permutation, the quadratic term is

$$\frac{1}{6}\left(V-{\Vert \sum _i{g}_i\Vert }_2^2\right)\le V/6.$$

The product of $L^p$ norms has quadratic term $(p-1)V/2$. Any fixed $p>4/3$ has a strict local gap. Small perturbations of the permutation law preserve it if the coordinate marginals remain exactly uniform, which kills every linear term. Away from constants, compactness and the strict equality classification of the exponent-two permanent bound supply a uniform gap. Choosing $p_0<2$ sufficiently close to two covers both regions. Tensorization applies the inequality one coordinate at a time; the fixed saving $1-1/p_0<1/2$ then persists through four-row moment recursions. (OpenAI, 2026a)

These are selected proof mechanisms across all twelve manuscripts. Their detailed harmonic-analysis estimates and full recursive inductions remain attributed inputs, as does their composition into each manuscript’s particular mixing constant.

See Also

• Family 227 distinguishes a spectral gap, a mixing exponent, and a cutoff location in interacting-spin dynamics.
• Family 239 also needs joint dependence control beyond estimates for one random coordinate.

🏷️ Manuscripts and verification scope

• Optimal-order mixing of the Thorp shuffle — pinned manuscript and companion source.
• Random coordinate frames and partial permutation laws — pinned manuscript and companion source.
• From partial permutation information to Fourier bounds — pinned manuscript and companion source.
• Conditional information under deterministic coordinate sweeps — pinned manuscript and companion source.
• Conditional permutations in a revealed switching environment — pinned manuscript and companion source.
• Routing densities and representation contraction for Thorp sweeps — pinned manuscript and companion source.
• Row–column symmetry and contraction of coordinate sweeps — pinned manuscript and companion source.
• Random-subspace tests and trace smoothing for coordinate sweeps — pinned manuscript and companion source.
• Compatibility entropy and the spectrum of a Thorp sweep — pinned manuscript and companion source.
• Signed tensor densities and diagram budgets for the Thorp shuffle — pinned manuscript and companion source.
• Conditional coordinate sweeps and analytic transfer — pinned manuscript and companion source.
• A strict four-row permanent inequality and permutation moments — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The main selection documents the 1600d upper bound and support lower bound. Several companion selections are narrower: the partial-information selection is a finite analytic estimate; routing estimates retain the stated cutoff restriction J greater than twice the low-block size; compatibility and signed-moment selections do not include all full-density conclusions; the binary-sweep selection omits physical-shuffle law identification; and the four-row selection covers its finite inequality rather than the mixing consequence. Conditional revealed-environment estimates are averaged over the actual outside-path law. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A strict four-row permanent inequality and permutation moments.

🐻  OpenAI 2026b. Compatibility entropy and the spectrum of a Thorp sweep.

🐻  OpenAI 2026c. Conditional coordinate sweeps and analytic transfer.

🐻  OpenAI 2026d. Conditional information under deterministic coordinate sweeps.

🐻  OpenAI 2026e. Conditional permutations in a revealed switching environment.

🐻  OpenAI 2026f. From partial permutation information to Fourier bounds.

🐻  OpenAI 2026g. Optimal-order mixing of the Thorp shuffle.

🐻  OpenAI 2026h. Random coordinate frames and partial permutation laws.

🐻  OpenAI 2026i. Random-subspace tests and trace smoothing for coordinate sweeps.

🐻  OpenAI 2026j. Routing densities and representation contraction for Thorp sweeps.

🐻  OpenAI 2026k. Row–column symmetry and contraction of coordinate sweeps.

🐻  OpenAI 2026l. Signed tensor densities and diagram budgets for the Thorp shuffle.