E. O. Thorp's shuffling scheme, studied initially for the game of Faro, is the following thorp-1973.pdf. A stack of $n=2^d$ cards is indexed by the bit strings of length $d$ in $V=\mathbb F_2^d$, ordered lexicographically. One physical shuffle pairs every card $x$ with $x+e_1$, the string obtained by flipping the first coordinate, and independently for each pair chooses one of the two orders with a fair coin. Writing $R(x_1,\dots,x_d)=(x_2,\dots,x_d,x_1)$ for the cyclic rotation, a physical shuffle is $RS$ where $S$ applies the chosen swaps in the pairs $\{x,x+e_1\}$. Repeating $RS$ alone would only randomize the first few coordinates, so the shuffle alternates between the swap and the rotation. In the rotating frame $X_t=R^{-t}Y_t$, where $Y_t$ is the physical permutation after $t$ shuffles, the dynamics become
$$ X_{t+1} = R^{-t}S_{t+1}R^t X_t . $$
A layer is one step of $X$, acting by fair independent switches along a single coordinate matching of the cube. A sweep consists of $d$ consecutive layers, one in each coordinate, so that after $d$ physical shuffles the rotating and physical frames coincide.

Thorp's shuffle is used as the basis of deterministic enciphering on small domains mrs-2009-thorp-encipher.pdf, ./hoang-morris-rogaway-2012-enciphering-scheme.pdf. Its mixing properties were first bounded by Morris, who obtained $O(d^{44})$ physical shuffles for power-of-two decks morris-2008.pdf; the intermediate $O(d^{29})$ estimate of Montenegro and Tetali montenegro-tetali-2006.pdf; and the subsequent $O(d^3)$ bound of Morris for $n=2^d$ morris-2013.pdf. For every even deck size, Morris proved $O((\log n)^4)$ morris-2009.pdf. Estimates to date do not settle the dependence on the constant, and the focus is less on the leading constant than on a comparison between two far more refined laws: the law of the entire permutation, conditioned on the observed trajectories of a fixed subset of the cards.

Fix $m=n/2$ labels of the deck as outside labels, leaving $m$ free labels. Reveal the full trajectories of the outside labels through an interval ending at a sweep boundary. Two facts then hold. First, at every boundary the outside labels occupy $m$ slots, and the free labels occupy the complementary $m$ slots. Second, every switch coin on an edge incident to an outside card is determined by the trajectory, because the trajectory lists both the incoming and outgoing endpoints of that edge; the only unexposed coins are the ones on free-free edges. The unexposed coins compose to a bijection $T$ from the initial free slots to the final free slots, and indexing both sets in increasing order turns $T$ into a permutation $g$ in $S_m$. The permutation's conditional law $\nu_{\mathcal E}$, given the outside trajectory $\mathcal E$, is the object of study.

The main assertion is that this conditional law is nearly uniform.

Theorem. Let $n=2^d$ and start the shuffle from any deterministic deck. Fix $m$ outside labels and $m$ free labels. Take $s_0=400$ and $J=40000$ and run $J(s_0+1)=16040000$ sweeps. Let $\nu_{\mathcal E}$ be the conditional law of the free-slot permutation $g$ given the outside trajectory $\mathcal E$, and let $U_m$ be uniform measure on $S_m$. Then
$$ \sup_{\text{deterministic starts}} \mathbb E_{\mathcal E}\|\nu_{\mathcal E}-U_m\|_{\mathrm{TV}} \longrightarrow 0 \qquad(d\to\infty). $$
Consequently, the full-deck law from every deterministic start is within $1/4$ in total variation of uniform after $J(s_0+1)d = 16040400 d$ physical shuffles.

The statement is equivalent to the pair consisting of $\mathcal E$ and $g$ having law close to the product of the environment law and $U_m$:
$$ \|\mathcal L(\mathcal E,g)-\mathcal L(\mathcal E)\otimes U_m\|_{\mathrm{TV}} = \mathbb E_{\mathcal E}\|\nu_{\mathcal E}-U_m\|_{\mathrm{TV}} . $$
The equivalence says that the free-slot permutation is nearly independent of the observed environment. The averaged statement is not the same as a statement for each environment; rare environments can leave too few useful free switches. The proof deletes a small amount of probability under the actual outside-path law, restoring it at the end.

The upper bound is sharp in the exponent of $d$. In $t$ physical shuffles there are at most $2^{tn/2}$ switch strings (half the coins are redundant to the choices of switched pairs), so the support of the shuffle law in $S_n$ has uniform mass at most $2^{tn/2}/n!$ and the law is at total-variation distance at least $1-2^{tn/2}/n!$ from uniform. In particular, distance at most $1/4$ requires
$$ t\ge\left\lceil\frac{2}{n}\log_2\frac{3n!}{4}\right\rceil = 2d - O(1), $$
and distance at least $1-2^{-n/2}$ holds whenever $t\le d-2$, so the mixing time in Theorem 1 is of order exactly $d$.

The proof has three stages. First, any ordered half-deck, from any deterministic starting layout, is brought within $n^{-3}$ of uniform ordered endpoints after $400$ sweeps. The route is a two-copy calculation for one sweep, split into averages within large subcubes and fluctuations inside them, followed by a two-sweep contraction. Second, alternating a $400$-sweep preparation interval with a single active sweep and repeating this chunk $40000$ times, truncation of the preparation law gives domination by a uniform free set together with an independent uniform slot permutation. During the active sweep, counting two-free edges met by each free carrier, and deleting outcomes with too many poor carriers, gives enough fresh coin constraints that agreement at many endpoints becomes unlikely. A symmetric-group character bound converts endpoint agreement into a trace contraction, and preparation domination promotes the trace to a positive-operator contraction that iterates across chunks. Third, coupling two decks, one from any fixed start and one from uniform, uses the preparation lemma on the outside labels and the conditional bound on the free labels.

