Truncating the preparation interval

Given the chunk’s starting layout with free set \(z_0\), consider the ordered endpoint injection \(y\) at the end of the preparation interval of fictitious free labels placed canonically in the free slots at its start. Let \(p(y)\) be its probability without conditioning on paths, from this start. Equivalently \(y\) encodes the endpoint free set \(z\) and the preparation permutation \(g\) on the canonical indices. Write \(u_*=(\binom{n}{m}m!)^{-1}\) for the uniform injection probability. Weight the preparation outcomes by \(\min(1,u_*/p(y))\) (use 1 at \(p(y)=0\)), using \(y\) of this interval’s canonical increment, not the endpoints of labels carried in from prior chunks. Denote the resulting subprobability on \(g\) conditional on preparation outside paths \(e\) by \(\widetilde\nu_b^e\). Since \(z=z(e)\) is determined by those paths, \[ \mathbb E_e\big[{\bf 1}_{\{z(e)=z\}}\widetilde\nu_b^e(g)\big] =\min(p(y),u_*)\le u_* \qquad\text{for each }(z,g). \tag{6}\] Thus the retained joint measure averaged over paths is dominated by the law of uniform \(z\) and independent uniform \(g\). By (5) the expected removed mass is at most \(\delta_n\). Also the unweighted marginal of \(z\) is within \(\delta_n\) of uniform.

Active truncation

For each free carrier (card considered from its slot at the start of the active sweep), count the stages of this sweep at which it is on an edge with two free slots. Call the carrier poor if this count is less than \(d/4\). Retain the active trajectory if at most \[L=n^{1-1/40}\] free carriers are poor, dropping it otherwise. This criterion does not depend on their incoming labeling. With active outside paths \(e'\), write \(\widetilde\nu_a^{e'}\) for the conditional subprobability law of the active permutation.

At a uniform start set \(z\) independent of the fresh switches, the probability of dropping is at most \(n^{-1/40}\) for large \(d\). In fact for any full sweep switch realization form the meeting graph on the \(n\) initial slots, joining two whose carriers occupy the two slots of the same switch at some stage. It has \(d\) distinct neighbors per slot: after such a meeting at stage \(i\) the two differ in bit \(i\) and keep differing there through the sweep, preventing any later meeting in it. The graph does not use \(z\). Given a particular slot is in the uniform free set, for its \(d\) neighbors the probability any \(k\) specified ones are all outside is at most \((m/(n-1))^k\) (sampling without replacement). As in (2), the probability of having more than \(3d/4\) outside neighbors is at most \[(1+m/(n-1))^d 2^{-3d/4}\le n^{-1/20}\] for large \(d\) (the limiting \(\log_2(3/2)<7/10\)). This bounds the poor probability for that free slot. The expected number poor is thus at most \(m n^{-1/20}\); apply Markov’s inequality to obtain the dropping bound. Generating full switches here computes exactly the expected removed conditional mass when averaging over the outside paths and the free switches. This path-averaged loss as a function of the active starting layout depends only on its free set (relabeling the outside has no effect). Thus from the end of the unweighted preparation interval its expectation is at most \(n^{-1/40}+\delta_n\), for any start of the chunk.