Three alternative constructions give weaker but independent upper bounds, each with its own mechanism and its own mass and independence arguments. A reset construction extracts an exact uniform component from a long block, then computes a return probability for a central relative-permutation increment between two coupled copies, using the splitting technique of Nummelin. A trajectory-overlay construction adds predictable independent fair switches to a base trajectory without changing the underlying shuffle law, mixes one group of indices with a character estimate, and then uses three rounds on two transverse partitions, completed by a contingency-table local-limit theorem hastad-2006-square-lattice-shuffle.pdf. A two-halves construction reveals only the unlabelled occupancy history of two colors; the resulting internal half-permutations are independent conditional on the history, and a positive-operator Fourier bound emerges from truncation of the two factors plus an inverse-image bound on the first block.

The character input throughout is the uniform Larsen--Shalev estimate ./larsen-shalev-2008.pdf, in the fixed-slack formulation recorded by Keller, Lifshitz and Sheinfeld keller-lifshitz-sheinfeld-2024.pdf. Standard branching, Schur orthogonality and hook-length formulas enter through ./sagan.pdf and etingof-2011-intro-representation-theory.pdf; the special case of reciprocal-square summability of irreducible degrees also follows from Liebeck and Shalev liebeck-shalev-2004.pdf. Sequential total-variation comparison in Morris's exclusion-process analysis supplies a comparison used in the half-deck preparation step morris-exclusion-2006.pdf. Negative dependence under partial symmetrization, in a restricted form needed for the poor-carrier bound, is due to Borcea, Branden and Liggett borcea-branden-liggett-2009-negative-dependence.pdf.

The conditional slot-bijection lemma fixes the basic bookkeeping. Conditional on the outside trajectory, the outside-attached switch coins are fixed and the remaining coins are independent and fair. Composing the free-free coins through an interval gives a bijection $T_e$ from the initial to the final free-slot set, hence a permutation $g_e=\iota_T^{-1}T_e\iota_0$ in $S_m$ where $\iota_0,\iota_T$ are the increasing identifications of slot sets with $[m]$. The conditional law of $g_e$ does not depend on which free labels entered the interval, and the laws on disjoint intervals compose by convolution with the later increment on the left. Uniqueness of the single-card path through one sweep is used repeatedly: initial and final positions determine every intermediate position, because just before coordinate $i$ is updated, its earlier hits are terminal and later hits are still initial.

For one tracked free card, the same lemma gives a linear evolution. Conditional masses average across a free-free edge and transport across a mixed edge; the uniform vector follows identically. A signed difference from uniform therefore has sum zero and Euclidean norm nonincreasing in time, and this linear rule is adapted to progressively revealed paths even though it is a formula for the conditional law given the full trajectory. This linear evolution supplies the one-sweep and two-sweep estimates of $Q$ used in the half-deck preparation.



The analysis is done on row vectors of probabilities or of their differences, in the ordinary Euclidean norm. If $u$ is a free-slot row vector, then $\|uQ\|\le\|u\|$ by convexity of the square applied inside each column followed by row sums. Put $A_E=\mathbb E[QQ^\top]$, with the expectation over the paths from the fixed blocked start $E$. Its entry at $x,y$ is the probability that two copies, started at $x,y$ and run independently conditional on the common blocked paths, finish at the same position; both the switch randomness and the blocked-path randomness are averaged. The matrix $A_E$ is symmetric and a contraction, as is $QQ^\top$.

Let $h=\lfloor d/2\rfloor$, and call the blocks determined by bits $>h$ the coarse blocks. These have size $2^h$. For a free-slot vector $u$, write $u_c$ for the orthogonal projection onto the subspace constant on coarse blocks; the projection averages $u$ over the free slots inside each coarse block. Call a blocked set $E$ good when its fraction in every coarse block is at most $3/4$. Set $q=7/8$ and
$$ \epsilon_n = n\left(\frac{3/2}{2^{3/4}}\right)^{2^h}. $$
From a good starting set, one sweep contracts fluctuations within large subcubes; the same sweep makes the expected energy of the output coarse averages small. Combining the two estimates in a second sweep contracts the whole vector.

Lemma (coarse-block estimates). For the one-sweep matrix $Q$ and every free-slot row vector $u$, a good starting blocked set $E$ satisfies
$$ \mathbb E\|uQ\|^2 = u A_E u^\top \le \|u_c\|^2 + q^{d-h}\|u\|^2. $$
For every starting blocked set $E$ with $|E|\le n/2$, the ending set satisfies $\mathbb P(E'\ \text{not good})\le\epsilon_n$. If $u$ has sum zero, then its coarse part on the ending free slots satisfies
$$ \mathbb E\|(uQ)_c\|^2\le(4\cdot 2^{-h}+\epsilon_n)\|u\|^2. $$

Proof. Let $p_k(x)$ be the initial blocked fraction in the block of size $2^{k-1}$ having bits $>k$ equal to those of $x$ and bit $k$ opposite to that of $x$, and set $q_k(x)=(1+p_k(x))/2$. Let $j$ be the largest coordinate on which $x,y$ differ, or $0$ when $x=y$. The identity
$$ A_E(x,y)=2^{-j}\prod_{k=j+1}^d q_k(x) $$
follows from two-copy path analysis. The two copies coalesce on the first coordinate on which they agree; before that they are independent of each other. For $k>j$, given that they matched through stage $k-1$ and are now together, they stay together with probability $1$ when the neighbor slot is blocked and with probability $1/2$ otherwise, and the probability the neighbor is blocked, given this history and their common prefix, is $p_k(x)$. Multiplying these stay-together probabilities gives the identity, including the case $j=0$.

The row sum inside the block of $x$ equals $\prod_{k=h+1}^d q_k(x)$. For $1\le j\le h$ there are $2^{j-1}(1-p_j(x))$ free $y$'s with that particular last-difference value, and the contributions telescope with the diagonal term. This row sum is constant on the coarse block of $x$ and at most $q^{d-h}$ when $E$ is good, because each factor $p_k(x)$ for $k>h$ is a weighted average of coarse-block blocked fractions. The coarse-constant subspace is thus invariant under $A_E$ and contracts there by $q^{d-h}$. On its orthogonal complement, the between-block entries contribute zero and the symmetric within-block matrices have norm at most their maximum row sum, again at most $q^{d-h}$ because all entries are nonnegative. Symmetry excludes a cross term between the two subspaces.

The blocked-slot indicators satisfy, for any set of slots, that the probability all are blocked is at most the product of their marginal probabilities. This holds at the deterministic start; a single fair swap preserves the inequality, since for a test set containing one of the two swap slots the two old bounds are averaged, and for one containing both, the product of the marginals can only increase when both are replaced by their average. Disjoint simultaneous swaps are processed one at a time. After a sweep all marginals equal $r/n$ by single-card uniformity. Expanding the product of $1+$indicator over the coarse block of a fixed output, applying Markov's inequality, and taking the union bound over $2^{d-h}$ coarse blocks gives $\mathbb P(E'\ \text{not good})\le \epsilon_n$. This restricted form of preservation of negative dependence under partial symmetrization is due to Borcea, Branden and Liggett borcea-branden-liggett-2009-negative-dependence.pdf.

For the last display, on good output the squared block sums are divided by block free-slot counts of at least $2^h/4$ by goodness, giving the factor $4\cdot 2^{-h}$ against the unconditional numerator bound. On bad output the norm is bounded by $\|u\|$ by contraction. The bound combines the two cases.

Proposition (uniform half-deck preparation). For all sufficiently large $d$, every ordered list of $k\le n/2$ distinct labels, from every deterministic starting layout, has endpoint law within $n^{-3}$ in total variation of uniform ordered distinct positions after $400$ sweeps.

Proof. Fix at most $m$ blocked cards and track one specified free card over sweeps, starting deterministically. Let $u_s$ be its law conditional on the blocked paths through sweep $s$, minus uniform on the then-free slots. Given those paths, the next blocked paths are fresh from the then layout; on revealing them, $u_{s+1}=u_s Q$ for their conditional matrix. Future blocked paths reveal nothing about the unused free coins of the past, and uniform vectors are carried to uniform vectors. In particular there is a pathwise norm contraction. Write $a_s=\mathbb E\|u_s\|^2$, with $a_0\le 1$.

For $s\ge 1$ the mean squared coarse part of $u_s$ is bounded by $(4\cdot 2^{-h}+\epsilon_n)a_{s-1}$ given the paths through the previous sweep. The contribution of the bad event after sweep $s$ is at most $\epsilon_n a_{s-1}$ by pathwise contraction and the bad-set probability. Applying the good-start estimate for the next sweep and contraction otherwise,
$$ a_{s+1}\le q^{d-h}a_s+(4\cdot 2^{-h}+2\epsilon_n)a_{s-1}\le n^{-1/20}a_{s-1} $$
for all sufficiently large $d$. Here $a_s\le a_{s-1}$, the quantity $\epsilon_n$ decays faster than any inverse power of $n$, and $\log_2(8/7)/2>1/20$. Taking the fixed length $s_0=400$ and iterating with the sweep index jumping by two gives $a_{s_0}\le n^{-10}$.

For any ordered list of $k\le m$ cards from any fixed start,
$$ d_{\text{TV}}\left(\text{law of their positions after }s_0\text{ sweeps},\ \text{uniform ordered distinct positions}\right)\le\delta_n:=n^{-3} $$
for large $d$. For each next card, condition first on the paths of the previous cards, taking them as the blocked set above. The mean total-variation deviation from uniform on the remaining end slots is at most $\sqrt{n a_{s_0}}/2$ by Cauchy-Schwarz. Conditioning on the previous endpoints alone cannot increase this averaged bound, by mixing with the same uniform comparison. The next-card bounds sum to the joint bound by interpolating between the actual endpoint law of an initial segment of the list and uniform sequential conditional laws on the rest; consecutive laws differ by at most the averaged next-card deviation. Since $k\sqrt{n\cdot n^{-10}}/2\le\delta_n$, the claimed deviation follows. The sequential total-variation comparison also appears in Morris's exclusion-process analysis morris-exclusion-2006.pdf.


After the $400$-sweep preparation, the shuffle alternates a $400$-sweep preparation with a single active sweep, repeated $J=40000$ times. For each free carrier, meaning each card considered from its slot at the start of the active sweep, count the stages of that sweep at which the carrier sits on an edge with two free endpoints. Call the carrier poor if this count is less than $d/4$. Set $L=n^{1-1/40}$. Conditional on the active outside paths $e'$, the retained subprobability $\tilde\nu_a^{e'}$ on $S_m$ assigns to a free permutation $g$ the probability that the active sweep produces $g$ and keeps at most $L$ poor carriers. Retention does not depend on the incoming free labeling.

At a uniform start set $z$ independent of the fresh switches, the drop probability is at most $n^{-1/40}$ for large $d$. For any full-sweep switch realization, form the meeting graph on the $n$ initial slots, joining two slots whose carriers occupy the two endpoints of the same switch at some stage. The graph is $d$-regular. Given that a particular slot is in the uniform free set, the probability any $k$ specified neighbors of it are all outside is at most $(m/(n-1))^k$ by sampling without replacement. The probability that a slot has more than $3d/4$ outside neighbors is therefore at most
$$ (1+m/(n-1))^d 2^{-3d/4} \le n^{-1/20} $$
for large $d$, using $m/(n-1)<1/2$ and $\log_2(3/2)<7/10$. The expected number of poor carriers is at most $m n^{-1/20}$, and Markov's inequality gives a drop probability of at most $m n^{-1/20}/L\le n^{-1/40}$. The path-averaged loss depends on the active starting layout only through its free set, and averaged over the outside-path law it is at most $n^{-1/40}+\delta_n$ from the end of the unweighted preparation.