The active subprobability has zero sign transform: \[\sum_g \widetilde\nu_a^{e'}(g)\operatorname{sgn}(g)=0.\] The free-free edge sets are determined by \(e'\). If there are none, no trajectory is retained for large \(d\) (\(m>L\)). Otherwise flip the free coin on one fixed free-free edge at the last stage having any. The counts for the carriers are unchanged (no further free-free stages), retention is invariant, and this probability-preserving involution changes the endpoint parity by exchanging the endpoints of the two carriers there.

Trace estimate for an active interval

Use unitary complex irreducible representations \(\rho\) of \(S_m\), writing the transform of a measure as \(F=\sum_g \nu(g)\rho(g)\). Denote by \(D\) the dimension and \(\chi\) the (unnormalized) character. We use the ordinary trace, with \(\|B\|_{\mathrm{HS}}^2=\operatorname{tr}(B^*B)\). Write \(F_a\) for the transform of \(\widetilde\nu_a^{e'}\), and put \[A(z)=\mathbb E_{e'}[F_a^*F_a\mid\text{active start with free set } z], \qquad b_\rho=\mathbb E_{z\ {\rm uniform}}\frac{\operatorname{tr} A(z)}{D}.\] The expectation defining \(A(z)\) is the same for any outside labeling of the other slots: such a relabeling just bijects outside paths with the same constraints on switch moves and the same probabilities and free kernels. For the sign representation \(F_a=0\). We treat \(D>1\) next. The representation-theoretic background used here is recalled in [21, 3].

For the trace, conditional on \(e'\), take two independently generated free switch realizations \(X,Y\); letting \(g_X,g_Y\) be the resulting permutations, expansion gives \(\operatorname{tr}(F_a^*F_a)\) equal to the conditional average of \(\chi(g_X^{-1}g_Y)\) times the indicators that both are retained. Let \(f\) be the number of fixed points of \(g_X^{-1}g_Y\). Given a retained \(X\), for any \(a\) specified free starting indices to be fixed, their carriers must have the same paths in \(Y\) as in \(X\), by single-sweep path uniqueness from endpoints. At least \(a-L\) of them are not poor in \(X\), so they jointly visit at least \(d(a-L)/8\) distinct free-free switches (at most two carriers per switch). The coins there in \(Y\) would all have to match, and they are independent fair coins conditional on \(e'\) and \(X\). By a union bound, with \(\beta=1/100\) and for integers \(n^{1-\beta}\le a\le m\), \[ \mathbb P(f\ge a,\ X,Y\text{ retained}\mid e') \le \binom{m}{a} 2^{-d(a-L)/8} \le n^{-a/32} \tag{7}\] for large \(d\), since \(L\le a/2\) and \((em/a)^a\le n^{2\beta a}\) (here \(e\) in \(em/a\) is the base of natural logarithms).

The endpoint-agreement estimate must now be converted into a character estimate. We record the two bounds used here and in the reset and overlay constructions.

Apply the lemma with \(r=m\) and \(\delta=\beta/8=1/800\). For large \(n\), \(n^{1-\beta}\le m^{1-4\delta}\), so pairs with \(f\le n^{1-\beta}\) contribute at most \(D^{-\delta}\) to the normalized trace. For larger integer \(f\), use (7) and (9); their total contribution is at most \[D^{-\delta}\sum_{f>n^{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 holds uniformly over the outside paths. In particular \[ 0\le b_\rho\le 2D^{-1/800} \qquad\text{for all sufficiently large }n. \tag{10}\]

To sum the trace estimates, we also need a bound on small representation degrees. The following elementary argument proves the reciprocal-square case of the more general summability theorem of Liebeck and Shalev [8]. This case suffices for all the sums below.

In particular, \[ \sum_{\rho:\,D>1}D^{-20}=o(1), \tag{12}\] and the minimum nontrivial degree \(D>1\) tends to infinity. Absorbing the factor \(2\) in (10), we may therefore use \(b_\rho\le D^{-1/1600}\) for all sufficiently large \(m\).

From traces to contraction over chunks

The active interval has supplied an averaged normalized trace. Its matrix need not be central, and matrices from consecutive intervals need not commute. We now use preparation domination to upgrade the trace bound to a positive-operator inequality, uniformly in the incoming outside layout. This is the step that makes the conditional law of the entire assignment accessible.

Let \(F_b\) be the transform of the preparation subprobability conditional on paths \(e\). Conditional on the chunk paths the chunk subprobability (composing preparation then active) has transform \(F_a F_b\). Averaging over chunk paths from any start, its squared-matrix estimate in positive semidefinite order is \[ \begin{aligned} \mathbb E[(F_a F_b)^*(F_a F_b)] &=\mathbb E_e[F_b^* A(z(e)) F_b]\\ &\preceq \mathbb E_e\sum_g\widetilde\nu_b^e(g)\rho(g)^* A(z(e))\rho(g) \preceq b_\rho I. \end{aligned} \tag{13}\] 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 1. For the second, each conjugated matrix is positive semidefinite, so use (6) to bound by the average with uniform \(z,g\). For each \(z\), the uniform \(g\) conjugation gives \(\operatorname{tr}(A(z))I/D\) by Schur’s lemma.

Use \(J=40000\) chunks. Conditional on their outside paths let \(\nu\) be the full probability law of the overall free-slot permutation and let \(\widetilde\nu\) be the composition of the subprobabilities above. Then \(\widetilde\nu\le\nu\) coefficientwise. Indeed all truncations use only the randomness of their respective interval conditional on paths and the layout information there, computing increments on canonical slots regardless of previous free permutations. Write \(F_{\rm tot}\) for the transform of \(\widetilde\nu\), the product of the chunk transforms (latest on the left). Applying (13) given previous paths for the last chunk and iterating gives \[\mathbb E[F_{\rm tot}^*F_{\rm tot}]\preceq b_\rho^J I\] from any starting layout: the preceding product is determined by the preceding outside paths and the bound (13) is uniform conditional on them. The sign transform is zero. The mass \(M\) of \(\widetilde\nu\) is the product of the interval masses. By bounding the deficit of the product by the sum of deficits, \[\mathbb E[1-M]\le J(2\delta_n+n^{-1/40}).\] Here we average the deficits under the ordinary outside path law; the preparation and active loss bounds hold given the outside layout starting each chunk, with the unweighted preparation path law for bounding the active loss.

Finite-group Plancherel and Cauchy-Schwarz now give, with \(U_m\) uniform on \(S_m\), \[\frac12\mathbb E\|\widetilde\nu-MU_m\|_1 \le \frac12\left(\sum_{\rho:\,D>1}D^2 b_\rho^J\right)^{1/2}=o(1).\] Indeed for the difference \(v\) we have \(\|v\|_1^2\le |S_m|\sum_g |v(g)|^2=\sum_\rho D\|\sum_g v(g)\rho(g)\|_{\rm HS}^2\) (the equality also follows directly by the regular character identity). The trivial transform of the difference vanishes, and at nontrivial representations the uniform transform vanishes. Take expectations using the matrix bound (and bound the mean norm by its root mean square), then use (12) since \(J/1600=25\). Restoring the missing nonnegative measure, we conclude \[ \mathbb E\ d_{\rm TV}(\nu,U_m)=o(1) \tag{14}\] uniformly in the outside starting layout: add at most \(\mathbb E[1-M]\) to the centered subprobability bound by comparing \(\nu-\widetilde\nu\) to \((1-M)U_m\). Here \(\nu\) itself is conditional on all the outside paths.

Completing the first route

Couple a chain from any fixed deck and one started uniform (uniformity is preserved by the independent random positional permutations). After \(s_0\) sweeps we can couple the ordered positions of the \(m\) designated outside labels to agree with probability at least \(1-\delta_n\), by (5) 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. Each is within \(d_{\rm TV}(\nu,U_m)\) of uniform on the same set of end free orders (permuting from any fixed incoming order). Maximally couple them, so the expected failure probability on this continuation is at most \(2\mathbb E\,d_{\rm TV}(\nu,U_m)=o(1)\) by (14), uniformly on agreement layouts. This couples endpoints with the correct marginals by path conditioning (on initial disagreement one can just continue independently). The total failure probability is at most \(\delta_n+o(1)<1/4\) for sufficiently large \(d\), bounding the worst-case total variation.

The conditional assertion of Theorem 1 was established in (14), over \(40000(400+1)=16040000\) sweeps. The coupling proves its full-deck conclusion: 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; neither the argument nor its conclusion asserts a bound for each fixed environment.

Partial mixing and forward minorization

The reset needs an ordered marginal estimate for every fixed positive omitted fraction, rather than only for a half-deck. We prove it through a two-sweep signed-mass estimate, then use the same marginal bound in the reverse coordinate order to minorize the forward reset kernel.

Fix some observed labels and let \(h\) be the number of remaining labels. Lemma 2 gives independent fair coins on the unobserved switches. To describe the conditional distribution for the position of a single particular hole label, one can evolve probability masses on the holes: at a pair of two holes the outgoing masses are both the average of the incoming ones, and at a mixed pair the hole mass goes to the outgoing hole. Which positions are holes at all the times is known from the observation. Although this description is conditional on the full observation, the forward calculation of mass through any layer only uses the observed paths up to then, as unobserved switches are left independent even when conditioning on the future part too. Uniform mass \(1/h\) per hole follows the same rule. We will bound the expected squared Euclidean norm of signed masses (mass zero off the holes, total mass zero) evolving by these rules, taking expectation when the trajectories are random, not conditioned. This is an adapted evolution in the switch process; at a mixed pair the placement of the outgoing mass uses the fresh fair switch coin. At every update the squared norm is non-increasing.

Comparison conditional on a switch environment

We have proved uniform marginal control in both coordinate orders and converted it into pointwise minorization. The reverse-order estimate was used to control columns of the forward kernel; the actual reset is still a product of forward sweeps. We next exploit the minorization without changing that actual run.

From now on let \(\rho=2^{-20}\), with \(d\) sufficiently large, and fix a set of \(k=\rho N\) nonhole labels; let \(H\) be the set of \(h=N-k\) hole labels. These roles of the labels are for the comparison only. Run \(l=128\) blocks, each consisting of a reset of \(4s\) sweeps followed by a single mixing sweep (all sweeps are actual random shuffles). Write \(X\) for the process as permutations taking labels to positions.

Define an environment by revealing all the reset coins and, during the single mixing sweep of each block, revealing the switches touched by the nonhole trajectories and their values. The environment determines all nonhole paths. Conditional on it, the unrevealed switches during mixing sweeps (the two-hole switches) are independent and fair, by the fixed-values observation as for trajectories earlier: every completion has the same nonhole paths, using also the fixed reset values. We may generate \(Y\) independently of \(X\) conditional on the environment with the same conditional law, by sharing the reset and touched switch values and independently redrawing the two-hole switches during mixing sweeps. The copies have the same nonholes in the same positions. Unconditionally this joint generation can be done chronologically, generating fresh coins for \(X\) and using independent coins for the redraws (the switches to be redrawn in a layer are known upon entering it).

For this environment \(\mathcal E\), let \(p_{\mathcal E}\) be the final law of the hole assignment conditional on \(\mathcal E\), a bijection from the \(h\) hole labels to their available endpoint positions, and let \(u_{\mathcal E}\) be uniform on those \(h!\) assignments.

Full-deck mixing

The support obstruction was proved in Section 2; in particular it implies the lower bound \(t_{\mathrm{mix}}\ge d\) for all sufficiently large \(d\).

Mixing a fraction of the base indices

Fix \(K=8\), and let \(q=n/K\); throughout this section only sufficiently large \(d\) need be considered.

An overlay on the base trajectories

The marginal estimate has prepared the starting positions of the indices that will receive extra switches. We now define those switches so that their conditional law can be studied separately while the resulting physical process remains an ordinary Thorp shuffle.

Call the initial position names of the base shuffle its indices, in \(V\). Just before a layer, the matching of locations induces a matching of the indices via their base positions at that time. We can put extra switches on selected edges of this index matching chosen from the pre-layer base data. In our overlay construction we supply these switches from fresh arrays of independent fair coins independent of the base arrays. Form the actual layer coins on the location pairs by xoring the corresponding extra bits (0 where absent) with the base bits. The actual shuffle has the ordinary law: conditional on the past and the extra bits for a layer, the base bits in that layer still have their independent uniform law, since the selection and extra bits do not use the current base coins. So the resulting coin array has the independent fair law at every layer given the past. If the base permutation (indices to current positions) is \(B\), the actual permutation is \(B D\), with \(D\) the overlay permutation on indices, initialized to the identity. At each layer \(D\) is left-multiplied by the extra switches in the pre-layer index matching and \(B\) is then updated by the base switches on locations. This gives exactly the xor dynamics just specified.

For a fixed group \(A\subseteq V\) of \(q\) indices, we call the following procedure a call on \(A\).

Given the base trajectories, the left multiplier is a product of independent random permutations on \(A\), with laws determined, phase by phase, by the segments of ordered base trajectories of \(A\) in the active layers (including their positions just before the active layers). These laws describe the multipliers irrespective of the incoming overlay. For analyzing the expected conditional distance we can use an ideal experiment with independent such segments, each started from uniform ordered distinct locations of the indices in \(A\) and run with ordinary base layers. Indeed the joint law of the actual segments, even given data before the call, is within \(o(1)\) in total variation of this ideal segment law for constant \(k\). This follows by Lemma 13 in each \(20d\)-layer preparation interval, conditional on earlier base history, followed by the same ordered-location transition dynamics on the active layers. These dynamics do not depend on the placements of other indices. Equivalently one can couple each new segment start to a fresh uniform one and use matched segment dynamics when the coupling succeeds, with failure probability bounded by the sum of the partial mixing errors. Since the conditional distance is a bounded function of the segments, it suffices to bound its expectation in the ideal experiment.

It remains to prove the conditional group estimate for these independent ideal segments, which we do next.

Estimate for an ideal active segment

Let \(E\) denote an ideal segment environment, i.e. the ordered placement and \(d\)-layer base trajectories of \(A\) in the experiment above. Conditional on \(E\), denote by \(\mu_E\) the law of the overlay multiplier on \(A\) generated by the internal extra switches. We visualize its generation with labels starting at the corresponding indices of \(A\) (identity overlay at the start for describing this multiplier); in locations, these labels follow the actual switched paths. An internal encounter of such a label is when it is on a location pair having two indices in \(A\). The set of locations occupied by the labels from \(A\) is precisely the base location set of \(A\) throughout. Thus in the actual switch dynamics an internal encounter is pairing with another label from \(A\).

Fix constants \[h=1/32,\qquad \eta=1/4096,\qquad \delta=\eta/4 .\] Call the extra-switch outcome good if at most \(q^{1-\eta}/2\) of its labels have fewer than \(h d\) internal encounters. Denote by \(\mu'_E\) the subprobability obtained from \(\mu_E\) by counting only switch outcomes that are good (there is no renormalization).

The mass discarded has expectation \(o(1)\). For every fixed starting placement, averaging over the base and extra switches gives the same product law of independent fair actual switch arrays, by predictability and the base-coin xor argument. Hence the actual location-switch array is independent of the uniformly sampled starting placement of \(A\), even though the choice of extra edges depends on that placement. In \(d\) consecutive directions, any two actual labels (considering labels on all the start sites) can be paired at most once. They could pair only at the direction of the last, in layer order, of the bits on which their start sites differed. Before that direction such an unchanged different bit would preclude pairing on another direction. Afterwards all still unprocessed bits are equal, so pairing in an unprocessed direction (requiring a difference there) is impossible. Each label therefore has \(d\) distinct partners. Conditional on a specified active label’s start position and on the actual location switch arrays, its partners’ start positions are determined; the other \(q-1\) active start positions are a uniform subset among the \(n-1\) others. Its number of encounters is hypergeometric from sampling \(d\) sites out of \(n-1\) with \(q-1\) active. This law differs from a binomial with parameters \(d,(q-1)/(n-1)\) in total variation by at most \(\binom{d}{2}/(n-1)\), by coupling sampling with and without replacement. For large \(n\) the binomial mean is at least \(d/16\); the probability to be below \(hd\) is at most \(\exp(-d/128)\) by the binomial Chernoff bound. With the sampling error included, the resulting bound times \(q^\eta\) tends to zero. The expected number of low-encounter labels and Markov’s inequality now give the claim on discarded mass.

Let \(\alpha,\beta\) be outcomes of independent extra-switch arrays given \(E\), identified also with their permutations. Write \(F\) for the number of fixed points of \(\alpha^{-1}\beta\). For all sufficiently large \(n\) and integers \(f\ge q^{1-\eta}\), we have \[ \Pr(\alpha\text{ good},\ F\ge f)\ \le\ q^{-c_* f}, \qquad c_*=h/8,\qquad (f\le q). \tag{15}\] Indeed fix \(E\) and the switches of a good \(\alpha\). Agreement of the two paths of a label at their endpoint (i.e. agreement of the output index) requires agreement at every layer: in locations in the cyclic-direction frame, the start and end of a \(d\)-layer path specify it since each bit is processed only once. For any set of \(f\) agreed labels at least \(f/2\) have at least \(hd\) encounters in \(\alpha\)’s outcome. Making \(\beta\) follow those paths fixes its extra coins on their internal encounters, at least \(hdf/4\) distinct coins since each pair can be counted at most twice in its layer. These coins are independent given \(E\). Union bounding over sets costs at most \(\binom{q}{f}\le(e q/f)^f\); this times \(2^{-hdf/4}\) is at most \(q^{-h f/8}\) by \(d\ge\log_2 q\) and the choice of \(\eta\), for large \(n\). This proves (15).

We use irreducible complex unitary representations \(\pi_\lambda\) of \(\mathfrak S(A)\) with dimensions \(D_\lambda\) and (un-normalized) characters \(\chi_\lambda\). Write \(\widehat\nu(\lambda)=\sum_g\nu(g)\pi_\lambda(g)\) for the matrix of a (possibly subprobability) law. Define the per-segment factor \[ b_\lambda=\frac{1}{D_\lambda}\mathbb E_E\operatorname{Tr}\!\left( \widehat{\mu'_E}(\lambda)^*\,\widehat{\mu'_E}(\lambda)\right) =\mathbb E\!\left[ \mathbf 1_{\alpha\ {\rm good},\,\beta\ {\rm good}}\, \frac{\chi_\lambda(\alpha^{-1}\beta)}{D_\lambda}\right]. \tag{16}\] The second equality uses the independent switches of \(\alpha,\beta\) conditional on \(E\). Moreover the expectation of the matrix inside the trace is \(b_\lambda I\). The law of the subprobability kernel is invariant under conjugating by permutations of \(A\): this renames the uniformly placed indices, with the same good-outcome rule. The scalar matrix claim follows by Schur’s lemma. The representation-theoretic background used here is recalled in [21, 3].

Apply Lemma 5 with group size \(q\) and \(\delta=\eta/4=1/16384\). Since \(4\delta=\eta\), if the number \(f\) of fixed points is at most \(q^{1-\eta}\), then \[\frac{|\chi_\lambda(\sigma)|}{D_\lambda}\le D_\lambda^{-\delta}.\] For all \(f\), the same lemma gives \[ \frac{|\chi_\lambda(\sigma)|}{D_\lambda} \le D_\lambda^{-\delta}q^{\delta f}. \tag{17}\]

Applying the small-\(f\) bound and (15), (17) in (16) (bounding by absolute values), and using \(\delta<c_*\), yields \[ 0\le b_\lambda\ \le\ 2D_\lambda^{-\delta} \tag{18}\] for large \(q\), since \(\sum_{f\ge q^{1-\eta}} q^{-(c_*-\delta) f}=o(1)\). For the sign representation we have the better bound \(b_{\rm sign}=o(1)\). If the environment contains any internal match then the sign expectation before truncation is zero by the fair extra coin on it. Its magnitude after truncation is then at most the mass discarded. If there is no internal match, no outcome is good, for large \(q\). This proves the sign estimate by the bound on expected discarded mass.

The reciprocal-degree estimate of Lemma 6 gives \[ \sum_{\lambda:\,D_\lambda>1}D_\lambda^{-2}=o(1). \tag{19}\]

Now take \(k=\lceil 4/\delta\rceil\). In the independent segment experiment let \(\nu'\) denote the product law obtained by convolving the \(k\) subprobabilities (multipliers applied on the left). At each nontrivial representation the expected squared Hilbert-Schmidt norm of its matrix is \(D_\lambda\) times the product of the \(b_\lambda\) factors: iteratively use independence and the scalar matrix expectation after (16) for the latest matrix in the product. The estimates are uniform even if cyclic phases differ. By finite group Plancherel, for the uniform probability \(U_A\) on \(\mathfrak S(A)\), \[q!\sum_g |\nu'(g)-U_A(g)|^2 = |\nu'(\mathfrak S(A))-1|^2+ \sum_{\lambda\ne{\rm triv}}D_\lambda \|\widehat{\nu'}(\lambda)\|_{\rm HS}^2 .\] The mass deficit tends to zero in expectation (bounded by the sum of discarded masses), thus also in expected square. The expected sign term tends to zero. The expected sum for \(D_\lambda>1\) is at most \[2^k \sum_{D_\lambda>1} D_\lambda^{2-\delta k}=o(1)\] by (18), (19). These account for all irreducibles (the one-dimensional ones being trivial and sign for large \(q\)). By Cauchy-Schwarz the expected \(\ell^1\) error tends to zero. Reinstating the discarded masses costs \(o(1)\) also in expected \(\ell^1\), since the product law before truncation dominates \(\nu'\) pointwise. This proves Proposition 14 for independent segments, and hence for the actual segments by the comparison in the call construction.

From group calls to the whole permutation

We can now randomize any one prescribed group of \(n/8\) indices, conditional on the base in expected total variation. Mixing the groups of just one partition would preserve which labels belong to each group. Two transverse partitions remove that obstruction. We prove the required three-round comparison, including its discrete total-variation conclusion.

Choose two partitions of the base index set \(V\), one into \(R_1,\ldots,R_K\), the other into \(C_1,\ldots,C_K\), with \(|R_i\cap C_j|=n/K^2\); this is possible for large \(d\). Make calls for the \(R\)-groups, then the \(C\)-groups, then the \(R\)-groups again, one call for each group of the indicated partition, in any fixed order within each partition. Conditional on the full base, the multipliers from distinct calls are independent (they use independent extra coins on edges prescribed from the base). In expectation over the base, their product law has total-variation error \(o(1)\) from the product law using independent uniforms on the called groups. This follows by the per-call error just proved, summed over the \(3K\) calls, replacing conditional laws in the product and mapping to the composed permutation. Inside each partition these ideal uniforms together act as an independent uniform shuffling within each group.

The remaining comparison concerns only uniform group shuffles. Alternating independent row and column permutations were studied by Håstad in the square lattice shuffle [4]. Here the number of blocks is fixed and their intersections grow; the proof uses the resulting contingency-table local limit.

We conclude that the overlay product conditional on the base has expected total-variation distance \(o(1)\) from a uniform permutation on \(V\). Multiplying by the final base permutation (fixed under the conditioning) preserves the comparison with uniform. Removing the conditioning and mapping back to the deck locations proves total-variation distance \(o(1)\) for the actual shuffle. All estimates hold for any initial deck by identifying its cards with their starting positions. The shuffle has uniform stationary law since every layer applies a random permutation according to switches independent of the incoming deck. We used \(3K\cdot k\cdot 21d\) full layers of the type counted as steps in the shuffle definition. This gives the upper bound by an absolute multiple of \(d\) for sufficiently large \(d\). The choices give \(\delta=1/16384\), \(k=65536\), and \(3Kk\cdot21=33030144\), so the upper time is \(33030144d\) complete shuffles.

This proves Theorem 12. The support bound of Section 2 also gives \(t_{\mathrm{mix}}\ge d\) for all sufficiently large \(d\).

The two precise inputs

Here we use two companion results. We state their full hypotheses so that the conditional law to which each applies is explicit. Write \(\operatorname{inj}(I,J)\) for the set of injections from a finite ordered set \(I\) into a finite set \(J\).

The conditional path theorem [17] has the following form. Fix \(0<p<1\) and define \[ \rho_p=\frac{3+p}{4},\qquad c_p=-\frac18\log_2\rho_p, \qquad b=\lceil10/c_p\rceil. \tag{22}\] For every deterministic starting deck, every specified base set of \(r_0\) labels, and every ordered list of \(k\) additional labels satisfying \(r_0+k-1\le pn\), after \(2b\) sweeps, \[ \mathbb E_{\mathcal H}\left\| \mathcal L(\text{list endpoints}\mid\mathcal H) -\operatorname{Unif}\operatorname{inj}([k],V\setminus E_{\mathcal H}) \right\|_{\mathrm{TV}}\le k n^{-4}. \tag{23}\] Here \(\mathcal H\) is the full labelled base-path history and \(E_{\mathcal H}\) its endpoint set. The estimate holds for every cyclic coordinate order, including the reverse order. It also holds after coarsening \(\mathcal H\), provided the endpoint available set remains determined. All thresholds depend only on the fixed \(p\).

The abstract conditional-product transfer [18] concerns \(V=A\sqcup C\) with \(|A|=|C|=h\), and \(H=S_A\times S_C\). Partition each half into \(L\) equal buffers, where \(L\ge2C_0\) and \(C_0=2000000\). Suppose a subprobability \(\xi\) on \(S_V\) has both ordered inverse-image marginals \(x^{-1}|_A\) and \(x^{-1}|_C\) pointwise at most twice uniform. For every environment \(z\), let \(\nu_A^z,\nu_C^z\) be subprobabilities on the two half-groups. Assume that, in each factor and for every buffer, the ordered image tuple on the complement of that buffer has marginal at most twice uniform. For each \(z\), choose an arbitrary deterministic permutation \(t_z\in S_V\). If \(Z\) has any probability law, put \[\omega=\mathbb E_Z\big[\delta_{t_Z}*(\nu_A^Z\otimes\nu_C^Z)\big], \qquad \theta=\omega*\xi.\] Then, for all sufficiently large \(h\), every irreducible representation of \(S_V\) of degree \(D>1\) satisfies \[ \|\widehat\theta\|_{\mathrm{op}}\le\sqrt{22}\,D^{-1/40}. \tag{24}\] The Hilbert–Schmidt norms in that theorem use ordinary, unnormalized trace. For either \(J\in\{A,C\}\), let \(\nu_J\) be a factor satisfying the buffer caps and let \(\gamma\) be an irreducible representation of \(S_J\), of degree \(D_\gamma\). The underlying buffer estimate is \(\|\widehat\nu_J(\gamma)\|_{\mathrm{HS}}^2/D_\gamma\le\min(1,2D_\gamma^{-1/2})\). For irreducibles \(\alpha\) of \(S_A\), \(\beta\) of \(S_C\), and \(\lambda\) of \(S_V\), write \(c_{\alpha\beta}^{\lambda}\) for the multiplicity of \(\alpha\otimes\beta\) in the restriction of \(\lambda\) to \(H\). These multiplicities are retained through the estimate \(c_{\alpha\beta}^{\lambda}\le\min(D_\alpha,D_\beta)\), where each \(D\) denotes the corresponding degree. For the final Fourier sum we will use the local reciprocal-square estimate in Lemma 6.

These are separate inputs. The first supplies conditional tuple information from the shuffle; the second converts explicit caps and a conditional product into an operator bound. The product property will now be proved for the actual shuffle environment.

Inverse-image caps for the first block

For these choices, \(L\) divides \(h=n/2\) for all sufficiently large \(d\). Fix two halves \(A,C\) of \(V\) and partition each into \(L\) buffers of size \(h/L\). Let \(X,W\) be independent permutations each generated by \(2b\) forward sweeps, and let \(\mu\) be the law of \(WX\).

The inverse of \(X\) is generated by the independent involutive layers in reverse order. Apply (23) with empty base and a list consisting of \(A\), and then of \(C\). Since \(h-1\le pn\), each ordered inverse-image half-tuple has distance at most \(h n^{-4}\) from uniform.

We use the following elementary truncation rule repeatedly. If probability laws \(P,Q\) are on one finite set, then \[P\{v:P(v)>2Q(v)\}\le2\|P-Q\|_{\mathrm{TV}},\] since \(P(v)\le2(P(v)-Q(v))\) on those atoms and the total positive excess is the variation distance. Delete from the law of \(X\) every permutation whose inverse-image tuple on either half is an atom of more than twice its uniform probability. Call the resulting subprobability \(\xi\). It obeys both required pointwise caps, and \[ 1-\xi(S_n)\le4h n^{-4}=2n^{-3}. \tag{25}\] The deletion for the other half cannot increase a marginal. Thus one common \(\xi\) has the two caps simultaneously.

The occupancy environment and the conditional product

Color the positions at the start of \(W\) by membership in \(A\) or \(C\), regarding those starting positions as distinct labels for this block. Let \(Z\) record the set of positions occupied by each color after every layer, including the initial and final boundary. It records no labels within a color.

Write \(\mu_A^z,\mu_C^z\) for these two conditional probabilities. Fix a buffer \(B\subset A\). Apply (23) to \(W\) with all \(C\) labels as base and the list \(A\setminus B\) as the additional labels. Here \[r_0+k-1=h+(h-h/L)-1 =n-\frac n{2L}-1\le pn.\] The error is at most \((h-h/L)n^{-4}\). The full labelled \(C\) paths determine the color occupancy history \(Z\), and \(Z\) still determines their endpoint set. Hence the allowed coarsening in (23) gives that same expected error conditional on \(Z\). Applying the deterministic bijection \(t_Z^{-1}\) sends the comparison law to uniform ordered distinct images in \(A\). We conclude \[ \mathbb E_Z\left\| (\mu_A^Z)_{A\setminus B} -(U_A)_{A\setminus B}\right\|_{\mathrm{TV}} \le(h-h/L)n^{-4}. \tag{26}\] The same argument applies to every buffer of \(C\), interchanging the colors. The endpoints’ available set is essential here: ordinary unconditional list mixing would not imply (26).

For each \(z\), delete from \(\mu_J^z\) all permutations whose ordered image tuple outside any buffer exceeds twice its uniform probability, for \(J=A,C\). Denote the subprobabilities by \(\nu_J^z\) and their masses by \(a_J(z)\). The truncation rule and (26) give \[\mathbb E_Z\big[(1-a_A(Z))+(1-a_C(Z))\big] \le4L(h-h/L)n^{-4}=(2L-2)n^{-3}.\] Every surviving factor satisfies each cap for its particular \(z\), even if the loss at that environment is large. Lemma 17 now permits the product of these two deletions: define \[\omega=\mathbb E_Z[\delta_{t_Z}*(\nu_A^Z\otimes\nu_C^Z)].\] It is dominated pointwise by the true law of \(W\). Its missing mass is \(\mathbb E[1-a_Aa_C]\), bounded by the preceding display because \(1-a_Aa_C\le(1-a_A)+(1-a_C)\).

We have now established every conditional-law hypothesis of the transfer: the environment has its original probability law, each conditional measure is an actual product, each factor has all its buffer-complement caps, and the first block has the two inverse-image caps. Define \(\theta=\omega*\xi\). Independence of the original blocks and positivity of convolution give \(\theta\le\mu\) pointwise, while \[ 1-\theta(S_n)\le2L n^{-3}=o(1). \tag{27}\] The integer \(L\) is large but fixed before \(d\) tends to infinity.

Fourier completion and physical time

Applying (24) gives the degree-power operator bound for every \(D_\lambda>1\). We include the final deduction to keep the mass, parity and time conventions visible in this application.

The original block law \(\mu\) has expected sign zero. Indeed, condition on all switch coins except any one coin in a physical layer. Flipping that fair coin composes the final permutation with a conjugate transposition and reverses its sign. From \(\theta\le\mu\) and (27), \[|\widehat\theta(\mathop{\mathrm{sgn}})|\le1-\theta(S_n)\le2L n^{-3}.\] Let \(j=100\) and \(q=\theta(S_n)\). The trivial Fourier coefficient of \(\theta^{*j}-U_n\) is \(q^j-1=o(1)\) and its sign coefficient is \(\widehat\theta(\mathop{\mathrm{sgn}})^j=o(1)\). For all other irreducibles, without assuming their matrices commute or are normal, \[\sum_{D_\lambda>1}D_\lambda \|\widehat\theta(\lambda)^j\|_{\mathrm{HS}}^2 \le22^j\sum_{D_\lambda>1}D_\lambda^{2-2j/40} =22^{100}\sum_{D_\lambda>1}D_\lambda^{-3}=o(1).\] We used submultiplicativity of the operator norm, \(\|B\|_{\mathrm{HS}}^2\le D\|B\|_{\mathrm{op}}^2\), and Lemma 6, since \(D^{-3}\le D^{-2}\). Plancherel and Cauchy–Schwarz imply \(\|\theta^{*100}-U_n\|_1=o(1)\). Restoring the missing measure costs \(1-q^{100}=o(1)\), so \(\|\mu^{*100}-U_n\|_{\mathrm{TV}}\to0\).

Each of \(X,W\) costs \(2bd\) physical shuffles. One macro-step therefore costs \(4bd\), and the \(100\) independent macro-steps cost \(400bd\). They concatenate at sweep boundaries and hence have exactly the physical shuffle law at that time. Translation by any fixed initial deck preserves total variation. This proves Theorem 16.