The active subprobability has zero sign transform: $\sum_g\tilde\nu_a^{e'}(g)\operatorname{sgn}(g)=0$. The free-free edges are determined by $e'$. If there are none, no trajectory is retained for large $d$ because $m>L$. Otherwise, flip the free coin on one fixed free-free edge at the last stage having any. The carrier counts are unchanged, because no free-free stage follows. Retention is invariant. The endpoint parity changes, because the two carriers exchange their endpoints. This probability-preserving involution cancels the signed sum.

The character estimate used below is the uniform Larsen-Shalev bound ./larsen-shalev-2008.pdf, in the fixed-slack formulation of Keller, Lifshitz and Sheinfeld keller-lifshitz-sheinfeld-2024.pdf.

Lemma (character and fixed points). Fix $0<\delta<1/4$. For all sufficiently large integers $r$, every irreducible character $\chi$ of $S_r$ of degree $D=\chi(1)$, and every $\sigma\in S_r$ with $f$ fixed points satisfy
$$ f\le r^{1-4\delta}\ \Longrightarrow\ \frac{|\chi(\sigma)|}{D}\le D^{-\delta}, $$
$$ \frac{|\chi(\sigma)|}{D}\le D^{-\delta} r^{\delta f}. $$

Proof. Let $a_i$ count the $i$-cycles of $\sigma$ and define nonnegative $e_i$ by
$$ \sum_{i\le s}e_i=\log_r\max\left(1,\sum_{i\le s}i a_i\right), \qquad E(\sigma)=\sum_{i=1}^r\frac{e_i}{i}. $$
The Larsen-Shalev bound is $|\chi(\sigma)|\le D^{E(\sigma)+\varepsilon}$ for each fixed $\varepsilon>0$ and all sufficiently large $r$, uniformly in $\sigma$ and $\chi$. Since $\sum_i e_i=1$ and $e_1=\log_r\max(f,1)$, $E(\sigma)\le(1+\log_r\max(f,1))/2$. With $\varepsilon=\delta$ and $\log_r f\le1-4\delta$, the exponent $E+\delta-1$ is at most $-\delta$, giving the first display.

For the second display, conjugate the $f$ fixed points to the last $f$ symbols and restrict to $S_{r-f}$. By the Young branching rule, at most $r^f$ summands appear, counted with multiplicity, with dimensions $D_j$ summing to $D$. If $r-f$ exceeds a fixed absolute threshold, the restricted permutation has no fixed points, so its own $e_1$ vanishes and $E\le1/2$; the Larsen-Shalev bound with $\varepsilon=1/4$ then bounds the character on a summand of dimension $D_j$ by $D_j^{3/4}$. Holder's inequality with exponents $4/3$ and $4$ gives
$$ |\chi(\sigma)|\le\sum_j D_j^{3/4}\le\left(\sum_j D_j\right)^{3/4}(r^f)^{1/4}=r^{f/4}D^{3/4}. $$
Combined with $|\chi(\sigma)|/D\le1$, this is $|\chi(\sigma)|/D\le\min(1,r^{f/4}D^{-1/4})$. For every $x>0$ and $0<\delta<1/4$, $\min(1,x^{1/4})\le x^{\delta}$, so with $x=r^f/D$ the second display follows. If $r-f$ is below the threshold, $f\ge r/2$ for large $r$, and $D\le\sqrt{r!}$ by the regular character identity while $r^f\ge r^{r/2}\ge\sqrt{r!}$, so $|\chi(\sigma)|/D\le1\le D^{-\delta} r^{\delta f}$.

The reciprocal-square rate of decay of irreducible degrees is the second ingredient.

Lemma (reciprocal degrees). For the irreducible degrees $D_\lambda$ of $S_r$,
$$ \sum_{\lambda:\,D_\lambda>1}D_\lambda^{-2}=o(1)\qquad(r\to\infty). $$

Proof. $D_\lambda$ counts standard Young tableaux of shape $\lambda$ and equals $r!$ divided by the product of its hook lengths, with conventions as in Etingof et al etingof-2011-intro-representation-theory.pdf; this is a special case of the summability theorem of Liebeck and Shalev liebeck-shalev-2004.pdf. If the first row has length $r-j$ with $1\le j\le r/4$, fill its first $j$ boxes with $1,\dots,j$, choose $j$ of the other $r-j$ numbers for the boxes below the first row in one fixed standard order, and put the remaining numbers in increasing order along the first row. Every column below that row lies among its first $j$ columns, so these fillings are standard, giving $D_\lambda\ge\binom{r-j}{j}\ge3^j$. There are at most $2^j$ such shapes, and transposition gives the same bound for a long first column. The contribution from these shapes is at most $2(2/9)^j$, summable, and each fixed-$j$ term tends to zero.

For remaining shapes, apart from the single row and single column, the maximum $\Lambda$ of a row or column length is less than $3r/4$. If $\Lambda\ge r/10$, transpose if needed and retain the first row of length $\Lambda$ along with $t=\lfloor\Lambda/3\rfloor$ boxes below it, deleting corners of the tail. There are at least $t$ tail boxes because $\Lambda<3r/4$, and the same filling construction gives at least $\binom{\Lambda}{t}$ standard tableaux of this subdiagram, each extending to the original by adding corners. If $\Lambdan^{1-\beta}}n^{-f/32}m^{\delta f}\le D^{-\delta}\sum_{f>n^{1-\beta}}n^{-(1/32-\delta)f}=o(1)D^{-\delta}. $$
The estimate is uniform over the outside paths, so
$$ 0\le b_\rho\le 2D^{-1/800} $$
for all sufficiently large $n$. Together with the reciprocal degree sum
$$ \sum_{\rho:\,D>1}D^{-20}=o(1), $$
and the fact that the minimum nontrivial degree grows without bound, absorbing the factor $2$ into $D$ for large $D$ gives
$$ b_\rho\le D^{-1/1600} $$
for all sufficiently large $m$.

The chunk contraction converts the trace bound into an operator bound. Conditional on the preparation outside paths $e$, let $\tilde\nu_b^e$ be the retained joint measure of (free set $z=z(e)$, free permutation $g$ on the complementary slots). The retained measure sits inside the half-deck preparation estimate, so for each fixed $(z,g)$
$$ \mathbb E_e[\mathbf 1_{\{z(e)=z\}}\tilde\nu_b^e(g)]=\min(p(y),u_*)\le u_*, $$
where $u_*$ is the uniform mass of a joint (free set, permutation) configuration, that is, $u_*=m!/n!$. The truncated joint measure, averaged over paths, is thus dominated by the law of uniform $z$ and independent uniform $g$. The expected removed mass is at most $\delta_n$, and the unweighted marginal of $z$ is within $\delta_n$ of uniform.

Conditional on the chunk paths, the composition of preparation and active sweep has transform $F_aF_b$. Averaged over chunk paths from any start, its squared-matrix estimate in positive semidefinite order is
$$ \mathbb E[(F_aF_b)^*(F_aF_b)]=\mathbb E_e[F_b^* A(z(e))F_b]\preceq\mathbb E_e\sum_g\tilde\nu_b^e(g)\rho(g)^* A(z(e))\rho(g)\preceq b_\rho I. $$
For the equality, the next outside paths start fresh and $A(z)$ does not require their particular starting labeling. The first inequality is weighted Cauchy-Schwarz applied to $A^{1/2}F_b$ on each vector with weights of sum at most one. For the second, each conjugated matrix is positive semidefinite, and the pointwise domination bounds its $e$-average by the average against uniform $(z,g)$. For fixed $z$, uniform $g$ conjugation gives $\operatorname{tr}(A(z))I/D$ by Schur's lemma, and averaging the scalar over uniform $z$ gives $b_\rho I$.

Use $J=40000$ chunks. Conditional on the outside paths of all chunks, let $\nu$ be the full probability law of the free-slot permutation and let $\tilde\nu$ be the composition of the subprobabilities above. Then $\tilde\nu\le\nu$ coefficientwise, since every truncation uses only the randomness of its own interval conditional on paths and the layout information there, computing increments on canonical slots regardless of the incoming free permutation. Write $F_{\mathrm{tot}}$ for the transform of $\tilde\nu$, the product of the chunk transforms with later chunks on the left. Applying the chunk contraction given previous paths for the last chunk and iterating gives
$$ \mathbb E[F_{\mathrm{tot}}^*F_{\mathrm{tot}}]\preceq b_\rho^J I $$
from any starting layout. The sign transform vanishes. The mass $M$ of $\tilde\nu$ is the product of the interval masses, and the deficit of the product is at most the sum of deficits, so
$$ \mathbb E[1-M]\le J(2\delta_n+n^{-1/40}). $$

Finite-group Plancherel and Cauchy-Schwarz now give, with $U_m$ uniform on $S_m$,
$$ \tfrac12\mathbb E\|\tilde\nu-MU_m\|_1\le\tfrac12\Big(\sum_{\rho:\,D>1}D^2b_\rho^J\Big)^{1/2}=o(1). $$
Indeed, for a signed measure $v$ of total mass zero, Plancherel gives $\|v\|_1^2\le|S_m|\sum_g|v(g)|^2=\sum_\rho D\|\sum_g v(g)\rho(g)\|_{\mathrm{HS}}^2$. The trivial transform of $\tilde\nu-MU_m$ vanishes, as does the uniform transform at each nontrivial representation, and the matrix bound then gives the display since $J/1600=25$ and $\sum_{\rho:\,D>1}D^{-23}=o(1)$. Adding the removed mass gives
$$ \mathbb E\ d_{\mathrm{TV}}(\nu,U_m)=o(1) $$
uniformly in the outside starting layout.

Couple a chain from any fixed deck with a chain started from uniform. After $s_0$ sweeps the ordered positions of the $m$ designated outside labels can be coupled to agree with probability at least $1-\delta_n$ by the preparation proposition and maximal coupling; complete the two endpoint decks by their respective conditional laws. On agreement, sample common outside paths for the next $J$ chunks from their path law. Conditional on these paths, the final free orders in each deck have distributions obtained using $\nu$ on their possibly different incoming free orders, and each is within $d_{\mathrm{TV}}(\nu,U_m)$ of uniform on the same set of end free orders. Maximally coupling them, the expected failure probability on this continuation is at most $2\mathbb E\,d_{\mathrm{TV}}(\nu,U_m)=o(1)$ on agreement layouts. The total failure probability is at most $\delta_n+o(1)<1/4$ for sufficiently large $d$, giving a bound on the worst-case total variation.

Including the initial preparation gives $400+40000(400+1)=16040400$ sweeps, each costing $d$ physical shuffles. The conditional expectation is over the ordinary law of the outside paths; no assertion is made for a single fixed environment. This completes the proof of the theorem.


Now turn to the reset construction, whose full-deck bound is $171798691968d$ physical shuffles. The route is independent of the first: it extracts an exact uniform component from a long reset block, then computes a return probability for a central relative-permutation increment between two coupled copies.

Fix $0<\rho\le1$, take $\rho=2^{-20}$, and set $N=n=2^d$ throughout. Distinguish $k=\lceil\rho N\rceil$ nonhole labels and $h=N-k$ hole labels.

For an observed hole path, the conditional position of a single hole is determined by the mass evolution rule: at a two-hole pair the two outgoing masses are both the average of the incoming ones, and at a mixed pair the hole mass is transported to the outgoing hole. Total mass is preserved and uniform mass $1/h$ per hole follows the same rule. A signed difference from uniform (supported on the holes, total mass zero) has squared Euclidean norm non-increasing at every update. The forward mass calculation through a layer uses only the observed paths up to that time, since unobserved switch coins remain independent fair even after conditioning on the future part.

Lemma (two-sweep mass contraction). Fix $0<\rho\le1$. For all sufficiently large $d$ depending only on $\rho$, any deterministic placement of $h\ge\rho N$ holes and any signed mass vector supported on the holes with sum zero has expected squared norm after two sweeps at most $N^{-\rho/16}L$, where $L$ is the initial squared norm. The estimate also holds conditionally on the past when the two sweeps begin.

Proof. Consider a single sweep, split into its first $r=\lfloor d/2\rfloor$ layers and its last $d-r$ layers. Conditional on the switch coins of the first $r$ layers, the evolutions inside different level-$r$ blocks (fixed by bits above $r$) proceed independently during layers above $r$, because a switch above coordinate $r$ never enters a lower block. Within each level-$r$ block $B$, the number $H_B'$ of holes at the end of the sweep is a sum of independent Bernoulli variables with mean $h_B'=h/2^{d-r}$, and Chernoff gives
$$ \mathbb P\big(|H_B'-h_B'|\ge\tfrac{\rho}{4}2^r\big)\le 2e^{-\rho^2 2^r/64}. $$
On the complementary event $D$ of the intersection over the $2^{d-r}$ level-$r$ blocks, holes remain roughly proportional across blocks in the second sweep, and the layer updates act by pair averaging.

Within any level-$i$ block $B$ in the second sweep, write $u=H_B/|B|$ and $m=M_B/|B|$ for the first moments of indicator and signed mass, $q$ for the second moment of mass, and $a=m/u$, $v=q-ua^2$ when $u>0$. Cauchy-Schwarz with support on the holes gives $v\ge0$, and rearrangement gives
$$ u=\tfrac{u_1+u_2}{2},\quad m=\tfrac{m_1+m_2}{2},\quad q=\tfrac{q_1+q_2}{2}-\tfrac{q_1u_2+q_2u_1-2m_1m_2}{4}, $$
and
$$ v=\tfrac12[(1-u_2/2)v_1+(1-u_1/2)v_2]+(1-u)J_B,\qquad J_B=\tfrac12(u_1a_1^2+u_2a_2^2)-ua^2\ge0. $$

Weighting by block sizes, the sum of $|B|v_B$ at level $i>r$ is at most $1-\rho/4$ times that at level $i-1$, plus the sum of $|B|J_B$ at level $i$. Each $|B|J_B$ equals the sum over the two children minus the parent of the quantity $|B|ua^2=M_B^2/H_B$. Thus the sum of $|B|J_B$ above level $r$ telescopes and is bounded by $\sum_{B\ \mathrm{level}\ r}M_B^2/H_B$. Cauchy-Schwarz gives $\sum_BM_B^2/H_B\le L$, and at the root $v=q$ because total mass is zero. Restricting to the first sweep's output, the expected squared norm on $D$ is at most
$$ (1-\rho/4)^{d-r}L+\sum_{B\ \mathrm{level}\ r}\frac{(M_B')^2}{H_B'}, $$
where $M_B'$ is the signed mass in $B$ after the first $r$ layers and $H_B'$ is the hole count there. Conditionally on the level-$r$ output, the mean of $|M_B'|^2$ is at most $L/2^{d-r}$, and on $D$ we have $H_B'\ge(\rho/2)2^r$, so the residual is at most $2L/(\rho 2^r)$. Combining with the $D^c$ probability $\le 2^{d-r}e^{-\rho^2 2^r/64}$,
$$ \mathbb E[\|\text{output}\|^2]\le\Big[(1-\rho/4)^{d-r}+\frac{2}{\rho 2^r}+2^{d-r}e^{-\rho^2 2^r/64}\Big]L\le N^{-\rho/16}L $$
for $d$ sufficiently large. The estimate holds conditionally on the past.

Proposition (partial mixing at fixed omitted fraction). Fix $0<\rho\le1$ and $s=\lceil320/\rho\rceil$. For all sufficiently large $d$ depending only on $\rho$, after $2s$ sweeps the ordered positions of any $b\le(1-\rho)N$ distinct labels are within $\varepsilon_N=N^{-8}$ in total variation of the uniform ordered injection, from any deterministic start. The same assertion holds for sweeps in reverse order $d,\dots,1$.

Proof. The mass contraction lemma iterated over $s$ pairs of sweeps gives an expected squared-norm bound of $N^{-s\rho/16}L=N^{-20}L$, since $s\rho/16\ge20$. For an ordered tuple with labels $1,\dots,b$, condition label $i$ on the paths of labels $1,\dots,i-1$, leaving at least $\rho N$ holes. The initial signed mass is the point mass at $i$'s slot minus uniform mass on the holes, with squared norm at most one. The final signed mass is the endpoint probability difference from uniform on positions not occupied by the earlier labels. Cauchy-Schwarz bounds its expected $L^1$ norm by $\sqrt{N}N^{-10}/2$. Conditioning on the earlier labels' endpoints rather than on paths cannot increase the averaged bound. Summing over $i$ and telescoping between the actual conditional kernels of an initial segment and the uniform sequential kernels bounds the total-variation distance by $\varepsilon_N$. The proof only used the order of the coordinates as an indexing, so it applies to reversed order as well.

Corollary (forward reset minorization). Let $K$ be the kernel of the $2s$ forward sweeps in the partial mixing proposition, on the ordered injection space $\Omega$ of $b$ labels. Then $K^2(x,y)\ge p_0/|\Omega|$ for $p_0=1-2\varepsilon_N$.

Proof. The kernel $K$ is doubly stochastic. Its transpose is the kernel of the inverse permutation law, sweeping in reversed order, so the partial mixing proposition applies row-wise to both $K$ and $K^*$. Put $w=1/|\Omega|$ and truncate each factor above by $w$: write $K(x,z)=w-a_z$ and $K^*(y,z)=w-b_z$ with $a_z,b_z\ge0$, and note that $\sum_za_z\le\varepsilon_N$, $\sum_zb_z\le\varepsilon_N$. In the inner product $K^2(x,y)=\sum_zK(x,z)K^*(y,z)$, the product of truncated factors is $w^2-w(a_z+b_z)+a_zb_z\ge w^2-w(a_z+b_z)$. Summing gives $K^2(x,y)\ge w-w(\varepsilon_N+\varepsilon_N)=p_0/|\Omega|$.

To lift the marginal bound into a conditional statement, fix $k=\rho N$ nonhole labels and let $H$ denote the set of $h=N-k$ hole labels. The role of the labels is used only for the comparison below. Run $l=128$ blocks, each consisting of a reset of $4s$ sweeps followed by a single mixing sweep, all sweeps being actual random shuffles. Write $X$ for the process taking labels to positions. Reveal an environment $\mathcal E$ recording all reset coins and, during the mixing sweep of each block, the switches touched by nonhole trajectories together with their values. The environment determines all nonhole paths; conditionally on it, the unrevealed two-hole switches in the mixing sweeps are independent and fair.

Given $\mathcal E$, generate $Y$ independently of $X$ with the same conditional law by sharing the reset and touched switch values and redrawing the two-hole switches. The two copies have the same nonholes in the same positions, and can be constructed jointly in chronological order using fresh coins for $X$ and independent coins for the redraws. Write $p_{\mathcal E}$ for the conditional final law of the hole assignment, and $u_{\mathcal E}$ for uniform measure on the $h!$ assignments.

Proposition (uniformity conditional on the reset environment). With $\rho=2^{-20}$, $s=\lceil320/\rho\rceil$ and $l=128$ blocks,
$$ \mathbb E_{\mathcal E}\|p_{\mathcal E}-u_{\mathcal E}\|_{\mathrm{TV}}\longrightarrow 0 \qquad(d\to\infty), $$
uniformly over deterministic starting decks.

Proof. The relative permutation $X^{-1}Y$ acts on the hole set $H$, starts at the identity, and is unchanged during a reset. In a layer of a mixing sweep it is multiplied on the left by a product of relative transpositions: transpose the two incident $X$-labels at each two-hole switch where the $Y$-switch value differs from the $X$-switch value. If $T_X,T_Y$ act on positions and $X,Y$ are pre-layer values, the new relative permutation is $(X^{-1}T_X^{-1}T_YX)\,X^{-1}Y$. Given the $X$ switches and paths, the relative toggles are independently fair. Write $Q$ for the multiplier over one mixing sweep; it depends only on the $X$ hole injection at the sweep start and on the switches (including redraws) within that sweep, and not on the prior relative permutation.

Mark two events for $X$ only; the marks do not alter its run. At each reset mark an acceptance whose conditional probability is $p_0/(|\Omega|K^2(x,y))$, where $K$ is the reset kernel, $x$ is the start, and $y$ is the sampled endpoint of the $h$ ordered hole labels. The reset minorization gives $K^2(x,y)\ge p_0/|\Omega|$, so the acceptance probability is at most one. Conditional on the past, the injection of the $h$ ordered hole labels just after the accepted reset, jointly with acceptance, has probability $p_0/|\Omega|$ for each injection. This is the splitting mechanism of Nummelin. The statement holds also when the past includes the other copy in the chronological construction, since the relative permutation is unchanged during the reset.

For the second mark, take a mixing sweep with $X$'s hole injection uniform at its start, as upon acceptance. Form the graph on all positions in which two positions are joined when their $X$-paths share a switch. The graph is simple and $d$-regular: after two paths meet they differ in that updated bit, which does not change again during the sweep, so they cannot meet at any later coordinate. The graph depends only on the fresh $X$ coins and is independent of the hole injection; given the graph, the nonhole labels occupy a uniform $k$-subset of vertices. The probability that some vertex has at least $\lceil d/2\rceil$ nonhole neighbors is at most $N2^d\rho^{d/2}=N^{-8}$ by a union bound and sampling without replacement. Mark the mixing sweep good on the complementary event; every hole label then has at least $d/2$ two-hole switches along its path. Write $\nu$ on the symmetric group of $H$ for the subprobability law of $Q$ under goodness when the $X$ hole injection is uniform at the sweep start. Its mass is $q\ge1-N^{-8}$. The increment and goodness depend on no nonhole identities, so $\nu$ is central. After an accepted reset the law of $(Q,\text{good})$ conditional on the past is exactly $p_0\nu$: writing $\mathcal F$ for the past before the reset,
$$ \Pr(\text{accept},\text{good},Q=g\mid\mathcal F)=p_0\nu(g). $$
Let $G_X$ denote the event that all accepts and all good marks occur for $X$, and $S$ the final relative permutation. Then
$$ \Pr(G_X)=(p_0q)^l,\qquad \Pr(S=\mathrm{id},G_X)=p_0^l\,\nu^{*l}(\mathrm{id}). $$
Indeed, the placement of $X$'s holes after an accepted reset is uniform and independent of the past, regardless of the current relative permutation, and the relative coin differences in the next sweep come from the independent redraws and give the multiplier law just described, allowing iteration with convolution.

Two facts on $\nu$ control its convolution powers. In a good mixing sweep, the sign character of $\nu$ is fair, since the sweep contains a two-hole switch and the relative toggles are independently fair. And for any $A\subseteq H$,
$$ \nu\{Q:Q\text{ fixes }A\text{ pointwise}\}\le 2^{-d|A|/4}\le h^{-|A|/4}. $$
For this estimate, imagine using the switches for $Y$ but starting the mixing sweep at the very same deck as $X$. The final relative permutation is $Q$. Within one sweep a path with given start and end is unique, so fixation of a label requires its two paths to agree at every switch on its $X$-path. In a good sweep at least $d|A|/4$ distinct two-hole switch coins are involved on those paths, counting any switch at most twice as path incidence, and their agreement probability gives the bound.

Lemma (return estimate). For the central sublaw $\nu$ on $S_H$ and $l=128$,
$$ h!\,\nu^{*l}(\mathrm{id})\le q^l+o(1). $$

Proof. Apply the character and fixed-point lemma with $r=h$ and $\delta=1/32$, and the reciprocal-degree lemma with $r=h$. For $\sigma\in S_H$ let $F(\sigma)$ be the number of fixed points and write $\theta_\lambda=\sum_\sigma\nu(\sigma)\chi_\lambda(\sigma)/d_\lambda$ with $d_\lambda$ the irreducible degree. For $F\le h^{7/8}$, the character lemma with $\delta=1/32$ gives $|\chi_\lambda(\sigma)|/d_\lambda\le d_\lambda^{-1/32}$ for large $h$. For $f>h^{7/8}$, the pointwise fixation bound gives $\nu(F=f)\le\binom{h}{f}h^{-f/4}\le h^{-f/10}$, using $\binom{h}{f}\le(eh/f)^f$. At a fully fixed $\sigma$ the all-fixed-points bound of the character lemma gives $|\chi_\lambda(\sigma)|/d_\lambda\le d_\lambda^{-1/32}h^{f/32}$. The tail $\sum_{f>h^{7/8}}h^{-f(1/10-1/32)}\le1$ for large $h$, and the conditional $\mathbb E_\nu$ over character values therefore satisfies $|\theta_\lambda|\le2d_\lambda^{-1/32}$.

By centrality each averaged representation matrix is scalar by Schur's lemma, with scalar $\theta_\lambda$. The regular representation trace for the convolution gives
$$ h!\,\nu^{*l}(\mathrm{id})=\sum_\lambda d_\lambda^2\theta_\lambda^l. $$
The trivial term is $q^l$, and the sign term vanishes. With $l=128$, the sum of absolute values of the other terms is at most $2^l\sum_{\lambda:D_\lambda>1}d_\lambda^{-l/32}\le2^l\sum_{\lambda:D_\lambda>1}d_\lambda^{-2}$, which is $o(1)$ by the reciprocal-degree lemma. This proves the return estimate.

Write $p_{\mathcal E}^G$ for the subprobability of $p_{\mathcal E}$ that includes the requirement $G_X$, and for the conditionally independent copy $Y$ define $G_Y$ by the same acceptance and goodness requirements with independent auxiliary randomness. The triangle inequality with the subprobabilities and Cauchy-Schwarz give
$$ \mathbb E_{\mathcal E}\|p_{\mathcal E}-u_{\mathcal E}\|_{\mathrm{TV}}\le\tfrac12\Pr(G_X^c)+\tfrac12\sqrt{h!\,\Pr(S=\mathrm{id},G_X,G_Y)-2\Pr(G_X)+1}. $$
Indeed, $p_{\mathcal E}-p_{\mathcal E}^G$ is nonnegative with expected mass $\Pr(G_X^c)$, and the expression inside the square root equals $\mathbb E_{\mathcal E}[h!\sum_g(p_{\mathcal E}^G(g)-1/h!)^2]$. This uses the two conditionally independent copies with their separate marks, with assignment agreement represented by $S=\mathrm{id}$. Dropping $G_Y$ from the positive term and applying the convolution formulas with the return estimate bounds the expression by $1-(p_0q)^l+o(1)=o(1)$, and likewise $\Pr(G_X^c)=o(1)$. The truncation by good subprobabilities costs only $o(1)$ in total variation. This proves the uniformity conditional on the reset environment.

For the full-deck law, note first that the nonhole marginal is close to uniform unconditionally. The first $2s$ sweeps already have the partial mixing estimate for the $k$ nonhole labels, and subsequent independent switches in the actual run preserve the uniform marginal kernel-wise, so they cannot increase its total-variation distance from uniform. The nonhole marginal is thus within $\varepsilon_N$ of uniform on their end positions. The distribution obtained by assigning the $h$ hole labels uniformly given the environment has these nonhole end positions and uniform assignment on the complement, so it is within $\varepsilon_N$ of uniform on the whole deck. By the conditional bound, the actual end distribution differs from this distribution by $o(1)$ in total variation, uniformly in the initial deck. The physical time is
$$ 128(4s+1)d=128(4\cdot320\cdot2^{20}+1)d=171798691968d $$
complete shuffles. The support lower bound from the first route gives $t_{\mathrm{mix}}\ge d$ for all sufficiently large $d$ as well.

Trajectory overlays provide a third mechanism, giving full-deck mixing in $33030144d$ physical shuffles. The base shuffle runs as usual, but on top of it independent fair switches are added along selected trajectories. Their placement is predictable from the base coins, so the actual law of switch arrays is unchanged; the extra switches then mix chosen groups of indices, on average over the base, without disturbing the physical shuffle law.

Use $V=\mathbb F_2^d$ with later permutations acting on the left. Fix $K=8$ and let $q=n/K=n/8$.

Lemma (preparing a group of base indices). After $20d$ layers, the ordered positions of any $q$ specified cards in the base shuffle have total-variation distance $o(1)$ from uniform ordered distinct positions. The estimate is uniform in their starting positions and in the starting cyclic phase.

Proof. Introduce a randomized linear change of frame, used only for proving this estimate. Restart notation at layer $1$ of the interval, with cyclically ordered directions $i_1,i_2,\ldots$, and represent the layer permutation as $L_t\widetilde T_t$, where $\widetilde T_t$ is an independent ordinary fair layer along $e_{i_t}$ and
$$ L_tx=x+\ell_t(x)e_{i_t} $$
for independent random linear forms $\ell_t$ with $\ell_t(e_{i_t})=0$, uniform under that constraint and independent of the $\widetilde T_t$. Each $L_t$ consists of switches on the same matching, so this factorization has the required shuffle law. Set $A_t=L_t\cdots L_1$ and $A_0=I$, and map each location through $A_t^{-1}$. In the changed frame, the layer dynamics conditional on the $L_s$ are independent arrays of fair switches in directions
$$ v_t=A_{t-1}^{-1}e_{i_t}, $$
by conjugating $\widetilde T_t$; their conditional laws depend only on those directions.

For $t>d$, conditional on prior directions, $v_t$ is uniform outside the hyperplane spanned by $v_{t-d+1},\ldots,v_{t-1}$. Indeed, the columns of the inverse transform evolve by $A_s^{-1}e_j=A_{s-1}^{-1}e_j+\ell_s(e_j)v_s$, using $L_s^{-1}=L_s$, and
$$ v_t=v_{t-d}+\sum_{s=t-d+1}^{t-1}\ell_s(e_{i_t})v_s. $$
The coefficients $\ell_s(e_{i_t})$ for $s\in[t-d+1,t-1]$ are independent fair bits, independent of all $v_p$ with $p