Proof. Use either the blocker-prefix filtration or the larger filtration containing the initial selection and all switch coins already used. The vector \(f_t\) is measurable for either; the larger filtration does not redefine the path-conditioned law \(p_t\). On a pair with one available position \(x\), its contribution to \(\xi_t\) is \(\pm f_t(x)(e_x-e_{x^{i_t}})/2\), with a fair sign. The signs for different pairs are conditionally independent. On the other pairs the noise is zero. This proves conditional centering, (6), and (9); the cross term between \(P_{i_t}f_t\) and \(\xi_t\) also has conditional mean zero.

Unroll \(f_{s+1}=P_{i_s}f_s+\xi_s\) over the last \(d\) updates. The initial term is zero because its coordinate averages include every direction. Noises created at different times are orthogonal in expectation, even after the subsequent deterministic operators, by conditional centering. A pair difference created at time \(t-j\) is followed by \(j-1\) averages in distinct other directions. Its endpoints spread over two disjoint subcubes of size \(2^{j-1}\), so its squared norm is multiplied by \(2^{-(j-1)}\). Different pair noises at one time have zero cross terms in expectation by their independent signs, even if the propagated supports overlap. Consequently \[a_t=\sum_{j=1}^d2^{-(j-1)}\mathbb E\|\xi_{t-j}\|_2^2,\] which proves (7). Subtracting one half of that identity from its version at \(t+1\) gives (8). Equivalently, taking traces after expanding (9) gives these same weights: the factor \(1/4\) multiplies the squared pair-difference norm \(2\cdot2^{-(j-1)}\), giving exactly \(2^{-j}\). ◻

Proof. The preceding update in direction \(i_s\) is \(s-d\to s-d+1\). Conditional on the blocker configuration immediately before that update, the blocker count in one coordinate half afterwards is a constant from two-blocker pairs plus a sum of at most \(n/2\) independent fair Bernoulli variables from mixed pairs. Its mean is half the total blocker count. If either half has blocker fraction greater than \(1-\alpha/2\), its count differs from this mean by at least \(\alpha n/4\). Hoeffding’s bound therefore gives probability at most \(2e^{-\alpha^2n/4}\) for this event.

Condition now on the blocker paths just after that preceding update. The next \(d-1\) updates use all other coordinates, acting independently in the two halves. The value \(f_s(x)\) is computed from the history in the half of \(x\) only. Its opposite partner \(x^{i_s}\) is in the other half. Every blocker in that other half has uniform one-card marginal there after these \(d-1\) coordinate updates, because each bit is refreshed once. Thus the partner-blocker indicator is conditionally independent of \(f_s(x)^2\), and its conditional mean is that half’s earlier blocker fraction. On histories with both fractions at most \(1-\delta\), summing over \(x\) bounds the conditional contribution by \(1-\delta\) times the conditional energy. On the remaining histories use \(\|f_s\|_2^2\le\|f_0\|_2^2\). This proves the first inequality. Apply (11), with \(\rho=1-\delta\), \(t_0=2d\), and \(2\gamma-1=1-\delta\), to obtain the second. ◻

Proof. For the first assertion use \(\alpha=1/16\) in Lemma 6. At \(T=1024d\), \(\gamma^{T-2d}\le e^{-1022d/64}\), so \(a_T\le2n^{-6}\) eventually. For the second use \(\alpha=1/8\), giving \(\gamma=31/32\) and \[a_{256d}\le e^{-254d/32}+16\eta_n, \qquad n^3a_{256d}=o(1).\] In each case expose the list in order. For its next card take the preceding labels as blockers. Conditional on their complete paths, its distance from uniform on the remaining positions is \(\|f_T\|_1/2\), whose expectation is at most \(\sqrt{na_T}/2\). Conditioning on just their endpoints can only decrease this expected distance, by convexity, since the uniform reference on available positions depends only on those endpoints. Interpolate between laws with a true prefix and a suffix extended uniformly without replacement. Adjacent laws differ by at most the preceding expected one-card error; summing at most \(n\) errors gives \(n^{3/2}\sqrt{a_T}/2\). The first bound is at most \(n^{-3/2}\) and the second tends to zero. This proves both assertions. ◻

Proof. Condition on the initial label choice and all switch history through \(s-L\). Each of these subcubes now evolves with its own independent coins. The update rule for \(f\) is local, so \(f_s(x)^2\) depends on the coins in the subcube of \(x\). Its partner \(x^{i_s}\) lies in a different subcube, since the current coordinate has not been used among the preceding \(L\) coordinates. The indicator that the partner is available is conditionally independent of \(f_s(x)^2\). Its conditional mean is the old density of available positions in its subcube: averaging in each of that subcube’s \(L\) coordinates makes the expected occupancy constant. On the asserted event this gives the factor \(1-r\). On its complement the sum of squared masses is at most one. Averaging proves the result. The argument uses unconditional concentration of the old available set, rather than claiming that it is uniform after path conditioning. ◻

Proof. Choose a uniform ordered list with underlying set \(A\). At any exposure index, the earlier labels are blockers and the next label is tagged; the number of available positions is at least \(qn\). Put \(L=\lfloor d/2\rfloor\). At every fixed time the available set is unconditionally uniform, since a shuffle permutation independent of the initial selection preserves uniform subset sampling. Its chance of having fraction below \(q/2\) in any one of the preceding-coordinate subcubes is at most \[ \eta_d=n(n+1)e^{-q2^L/8}. \tag{21}\] Indeed sample independent Bernoulli indicators of parameter \(m/n\), then condition their total to equal \(m\). This conditioning gives a uniform \(m\)-subset, and the conditioning event has probability at least \(1/(n+1)\): the value \(m\) is a mode of the binomial distribution with parameter \(m/n\). The degenerate parameter one is immediate. Before conditioning, the lower-tail Chernoff bound for a subcube of size \(2^L\) is at most \(e^{-q2^L/8}\). A union bound over at most \(n\) subcubes proves (21).

Lemma 10 gives \(w_s\le\rho a_s+\eta_d\) for \(s\ge L\), with \(\rho=1-q/2\). Set \(t_0=d+L\) and \(\theta=1-q/8\). Since \(\rho/(2\theta-1)<1\), the comparison induction gives \[a_t\le\theta^{t-t_0}+2\eta_d/q.\] At \(T=100bd\) the geometric term is at most \(\exp(-(100b-1.5)qd/8)\), and hence \(a_T=o(n^{-5})\) uniformly in the exposure index. The sequential comparison used in Proposition 7, now averaged over the initial list, bounds its mean tuple distance by \(n^{3/2}\sqrt{a_T}/2=o(1)\). The order of the chosen starting labels does not affect the distance for their restriction map, proving (20). ◻

Proof. The density of available positions is at least \(1/4\). If \(B_C\) counts blockers in a fixed preceding-coordinate subcube \(C\), uniform sampling gives \[\mathbb E2^{B_C} =\mathbb E\prod_{x\in C}(1+\mathbf 1_{\{x\text{ blocked}\}}) \le\sum_{J\subseteq C}(3/4)^{|J|}=(7/4)^{|C|}.\] Markov’s inequality therefore bounds the probability that \(B_C\) exceeds \(7|C|/8\) by \(((7/4)2^{-7/8})^{|C|}\). Union over at most \(n\) subcubes and Lemma 10 prove (22). The base is strictly less than one. Using the exact covariance recursion (9), or its trace identity (7), gives \[a_t\le(31/32)^{t-2d}+8\eta_d.\] The comparison is valid because \((7/8)/(2(31/32)-1)=14/15<1\) and \((7/8)8+1=8\). At \(T=1000d\) this is \(o(n^{-10})\). The expected conditional variation per list entry is at most \(\sqrt{ma_T}/2\le\sqrt{na_T}/2\). Summing as before proves the claimed mean tuple bound. ◻

Proof. Choose a uniform ordered partition and independently uniform orders of its eight complements. For one of these random orders and a fixed exposure index, let earlier labels be blockers, put \(p=1/8\), and use the centered vector \(f_t\) already defined. Unconditionally its available set is uniform and has size at least \(pn\).

Write \(s=\ell d+j\), with \(\lceil d/2\rceil\le j\le d-1\). Conditional on the history at \(\ell d\), the first \(j\) coordinate updates evolve independently in their \(j\)-dimensional subcubes. The argument of Lemma 10, with this pass boundary in place of \(s-L\), gives \(w_s\le(1-p/2)a_s+\delta_n\), where \[\delta_n=n\exp(-p^2\sqrt n/16).\] For completeness, in a subcube of size \(r\) let \(B\) count blockers. For every \(\vartheta>0\), expansion over subsets and sampling without replacement give \[\mathbb Ee^{\vartheta B} \le[1+(1-p)(e^{\vartheta}-1)]^r.\] Take \(\vartheta=p/4\) and use \(e^\vartheta-1\le\vartheta+\vartheta^2\). The logarithm of the Markov bound for \(B>(1-p/2)r\) is at most \[r\{-\vartheta(1-p/2)+(1-p)(\vartheta+\vartheta^2)\} \le-rp^2/16.\] Here \(r=2^j\ge\sqrt n\), and a union bound proves the displayed \(\delta_n\). At all other times simply use \(w_s\le a_s\).

Starting with \(a_d\le1\), the one-step memory inequality (8) now contracts by \(1-p/4\) at each late step, and otherwise does not increase except for the additive bound. There are \((2048-1)\lfloor d/2\rfloor\) late steps after time \(d\). Thus \[ a_T\le(1-p/4)^{2047\lfloor d/2\rfloor}+T\delta_n \le n^{-18} \tag{24}\] eventually. For the last inequality one may use \(\lfloor d/2\rfloor\ge d/3\) and \(p/4=1/32\).

For each query define \(E_a=\{\|f_T\|_2\le n^{-3}\}\). Its failure probability is at most \(n^{-12}\) by (24). There are at most \(8n\) queries, so their simultaneous success has probability at least \(1-8n^{-11}\), averaging over the initial choices and the shuffle. Fix choices of partition and orders attaining at least this probability. Let \(f(g)\) be the probability of permutation \(g\) together with simultaneous success. This proves its domination and mass assertion.

It remains to prove its pointwise coset bounds. In one fixed order, let \(\mathcal B_a\) reveal the full paths through \(T\) of the first \(a\) labels. The event \(E_a\) for query \(a\) depends only on \(\mathcal B_{a-1}\), since the initial tag is fixed and its conditional law is computed from earlier paths. On this event the conditional probability of a specified next endpoint is at most \[\frac1{n-a+1}+n^{-3} \le\frac{1+n^{-2}}{n-a+1}.\] For specified distinct endpoints, let \(S_a\) be the event that the \(a\)th card reaches its specified endpoint. In the product of \(\mathbf 1_{S_a}\mathbf 1_{E_a}\), condition first on \(\mathcal B_{n-n/8-1}\) and remove the last factor using this bound; then continue backwards. All previous factors are measurable at the conditioning step. This proves that the probability of the specified endpoint list together with all its good events is at most \[(1+n^{-2})^{n-n/8}\frac{(n/8)!}{n!} \le2\frac{|H_i|}{|G|}.\] The subprobability \(f\) also requires the other orders’ good events, so it is bounded by this probability. A coset \(gH_i\) specifies exactly this complement endpoint list, proving (23). ◻

Proof. Write \(C_u=\sup_{m\ge1}\sum_{\tau\vdash m}D_\tau^{-u}\) for the finite constants proved in [14]. For the separate peeling argument put \(C_{\rm peel}=512^2\). As before, every untrimmed positive-time shuffle block has zero sign expectation. All the lifting statements invoked below are proved independently in [14].

For the \(1024d\) law, apply the first part of Proposition 7 with \(b=16\) blocks. Use the sequential trimming operation in Lemma [l-l:trim] of [14]: reduce each coset mass exceeding its uniform mass to that mass. Each reduction preserves the earlier caps, and the total mass removed is at most \(\varepsilon=bn^{-3/2}\). The resulting subprobability \(f\le\mu\) has mass \(z\ge1-\varepsilon\) and caps one. Thus \(\nu=f/z\) satisfies \(\|\nu-\mu\|_{\mathrm{TV}}\le\varepsilon\) and has cap two when \(\varepsilon\le1/2\). Proposition [l-l:orbit-span] of [14] bounds the operator norm by \(A D^{-3/8}\), \(A=\sqrt{2bC_2}\). Since \(\|B^8\|_{\mathrm{HS}}\le\sqrt D\|B\|_{\mathrm{op}}^8\), the nonsign sum is at most \(A^{16}\sum_{D>1}D^{2-6}=o(1)\). Its sign coefficient has absolute value at most \(2bn^{-3/2}\). The same probability comparison proves mixing at \(8\cdot1024d\).

For the predictable construction, let \(f\le\mu\) be supplied by Proposition 13, and put \(z=\sum f\). Proposition [l-l:isotypic] of [14], with \(B=2,b=8\), gives \(\|\widehat f(\rho)\|_{\mathrm{HS}}^2\le16C_2D^{-1/2}\). Eight powers again leave an inverse-cube dimension sum. Its sign coefficient is bounded by \(1-z=o(1)\) and its trivial coefficient is \(z\). More explicitly, for any fixed \(R\), \[ \|f^{*R}-z^R U_G\|_1^2 \le\sum_{\rho\ne\mathrm{triv}} D_\rho\|\widehat f(\rho)^R\|_{\mathrm{HS}}^2. \tag{25}\] Thus the right side tends to zero for \(R=8\). The differences \(\mu^{*R}-f^{*R}\) and \(U_G-z^RU_G\) have \(\ell^1\) norms \(1-z^R=o(1)\), since the former is nonnegative. This proves mixing after \(8\cdot2048d\).

For peeling, take \(b=2^{22}\) and \(T=100bd\) in Proposition 11. A uniform equal-size partition has uniformly distributed complements, so averaging selects one deterministic partition whose sum of complement errors is \(o(1)\). Heavy-coset deletion gives a subprobability \(\eta\le\mu\) of mass \(1-o(1)\) and cap two. Since \(b\ge4(C_{\rm peel}+2)\), Corollary [l-l:peeling-lift] of [14] implies \[\sum_{D_\rho>1}D_\rho\|\widehat\eta(\rho)^4\|_{\mathrm{HS}}^2 \le(6b)^4\sum_{D_\rho>1} D_\rho^{1-4(1-(C_{\rm peel}+2)/b)}=o(1),\] because the exponent is at most \(-2\) and Theorem [l-l:degree-all-powers] of [14] applies. The trivial and sign coefficients, and restoration of missing mass, are handled exactly by (25). The total physical time is \(4T=400\cdot2^{22}d\).

Finally, Proposition 12 selects, by the same averaging argument, a deterministic partition into four blocks with complement errors summing to \(o(1)\) for the \(1000d\) law. Trim to a subprobability \(\eta\) of mass \(1-o(1)\) and cap two. Proposition [l-l:four-coefficient] of [14] gives \(\|\widehat\eta(\rho)\|_{\mathrm{op}}\le C D^{-1/8}\). After sixteen factors the nontrivial nonsign sum is at most \[C^{32}\sum_{\rho\ne\mathrm{triv},\mathop{\mathrm{sgn}}}D^{2-16/4} =C^{32}\sum_{\rho\ne\mathrm{triv},\mathop{\mathrm{sgn}}}D^{-2}=o(1).\] Again parity and missing mass are controlled as above. This proves the covariance route at \(16\cdot1000d=16000d\).

All blocks contain a whole number of sweeps. The moving frame therefore returns to the physical coordinates, and independent blocks have the convolution laws used above. Equation (2) supplies worst-start uniformity in every case. The lower obstruction is (3); it is independent of which upper-bound method is used. ◻

Proof. A character omitting the active coordinate is constant on every updated edge, and the update preserves the sum on that edge. A character containing the active coordinate has opposite values at the endpoints. An edge with two available positions contributes zero after averaging. Each edge with one available position contributes its entry times an independent centered sign. The conditional second moment is therefore \(L_s\).

At time \(t\ge d\), every nonempty character has a last update among the previous \(d\) layers. Exactly \(2^{d-j}\) subsets have their last update at time \(t-j\): they include that coordinate, omit the \(j-1\) more recent coordinates, and choose arbitrarily among the other \(d-j\). The empty coefficient is zero. Parseval, with normalization \(\|f\|_2^2=n^{-1}\sum_A\widehat f(A)^2\), now gives (27). ◻

Proof. The updates from \(a\) through \(s-1\) visit each coordinate other than \(i_s\) once and never cross the two halves. Given the initial history, the future switch arrays in the halves are independent of that history and of each other. Starting from the now known restrictions of \(V_a\) and \(f_a\), both the exposed paths and the forward flow inside one half are measurable functions of that half’s switch array alone. The cylinder description in Lemma 2 leaves its unvisited switches independent, so computing the conditional flow introduces no dependence on the other half. The flow value at \(x\) uses only the array in its own half, whereas the opposite partner’s membership in \(V_s\) uses the other array. In that other half, each exposed card is marginally uniform after these \(d-1\) layers, since each remaining bit has been refreshed with a fair bit. Distinctness of the card positions gives the stated expected available density. This proves (29). Subtract the available-partner contribution from \(a_s\) and use \(\|f_s\|_2^2\le1\) on the exceptional event to obtain (30). ◻

Proof. For the first assertion, \(a=s-d+1\ge1\) is the time immediately after the preceding update in coordinate \(i_s\). Given the history before that update, either half’s available count is \(A+\operatorname{Bin}(L,1/2)\), where \(2A+L=m\) and \(L\le m\). A deviation below \(m/4\) has probability at most \(\exp(-m/8)\) by the independent bounded-difference estimate for the \(L\) fair choices. The union bound handles both halves. Each half with at least \(m/4\) available positions has available density at least \(1/(2q)\).

For a random list, \(V_a\) is unconditionally a uniform \(m\)-subset, because a fixed permutation maps a uniform subset to a uniform subset. This statement is unconditional; no independence of \(f_a\) and \(V_a\) is asserted. A half count has mean \(m/2\). Its Doob martingale under sequential sampling without replacement has increments of absolute value at most one: changing the next draw can be coupled with the remaining completion by exchanging those two sites. The bounded-increment martingale inequality gives probability at most \(\exp(-m/32)\) for a downward deviation of \(m/4\), proving the first displayed choice.

For the other choice, sample independent Bernoulli variables with parameter \(m/n\) and condition their total to equal \(m\). The latter event has probability at least \(1/(n+1)\) since \(m\) is a binomial mode; the case \(m=n\) is deterministic. Before conditioning, a half count \(X\) satisfies \(\mathbb E2^{-X}\le e^{-m/4}\). Thus \(\mathbb P(X<m/4)\le\exp(-(1-\log2)m/4)\). Condition and sum over the two halves.

Finally, failure of the \(m/8\) balance forces at least \(k=\lceil7m/8\rceil\) of the \(m\) sampled sites into one half. For any specified \(k\) sample indices the probability is at most \(2^{-k}\). The union bound gives \(2\binom mk2^{-k}\), which is at most \(2e^{-cm}\): use \(\binom m{m-k}\le(8e)^{m/8}\) and \((7/8)\log2-(1/8)\log(8e)>0\). Lemma 16 now proves all three assertions. ◻

Proof. Apply (11) with \(\rho=1-\beta\), \(s_0=d\), \(t_0=2d\), and \(a_0\le1\). The condition on \(\gamma\) is exactly \((1-\beta)/(2\gamma-1)\le1\). For each list entry, Cauchy–Schwarz bounds the mean path-conditioned variation by \(\frac12\mathbb E\|f_T\|_1\le\frac12\sqrt{ma_T}\). Lemma 3 sums these errors: its uniform reference depends only on the previously exposed endpoints, so its path-conditioning version applies. Averaging this inequality over an independently sampled list gives the random-domain assertion. ◻

Proof. Apply Lemmas 17 and 18. The \(256\)-block row uses the \(m/8\) threshold; the other rows use \(m/4\). The exceptional terms are exponentially small in \(n\). For the numerical choices, \((63/64)^{510d}=O(2^{-7d})\) and \((31/32)^{198d}\le2^{-8d}\), since \(198\log_2(32/31)>8\). In the last row the geometric term is at most \(\exp(-100d/8)=o(2^{-4d})\). The sequential estimate multiplies \(\sqrt{na_T}/2\) by at most \(n\), giving the claimed errors. ◻

Proof. All Fourier bounds in the table are exact cases of [14]: Proposition [l-l:random-partition] for the first row; Proposition [l-l:coefficient-lift] for the coefficient and pointwise-character rows; Proposition [l-l:isotypic] for the global isotypic row; Propositions [l-l:coefficient-average] and [l-l:orbit-average] for the two projection averages; and Theorem [l-l:character-lift] for the last row. The last transfer uses a one-dimensional character of index at most \(b^{1024}\) in every block type of degree \(b\), which gives \((1024+2)/K=1026/8192<1/4\) in its displayed bound.

The first row uses the averaged complementary-coset estimate at \(200d\) directly. Its transfer constructs a conditional probability law and keeps the partition random inside the coefficient estimate; it does not select a deterministic partition there. All other rows use the selected partition and the indicated common trimming.

For an operator bound \(A D^{-\beta}\), the probability completion of Section 3.3 gives a nonsign summand \(A^{2r}D^{2-2r\beta}\). For a squared Hilbert–Schmidt bound \(A D^{-\beta}\), it gives \(A^rD^{1-r\beta}\). Substitution gives the column \(\kappa\). Every displayed upper exponent is negative, so the corresponding reciprocal-degree sum tends to zero. In particular the pointwise-character and small-index rows use subprobabilities; they need the same norm calculation with their mass retained.

To finish those two rows, let \(z=\nu(G)=1-o(1)\). Since the original shuffle block has zero sign expectation, the retained subprobability has sign coefficient at most \(1-z\). Equation (25) makes \(\|\nu^{*r}-z^rU_G\|_1=o(1)\), while restoring the missing mass costs \(1-z^r\le r(1-z)\) in each of the two positive measures. For the probability rows, closeness to the original block law gives sign coefficient \(o(1)\) and permits replacement of the \(r\) factors, as in Section 3.3.

Finally multiply the corresponding block length from Proposition 19 by \(r\). For the last row this is \(4(100\cdot8192+2)d=3276808d\). All block lengths are multiples of \(d\), so their convolutions are physical shuffle blocks. Translation by a deterministic starting deck preserves distance from uniform. ◻

Proof. Successive conditioning at two-sweep boundaries gives \(\mathbb E\|f_{2Rd}\|_2^2\le \kappa_d^R\) for the centered conditional law of each next card, exposing all preceding cards. There are always at least \(pn\) available positions. Cauchy–Schwarz bounds its expected conditional variation distance by \(\frac12\sqrt{n\kappa_d^R}\). Conditioning on the preceding endpoints alone can only decrease this expectation: the uniform reference on available positions is already measurable from those endpoints, and the conditional law is the conditional expectation of the path-conditioned law. Finally interpolate between joint laws with a true prefix of length \(j\) and uniform sampling without replacement thereafter. Consecutive laws differ by the conditional error at the next card, averaged under the actual prefix law. Summing at most \(n\) such errors proves the bound. ◻

Proof. Let \(m=\lfloor3d/4\rfloor\) and \(p=|F_0|/n\). At layer \(j\) of a sweep, \[f_j=A_jf_{j-1}+\xi_j.\] Conditional on the past, \(\xi_j\) is the sum, over pairs \(\{u,v\}\) with exactly one available endpoint \(u\), of independent centered vectors \(\pm f_{j-1}(u)(e_u-e_v)/2\). Here \(e_x\) denotes the unit vector at a position \(x\). Expanding the entire sweep, the centered noise terms at different times are orthogonal in second moment, even after applying deterministic averaging operators. Moreover \(\|B_m(e_u-e_v)\|_2^2\le2\cdot2^{-m}\), and all coordinate averages commute. Since \(B_df_0=0\), and writing \(f^*,h^*\) for the output, \[ \mathbb E\|B_mf^*\|_2^2\le d2^{-m}\|f_0\|_2^2,\qquad \mathbb E\|B_mh^*-p\mathbf 1\|_2^2\le d2^{-m}n. \tag{39}\] For the second inequality use the same expansion for flags and \(\|h_0\|_2^2=pn\le n\). Energy monotonicity bounds each layer’s sum of squared noise coefficients by the initial energy.

A level-\(m\) block varies in coordinates \(1,\ldots,m\). If one such block has a fraction of available positions below \(1/16\), the second squared norm in (39) is at least \(2^m/256\). Thus the event \(\mathcal G\) that all these blocks have density at least \(1/16\) satisfies \(\Pr(\mathcal G^c)\le256dn2^{-2m}\).

Condition on the output of sweep one. Before coordinate \(j\) of sweep two, distinct level-\((j-1)\) blocks have used disjoint fresh coins. In particular the two endpoints \(x,y\) of the next pair have independent flag-weight data, whose means are the entries of \(B_{j-1}h^*,B_{j-1}f^*\). Their energy loss is exactly \[\frac12\bigl(h(y)f(x)^2+h(x)f(y)^2-2f(x)f(y)\bigr).\] On \(\mathcal G\), for \(j>m\) both flag means are at least \(1/16\). The sum of the expected cross products over the pairs is at most \(\frac12\|B_{j-1}f^*\|_2^2\le\frac12\|B_mf^*\|_2^2\). The conditional expected energy therefore contracts by \(31/32\) at each such step, with additive term \(\frac12\|B_mf^*\|_2^2\). Iterating this recurrence, and using monotonicity on \(\mathcal G^c\), gives \[ \mathbb E\|f_{2d}\|_2^2\le \left((31/32)^{d-m}+16d2^{-m}+256dn2^{-2m}\right)\|f_0\|_2^2. \tag{40}\] Each term is \(o(n^{-1/256})\): for the first use \((31/32)^{d-m}\le e^{-d/128}\), while the others have powers at least \(3/4\) and \(1/2\), up to polynomial factors in \(d\). This proves (38). Iterating \(2048\) two-sweep blocks gives energy \(n^{-8}\), and Lemma 21 gives the stated marginal error. ◻

Proof. Condition on the configuration after coordinate \(j\). The remaining layers use independent switch arrays in the \(s\) transverse fibers, each of size \(n/s\). The final entry at the one site where a fiber meets \(B\) has conditional mean equal to that fiber’s mean signed weight and second moment at most its mean squared weight, by (35). The sum of these means is \((s/n)\sum_x f(x)=0\). Independence between fibers therefore bounds the conditional second moment of \(S_B\) by \((s/n)\) times the energy at the conditioning time, which is at most \(E_0\).

The availability indicators at those \(s\) sites are likewise independent under this conditioning. Their total mean is \(\mu=|F|s/n\ge\varepsilon s\). Hoeffding’s inequality (Lemma 4) bounds a downward deviation of at least \(\varepsilon s/2\) by \(e^{-\varepsilon^2s/2}\). Alternatively, for their sum \(J\), independence gives \(\mathbb Ee^{-J}\le e^{-(1-e^{-1})\mu}\), and hence \(\Pr(J<\mu/2)\le e^{-(1/2-e^{-1})\mu}\). ◻

Proof. The child blocks use independent switch arrays before merging. The averaging identities in (35) give, at each site of child \(i\), expected availability \(m_i/s\) and expected signed weight \(S_i/s\). No equality between the individual sites’ second moments is needed. On an edge with weights \(a,b\) and availability indicators \(q_a,q_b\), the energy loss is \((q_ba^2+q_ab^2-2ab)/2\). Independence across children and summation over their \(s\) paired sites give expected loss \[\frac{m_1\overline E_0+m_0\overline E_1-2S_0S_1}{2s},\] which proves the identity. ◻

Proof. Put \(k=\lfloor d/2\rfloor\), \(L=2^k\), and \(M=2^{d-k}\), and denote the first-sweep output by \((F^*,f^*)\). Sum the moment bound in Lemma 23 over the \(M\) level-\(k\) blocks. Its exponential tail, using \(1/2-e^{-1}>1/8\), and a union bound give \[ \Pr(\mathcal G^c)\le M e^{-pL/8},\qquad \mathbb E\sum_B S_B^2\le\|f_0\|_2^2,\qquad \mathcal G=\{|F^*\cap B|\ge pL/2\text{ for every }B\}. \tag{43}\] For each first-sweep output in \(\mathcal G\), write \(f^*=u+w\), where \(u\) has constant value \(S_B/|F^*\cap B|\) on each \(F^*\cap B\). This is an orthogonal decomposition, \(w\) has zero sum in each block, and \[\|u\|_2^2=\sum_B\frac{S_B^2}{|F^*\cap B|} \le\frac{2}{pL}\sum_BS_B^2.\] Run \(w\) through the second sweep. After the first \(j\ge k\) coordinates, its expected value at each site is zero and the probability of availability is at least \(p/2\). Different level-\(j\) blocks have evolved independently, so at the next merging pair the expected product of weights is zero. In the energy-loss formula the opposite flag multiplies each squared weight independently, with expectation at least \(p/2\). The expected energy hence contracts by \(1-p/4\) for each of the last \(d-k\) layers. The \(u\) component cannot increase in norm. Using \(\|u_{\rm out}+w_{\rm out}\|_2^2\le2\|u_{\rm out}\|_2^2+ 2\|w_{\rm out}\|_2^2\), and monotonicity outside \(\mathcal G\), proves \[ \mathbb E\|f_{2d}\|_2^2\le \left(Me^{-pL/8}+2(1-p/4)^{d-k}+\frac4{pL}\right)\|f_0\|_2^2. \tag{44}\] Here \((1-p/4)^{d-k}\le e^{-d/128}\), and the other terms decay faster than \(n^{-1/256}\). Thus their sum is at most \(n^{-1/256}\) eventually. After \(1024\) two-sweep blocks the energy is at most \(n^{-4}\); Lemma 21 proves the conclusion. ◻

Proof. For level-\(i\) blocks \(B\) of size \(2^i\), define \[S_i(f)=2^{-i}\sum_B\left(\sum_{x\in B}f(x)\right)^2.\] The block statistics of Lemma 23, now applied at every level \(i\), give \[ \mathbb ES_i(f^*)\le2^{-i}\|f_0\|_2^2,\qquad \Pr\{\text{some level-$r$ block has density below }p/2\} \le2^{d-r}e^{-p2^r/8}. \tag{46}\] Indeed each level-\(i\) block meets every transverse fiber once. Lemma 23, summed over the \(n/2^i\) blocks, gives the first bound. For the second, its proof gives a sum of independent availability indicators of mean at least \(p2^r\); the Bernoulli lower-tail bound used in (43) and a union bound suffice.

Condition now on \(f^*,F^*\) with all level-\(r\) block densities at least \(p/2\). Their unions have the same lower density bound. In the second sweep, Lemma 24 therefore multiplies each child energy by at most \(1-p/4\). Its signed cross term is bounded using \(2S_{B_0}S_{B_1}\le S_{B_0}^2+S_{B_1}^2\). Summing over merges of level-\(i\) blocks, and writing \(E_i\) for the energy after \(i\) layers of this sweep, gives \[\mathbb E(E_{i+1}\mid f^*,F^*) \le(1-p/4)\mathbb E(E_i\mid f^*,F^*)+\frac12S_i(f^*), \qquad r\le i<d.\] Iterate, discard the contraction factors on the nonnegative additive terms, use (46), and use pathwise monotonicity on the excluded event. The geometric sum \(\frac12\sum_{i=r}^{d-1}2^{-i}\le2^{-r}\) proves (45). Its first term is at most \(n^{-2\gamma_p}\); the other terms are \(O(n^{-1/2})\) and exponentially small in \(\sqrt n\), respectively. Since \(\gamma_p<1/2\), their sum is at most \(n^{-\gamma_p}\) eventually. Also the first term is at most \(e^{-pd/8}=n^{-p/(8\log2)}\), whose exponent exceeds \(p/16\), proving the alternative assertion. ◻

Proof. For a level-\(s\) block \(B\) put \(p_B=|B|/n\). Membership in \(B\) means that the last \(d-s\) output bits equal its prescribed suffix. Every card has membership probability \(p_B\). To compare two distinct cards, let \(i\) be their largest initially differing coordinate. Before layer \(i\), they use distinct switches, so their output bits are independent fair bits. At layer \(i\) they use one switch exactly when their earlier output prefixes agree; that switch forces opposite outputs. After layer \(i\) their prefixes are distinct, and they use distinct switches for the rest of the sweep.

If \(i\le s\), the only possible shared switch is in an unconstrained coordinate. All prescribed suffix bits are then sampled at distinct switches, and joint membership has probability \(p_B^2\). If \(i>s\), condition on both cards having the prescribed outputs at coordinates \(s+1,\ldots,i-1\). Their first \(s\) outputs remain independent uniform strings, so their prefixes agree with probability \(2^{-s}\). On this event joint membership is impossible at layer \(i\); off it both prescribed outputs occur with probability \(1/4\). The remaining prescribed bits are again sampled at distinct switches. Thus joint membership has probability \(p_B^2(1-2^{-s})\le p_B^2\). In either case the membership indicators have nonpositive covariance.

Let \(C\) be the covariance matrix of the membership indicators of all \(n\) initial labels. Their sum is the fixed number \(|B|\), so \(C\) has zero row sums. Its off-diagonal entries are nonpositive, and its diagonal is at most \(p_B\). Therefore \[v^TCv=\sum_{x<y}(-C_{xy})(v_x-v_y)^2 \le2p_B\sum_xv_x^2.\] Let \(h_B\) count the cards that start in \(F_0\) and end in \(B\), and let \(u_B\) be the sum of averaged loads there. It follows that \[ \mathbb Eh_B=p_B|F|,\qquad \operatorname{Var}(h_B)\le p_B|F|,\qquad \mathbb Eu_B^2\le2p_B\|f_0\|_2^2. \tag{48}\] For the last estimate, give the card initially at \(a\in F_0\) the deterministic signed weight \(f_0(a)\), and give every observed card, initially outside \(F_0\), weight zero. If \(g_t\) is the actual position permutation, the transported load is \(\widetilde f_t(x)=f_0(g_t^{-1}x)\), with \(f_0\) extended by zero. Fix a feasible history \(\mathcal H\) of all observed-card trajectories through the first sweep. Lemma 2 leaves the unvisited switches independent and fair, including an earlier unvisited switch when later observed paths are specified. The additional step here is to apply that conditional-flow rule to arbitrary signed loads. At a pair with two available inputs, averaging that unvisited fair coin averages the two incoming expected loads. At a pair with one available input, the observed trajectory determines its available output, so its load is transported to that output. Induction over layers, using linearity for the signed weights, therefore gives \[ f_t(x)=\mathbb E[\widetilde f_t(x)\mid\mathcal H],\qquad u_B=\mathbb E\!\left[\sum_{a\in F_0}f_0(a) \mathbf1_{\{g_d(a)\in B\}}\, \middle|\,\mathcal H\right]. \tag{49}\] Each initial label has probability \(p_B\) of ending in \(B\), and \(\sum_a f_0(a)=0\), so the unaveraged sum has mean zero and second moment \(f_0^TCf_0\le2p_B\|f_0\|_2^2\). Conditional Jensen proves the asserted bound for \(u_B\) for every signed initial load.

If \(\delta=1\), every position is available, so one sweep applies all coordinate averages and sends the zero-sum vector to zero. The list statement then concerns the empty list and is exact. For the remaining argument assume \(0<\delta<1\).

Put \(s_0=\lfloor3d/4\rfloor\). Chebyshev gives probability at most \(4/(\delta2^s)\) that a fixed level-\(s\) block has \(h_B<\delta2^s/2\). There are \(n/2^s\) such blocks. Summing over \(s\ge s_0\) bounds the failure probability by \(O_\delta(n2^{-2s_0})=O_\delta(n^{-1/2})\). Condition on a first-sweep output outside that event. At a second-sweep merge of children \(L,R\) of size \(m=2^{s-1}\), write \(b_L=u_L/h_L\), \(b_R=u_R/h_R\) for their means over available positions. Let \(V_L,V_R\) be their expected squared deviations from these means immediately before the merge, and \(V_B\) the corresponding parent quantity. Subtracting the parent mean energy from the common block-merging identity, Lemma 24, gives \[\begin{align*} V_B={}&\left(1-\frac{h_R}{2m}\right)V_L+ \left(1-\frac{h_L}{2m}\right)V_R\\ &+\left(1-\frac{h_L+h_R}{2m}\right) \frac{h_Lh_R}{h_L+h_R}(b_L-b_R)^2. \tag{50}\end{align*}\] To verify it, the premerge total energy is \(V_L+V_R+h_Lb_L^2+h_Rb_R^2\); the expected loss is \([h_RV_L+h_LV_R+h_Lh_R(b_L-b_R)^2]/(2m)\). Subtract the parent mean term \((h_Lb_L+h_Rb_R)^2/(h_L+h_R)\) to obtain the formula. All denominators are positive on the retained event.

For \(s>s_0\) the first two coefficients are at most \(1-\delta/4\). The last term is nonnegative and at most \(u_L^2/h_L+u_R^2/h_R\). Iterating to the root, whose load mean is zero, bounds the final conditional energy by \[(1-\delta/4)^{d-s_0}\|f_0\|_2^2+ \sum_{s=s_0}^{d-1}\frac{2}{\delta2^s} \sum_{|B|=2^s}u_B^2.\] For each level (48) bounds the expectation of the inner sum by \(2\|f_0\|_2^2\). Use monotonicity on the discarded event. The resulting two-sweep factor is \[ (1-\delta/4)^{d-s_0} +O_\delta(2^{-s_0})+O_\delta(n2^{-2s_0}). \tag{51}\] Its leading term is at most \(n^{-2a}\) for the stated \(a\), and the two other terms are \(O_\delta(n^{-3/4})\) and \(O_\delta(n^{-1/2})\). This proves the claim. By Lemma 21, any fixed \(R\) with \(aR>3\) now suffices for the asserted large-list mixing. ◻

Proof. The input marginal errors follow from Lemma 21. The coarse and centered bounds are those of Propositions 22 and 25. For the multilevel row, Proposition 26 gives energy \(n^{-h\gamma}\) and marginal error \(\varepsilon_n\le\tfrac12n^{(3-h\gamma)/2}=o(1)\). For translation symmetry, (47) has exponent \(p/16=1/2048\), so \((p/16)R=8\) and the marginal error is \(\tfrac12n^{-5/2}\). The last row has error \(\tfrac12n^{(3-a(1/8)R)/2}=o(1)\). Each bound is uniform, so any fixed partition into the indicated \(r\) equal blocks supplies all the complementary marginals.

Use the simultaneous trimming operations of Section 6.3. For the first row, excess trimming followed by normalization gives cap \(2\) eventually. For the fourth and fifth, heavy-coset deletion and normalization give caps \(4\) and \(3\). These probability laws are within \(o(1)\) of their original block laws. The second and third rows retain cap-one subprobabilities before their different completions.

Substituting the table’s caps, block counts and reciprocal-degree parameters in the preceding three transfer formulas gives its Fourier bounds. The exponents \(\kappa\) follow from \(D\|M^\ell\|_{\mathrm{HS}}^2\le D^2\|M\|_{\mathrm{op}}^{2\ell}\). Their sums tend to zero by the respective reciprocal-degree estimates at powers \(1,4,8,6,2\) in [14].

For the multilevel row, the cap-one construction loses mass \(\delta\le32\varepsilon_n\). Restore it as \(\eta=\nu+\delta U_G\). Every nontrivial Fourier matrix of \(\eta\) equals that of \(\nu\), so the table’s orbit bound still applies, and \(\|\eta-\mu\|_{\mathrm{TV}}\le\delta=o(1)\) for the original block law \(\mu\). Thus this row, like the first, fourth and fifth, meets the probability completion of Section 3.3: the original law has zero sign expectation, the nearby probability has sign coefficient \(o(1)\), and replacing the fixed number of factors costs \(o(1)\).

The centered row instead convolves the cap-one subprobability itself. Write \(z=\nu(G)\to1\). Domination by the original unbiased-sign block law gives \(|\widehat\nu(\mathop{\mathrm{sgn}})|\le1-z\). Its nonsign contribution is bounded by \((16C_4)^{16}\sum_{D>1}D^{-8}=o(1)\). Equation (25) therefore gives \(\|\nu^{*16}-z^{16}U_G\|_1=o(1)\). The positive difference \(\mu^{*16}-\nu^{*16}\) has mass \(1-z^{16}\le16(1-z)=o(1)\), which restores the original probability law.

Finally each block contains a whole number of sweeps, so the physical time is \(\ell T\), as tabulated. Translation by a deterministic initial deck preserves the distance from uniform. ◻

Proof. Condition on the observed paths through \(t\). Let \(K_t\) be the random kernel from the old available set to the new one: its rows are uniform on pairs with two available endpoints and deterministic at a single available endpoint, with its destination specified by the fresh observed movement. Expand the autocorrelation of \(f_tK_t\). This is a sum over two available starting endpoints \(x,y\), weighted by \(f_t(x)f_t(y)\), of the law of the difference of two independent draws from their rows, conditional on \(K_t\). For endpoints in distinct pairs, their fresh pair data are independent; after averaging the fresh coins, their difference has kernel \(L_{h(t)}\). For two endpoints in the same pair with two available inputs, including \(x=y\), the two row draws are independent uniform draws, so the same conclusion holds. The only exception is \(x=y\) with its partner observed. Both row draws then equal the same deterministic destination. Their difference is zero rather than the fair choice between \(0\) and \(e_{h(t)}\). Summing these corrections gives (56).

The product of all \(d\) coordinate-reset kernels maps a signed row to its total mass times uniform; it therefore kills \(v_{t-d}\). A correction created at step \(s\), \(t-d\le s<t\), has not yet had its own coordinate reset again. Subsequent resets transfer a fraction \(2^{-(t-1-s)}\) of \(\delta_0\) to zero, and transfer none of \(\delta_{e_{h(s)}}\) to zero. Including the prefactor \(1/2\) and summing all \(d\) corrections gives (57). ◻

Proof. The autocorrelation notation has \(r_t=a_t\) and \(b_t=w_t\) from Section 3. There are at most \(7n/8\) blockers, so Lemma 6 with \(\alpha=1/8\) gives (58). Its independence step is the exact opposite-half identity \[ \mathbb E\!\left[\sum_{x\in H_0}f_s(x)^2 \mathbf 1_{\{x\oplus e_{h(s)}\in O_s\}} \,\middle|\,\mathcal F_{s-d+1}\right] =\frac{|O_{s-d+1}\cap H_1|}{n/2} \mathbb E\!\left[\sum_{x\in H_0}f_s(x)^2 \,\middle|\,\mathcal F_{s-d+1}\right], \tag{60}\] where \(H_0,H_1\) are the two coordinate-\(h(s)\) halves. The conditioning time is just after that coordinate’s preceding update; only the subsequent independent arrays in the two halves are averaged here.

Insert (58) into the autocorrelation memory identity. The comparison (11) applies with \(\rho=\theta\), \(\eta=\epsilon_n\), \(t_0=2d\), and \(\gamma=63/64\), since \(\theta/(2\gamma-1)=30/31<1\). This proves the first energy bound. At \(t=1026d\), \(\gamma^{1024d}\le e^{-16d}\le n^{-16}\), and \(\epsilon_n/(1-\theta)\le n^{-16}\) eventually, giving the last bound. ◻

Proof. For each \(0\le j<q\), construct \(f_T^{(j)}\) by observing the first \(j\) paths and centering the conditional law of card \(j+1\). Let \(E_j=\{\max_x|f_T^{(j)}(x)|\le n^{-3}\}\), an event measurable from those \(j\) paths. The energy bound and Markov’s inequality give \(\Pr(E_j^c)\le2n^{-10}\). Take \(E=\bigcap_{j<q}E_j\).

To bound the probability for the first \(j+1\) targets and events \(E_0,\ldots,E_j\), condition on the first \(j\) trajectories. The preceding target constraints and those events are measurable there. On \(E_j\) the next target has conditional probability at most \[\frac1{n-j}+n^{-3}\le\frac{1+n^{-2}}{n-j}.\] After applying this upper bound, drop \(E_j\) and repeat for the preceding \(j\) targets and events. Induction gives (61). This argument retains subprobabilities throughout; it never asserts that the one-card estimates survive conditioning on the entire event \(E\). ◻

Proof. For each \(i\) take a fixed ordered list of the complement of \(D_i\) and apply Lemma 33 in the same forward shuffle space. Intersect the eight retained events and let \(\beta\) be the law of the endpoint permutation on this intersection. Its lost mass is at most \(16n^{-9}\). The image constraints are the coset \(gH_i\), so inclusion and (61) give \[\beta(gH_i)\le\frac{(1+n^{-2})^{7n/8}}{[G:H_i]}.\] Since \((1+n^{-2})^{7n/8}\le2\) for large \(n\), this is the second cap.

For the first cap, use the law of the inverse permutation. A physical \(T\)-step block is a product of complete cyclic coordinate sweeps with no residual rotation. Every matching layer is an involution, and all layers are independent; hence its inverse law is generated by the same layers in reverse order. The reversed order is again a periodic coordinate schedule, to which Lemma 33 applies. Intersect its eight events, producing a subprobability \(\widetilde\alpha\le\mathcal L(g^{-1}:g\sim\mu)\), then push it forward under inversion to obtain \(\alpha\le\mu\). The image constraint for \(g^{-1}\) becomes the preimage constraint for \(g\), whose fiber is \(H_ig\). Consequently \(\alpha(H_ig)\le2/[G:H_i]\), the first cap. To check the density normalization explicitly, \[\int_{H_i}A(h^{-1}g)\,dh=[G:H_i]\alpha(H_ig),\qquad \int_{H_i}B(gh^{-1})\,dh=[G:H_i]\beta(gH_i).\] Thus the two laws may differ, but each is dominated by the same physical block law, on the required side of multiplication. ◻

Proof of Theorem 30. Let \(\mu=q_d^{*1026d}\), where \(q_d\) is the law of one physical shuffle. Lemma 34 gives \(\alpha,\beta\le\mu\), each of mass at least \(1-16n^{-9}\). Thus \(\beta*\alpha\le\mu*\mu\) has mass \(1-O(n^{-9})\); its density relative to uniform is \(B*A\), with transform \(\widehat B(\lambda)\widehat A(\lambda)\). The displayed product bound and weighted reciprocal sum show that all nontrivial, nonsign Plancherel terms sum to \(o(1)\). The trivial coefficient is the total mass, which tends to one. The law \(\mu\) has zero sign expectation, and domination implies \(|\widehat\alpha(\mathop{\mathrm{sgn}})|,|\widehat\beta(\mathop{\mathrm{sgn}})|\le16n^{-9}\). Their product therefore also tends to zero. Plancherel gives \(\|B*A-1\|_{L^2(U_G)}=o(1)\), and Cauchy–Schwarz gives the same in \(L^1(U_G)\). Restoring the missing \(O(n^{-9})\) mass proves \(\|\mu*\mu-U_G\|_{\mathrm{TV}}=o(1)\).

The block length is a multiple of \(d\), so \(\mu*\mu=q_d^{*2052d}\) in physical time. Translation by any initial deck preserves the conclusion. The support bound from the opening argument gives \(t_{\mathrm{mix}}(d)\ge d\) for large \(d\), completing the stated two-sided estimate. ◻

Proof. The conditional one-card error is \(\mathbb E\|x_T\|_1/2\le\sqrt{|H_T|\mathbb EE_T}/2\le\sqrt{na}/2\). Lemma 3 sums these errors, first coarsening the preceding paths to their endpoints. Averaging the resulting inequality over the initial list gives the last assertion. ◻

A symmetry proof of Lemma 23. Fix \(B\in\mathcal B_j\), put \(s=2^j\), and let \(m\) be the conserved number of available positions. Immediately after updating coordinate \(t\), the law is invariant under swapping any chosen set of its matching edges: edges with one available position have independent symmetric outputs and outputs on edges with two available positions are equal. A symmetry that preserves the later matchings remains a symmetry through the later updates. In particular, after a sweep its law is invariant under independently translating the suffix \((j+1,\ldots,d)\) at each fixed length-\(j\) prefix. To verify this assertion, flip one coordinate \(t>j\) on all sites with a given prefix. This is a union of coordinate-\(t\) edges, and it preserves every later matching. Such flips generate all the asserted suffix translations.

Apply independent uniform suffix translations to an already completed configuration. Conditional on that configuration, the entries selected for \(B\) sample one site uniformly and independently from each prefix fiber. Their signed sum has mean zero and variance at most \(sE_0/n\); their available count is a sum of independent indicators with mean \(ms/n\). The translated configuration has the original law, so the same variance and exponential-moment estimates prove the lemma. This argument establishes the needed transitivity without asserting independence among the entries of the original completed sweep. ◻

Proof. Call the first-sweep output good if every block of level at least \(h\) has available-position density at least \(\varepsilon/2\). Lemma 23 and a union bound give the displayed exceptional probability. Conditional on a good output, let \(F_j\) be the expected energy after \(j\) layers of the second sweep. The merging identity and \(2M_1M_2\le M_1^2+M_2^2\) give \[F_{j+1}\le\sigma F_j+2^{-j-1}\sum_{B\in\mathcal B_j}M_B^2, \qquad h\le j<d.\] We have \(F_h\le E_0\) and \(\mathbb E\sum_{B\in\mathcal B_j}M_B^2\le E_0\) by (41). Iterate the inequality, bound its geometric weights by one, and sum \(\sum_{j=h}^{d-1}2^{-j-1}\le2^{-h}\). On the exceptional event use \(E_{2d}\le E_0\). This proves (64). Its first term has exponent \(-\tfrac12\log_2\sigma\), its second has exponent \(1/2\), and the final term decays faster than every power of \(n\). For \(\varepsilon=1/16\), \(-\tfrac12\log_2(63/64)>1/200\), proving the last assertion. ◻

Proof. Given the complete exposed paths, let \(M(u,v)\) be the conditional transition probability for a hidden tag from \(u\) to \(v\). Linearity of the signed flow gives \[x_d(v)=\sum_{u\in H}x(u)M(u,v).\] Consequently the coefficient \(\mathbb E\sum_vM(u,v)M(z,v)\) in its expected squared norm is a collision probability: sample the exposed paths with their actual law, and then sample two walkers independently conditional on those paths, starting at \(u,z\in H\).

We analyze this joint law chronologically. Generate the physical switches and the resulting available sets in layer order. On a pair with one available input, both walkers use its forced available output if they are there. On a pair with two available inputs, each walker uses its own extra fair coin, independent of every physical switch and of the other walker’s coins. Conditional on the complete exposed paths, this construction gives exactly two independent copies of \(M\), by Lemma 2. In the following calculation we average over the paths; we do not retain full-path conditioning when invoking independence of physical switch arrays.

For \(u\ne z\), let \(i\) be their largest differing coordinate, and for \(u=z\) put \(i=0\). Before coordinate \(i\), they use distinct matching pairs. Each updated bit is fair, and the two bits are independent given the preceding chronological history. If their first \(i-1\) outputs agree, their coordinate-\(i\) inputs form a pair of available sites. Their independent auxiliary choices then agree with probability \(1/2\). Their probability of agreement through coordinate \(i\) is therefore \(2^{-i}\).

Now take \(j>i\). Reveal the physical switches in the block \(C_{j-1}(u)\) during its first \(j-1\) layers and the auxiliary choices of both walkers through that time. Their histories are confined to this block, so this information determines whether they agree and, on agreement, their common address. No switches in its sister block \(C_j(u)\setminus C_{j-1}(u)\) have been revealed. Those switches are independent of the revealed information. Each site of the sister block has expected availability equal to its initial density \(\eta_j(C_i(u))\), since its first \(j-1\) coordinate averages have all been applied. This holds in particular at the now determined partner address.

If that partner is unavailable, the common input has a forced output and the walkers stay together. If it is available, their independent auxiliary choices agree with probability \(1/2\). Hence each level \(j>i\) contributes the factor \(1-\eta_j(C_i(u))/2\). Any disagreement in a processed coordinate is permanent within the sweep. Multiplying the successive conditional probabilities gives \[\mathbb E\sum_vM(u,v)M(z,v)=2^{-i}s_H(C_i(u)),\] including \(i=0\). Group the ordered off-diagonal pairs by their largest differing coordinate. The two orders of each pair give the coefficient \(2^{1-i}\) in (67). ◻

Proof. At every fixed time the available set is a uniform \(m\)-subset: after fixing all switches the shuffle is a permutation independent of the random initial list. This is an unconditional statement. Call an available set good if every block of level at least \(b\) has density at least \(\varepsilon/2\). It suffices by coupling to consider \(m=\varepsilon n\). A Bernoulli-\(\varepsilon\) subset conditioned on size \(\varepsilon n\) is uniform, and this conditioning event has probability at least \(1/(n+1)\) because \(\varepsilon n\) is a mode of the binomial distribution. The exponential-moment estimate in Lemma 23, followed by a union bound over fewer than \(2n\) blocks, gives \(\Pr(H_t\text{ not good})\le\Delta_n\).

Put \(w=x_{t+d}\). On a good second-sweep input, \(s_{H_{t+d}}(B)\le(1-\varepsilon/4)^{d-b}\) for every level at most \(b\). In (67) use \(2w(B_0)w(B_1)\le w(B_0)^2+w(B_1)^2\). At levels \(1\le i\le b\), \(\sum_{C\in\mathcal B_{i-1}}w(C)^2\le2^{i-1}\|w\|_2^2\); each such level contributes at most half the common factor times energy. The remaining levels contribute at most \(\sum_{i=b+1}^d2^{-i}\sum_{C\in\mathcal B_{i-1}}w(C)^2\). On failure of goodness, use \(E_{t+2d}\le1\). Apply the block-variance bound conditionally over the first sweep to each last sum; after summing over a partition its expectation is at most \(\mathbb E E_t\). This proves (68) without assuming that energy and goodness are independent.

For \(\gamma=\varepsilon/16\), the bracket is at most \(n^{-\gamma}\) for all sufficiently large \(d\): its first term is at most \((1+b/2)e^{-\varepsilon d/8}\) and its second is at most \(2n^{-1/2}\). Iteration through \(R\) sweep pairs gives \(\mathbb E E_T\le n^{-R\gamma}+R\Delta_n=n^{-8}+R\Delta_n\). The last term decreases faster than every power of \(n\). Lemma 35, averaged over lists, now proves the assertion. ◻

Proof. Apply Lemma 5 with \(f_t=x_t\), \(V_t=H_t\), and \(w_t=\mathbb EI_t\) to obtain (69). The opposite-half factorization of Lemma 16 holds also with the larger past field \(\mathcal F_{t-d+1}\): after that time the two halves use independent fresh switch arrays, and the path-defined vector in either half is a function of its own array. It remains to supply a lower bound on both available densities at that conditioning time.

The available-count argument in the proof of Lemma 17 bounds the chance that either half has fewer than \(m/4\) available positions by \(2e^{-m/8}\le2e^{-\varepsilon n/8}\). Off that event, both densities are at least \(\varepsilon/2\). The factorization and \(E_t\le1\) on the exception give the first row. For the second row, Lemma 6 with \(\alpha=\varepsilon\) gives \(\mathbb EI_t\le(1-\varepsilon/2)a_t+2e^{-\varepsilon^2n/4}E_0\); use \(E_0\le1\).

Finally use (11) with \(\rho=\gamma\), \(\eta=B_n\), \(t_0=2d\), and decay parameter \(\beta\). Its condition \(\rho/(2\beta-1)\le1\) is exactly the stated hypothesis. ◻

Proof. For each complement fix an ordering \(z_1,\ldots,z_{n-n/16}\). For its \(j\)th card let \(G_{i,j}\) be the event that the conditional final energy given the preceding paths is at most \(n^{-4}\). The iterated energy bound and Markov’s inequality give \(\Pr(G_{i,j}^c)\le n^{4-bk}\). The event is measurable from those preceding paths. On it each conditional endpoint probability is at most \[(n-j+1)^{-1}+n^{-2}\le\frac{1+1/n}{n-j+1}.\] Intersect all these events over the sixteen orderings, obtaining \(G_*\) with probability \(\theta\) and the stated bound on \(\delta\).

Fix one ordering and a tuple of distinct target endpoints. Drop the events from the other orderings. Condition on the first \(j-1\) full paths to bound the last target endpoint on \(G_{i,j}\); then drop \(G_{i,j}\) and repeat backwards. Every conditioning uses the original shuffle law and an event measurable from the preceding paths. The probability of the target tuple together with \(G_*\) is consequently at most \[\frac{(1+1/n)^{n-n/16}}{(n)_{n-n/16}}\le\frac e{(n)_{n-n/16}}.\] Let \(\nu\) be the endpoint law conditional on the trajectory event \(G_*\). Right convolution by \(U_{K_i}\) fills each endpoint fiber uniformly, and each fiber has \((n/16)!\) elements. This gives the density bound. Conditioning on an event of probability \(\theta\) changes TV by at most \(\delta\); the zero sign mean under \(\mu\) gives the final estimate by splitting its expectation over \(G_*\) and its complement. ◻

Proof. Write \(a=|C_0|=|C_1|\), and temporarily shorten subscripts to \(0,1\). Since \(\alpha_i=m_i/a\), Lemma 24 reads \[E_C=(1-\alpha_1/2)E_{C_0} +(1-\alpha_0/2)E_{C_1}+S_0S_1/a.\] We separate from each energy the squared mean on its available sites. When both counts are positive, \[D_C=\frac{m_0m_1}{m_0+m_1} \left(\frac{S_0}{m_0}-\frac{S_1}{m_1}\right)^2,\] and direct multiplication gives \[\alpha_C D_C=\frac12\left( \alpha_1\frac{S_0^2}{m_0}+\alpha_0\frac{S_1^2}{m_1}\right) -\frac{S_0S_1}{a}.\] Subtracting the baseline \(S_C^2/m_C\) proves (80). If a child is empty, \(D_C=0\) and the same identity holds using the declared zero convention.

At a singleton \(W_C=0\). Expanding the recursion from the root down therefore gives (81); at the root the baseline vanishes because the total signed sum is zero. Finally every non-root baseline in the sum of (79) occurs once with each sign. The surviving leaf terms sum to \(\sum_xf(x)^2\), and the root term is zero. This proves (82). ◻

Proof. Fix the functions in (83). Let \(g_{<i}\) transform only coordinates \(1,\ldots,i-1\) according to those functions, leaving coordinates \(i,\ldots,d\) unchanged. It bijects the coordinate-\(i\) matching edges. If an old edge \(e\) has prefix \(u=(x_1,\ldots,x_{i-1})\) and coin \(\omega_i(e)\), define the new coin by \[\omega_i'(g_{<i}e)=\omega_i(e)\oplus F_i(u).\] The prefix here is the original one, recoverable from its transformed image because \(g_{<i}\) is invertible. This is a deterministic bijection and toggling of the layer’s independent fair bits, so all modified layer arrays have their original joint law.

Inductively the input to the modified layer is the old input with the earlier coordinates transformed. At an edge with one available input position, the toggled coin transports that position and its weight to the image under the first \(i\) transformed coordinates. At an edge with two available input positions the two new weights are equal, so the same assertion holds. It is immediate on an empty edge. After the last layer the modified output is precisely the \(g\)-image of the original output. Since the coin laws agree, their output laws agree. ◻

Proof. First fix a coordinate block of size \(u=2^j\). Condition on the automorphism’s action through depth \(j\). Each source subtree with fixed first \(j\) bits maps to one target subtree of that depth. The actions inside these subtrees are independent uniform automorphisms. Thus the preimages of the block’s \(u\) leaves select one uniform leaf independently from each source subtree, each of size \(n/u\).

The hidden count \(X\) in the transformed block is a sum of independent indicators with mean \(z=|H|u/n\ge cu\). Multiplication of their exponential moments gives \(\mathbb E_g 2^{-X}\le e^{-z/2}\). Markov’s inequality yields \[\Pr_g(X<cu/2)\le\Pr_g(X\le z/2) \le 2^{z/2}e^{-z/2}\le e^{-z/8}\le e^{-cu/8}.\] There are fewer than \(2n\) coordinate blocks, so a union bound proves the density assertion. For the signed sum, the sum of the sampled means is \((u/n)\sum_xf(x)=0\). Independence gives variance at most the sum of the sampled second moments, namely \((u/n)\sum_xf(x)^2\). Taking \(u=s\) proves (84). ◻

Proof of Theorem 41. First randomize the input by uniform \(g\) and consider the density event in Lemma 44. On this event, every term of (81) with \(|C|\le s\) has \(\log_2(n/s)\) ancestors of sizes \(2s,4s,\ldots,n\). Their sibling blocks have size at least \(s\), hence density at least \(c/2\). Its multiplier is therefore at most \((1-c/4)^{\log_2(n/s)}\). By (82), the sum of all its nonnegative \(D_C\) terms is at most \(\mathcal E(H,f)\).

For \(|C|>s\), discard the multipliers. The corresponding details telescope to \(\sum_{|C|=s}S_C^2/m_C\), since the total signed sum is zero. On the density event this is at most \((2/(cs))\sum_{|C|=s}S_C^2\). There are \(n/s\) such blocks; their second-moment bounds in (84) sum to at most \(\mathcal E(H,f)\). On the exceptional event use the unconditional bound \(\Phi\le\mathcal E(H,f)\). Hence \[ \mathbb E_g\Phi(gH,gf) \le\left[(1-c/4)^{\log_2(n/s)}+\frac{2}{cs} +2n e^{-cs/8}\right]\mathcal E(H,f) \le n^{-1/64}\mathcal E(H,f) \tag{85}\] for sufficiently large \(d\). Indeed the first term is at most \(e^{-cd/8}\), whose exponent in \(n\) is \(c/(8\log2)>1/64\), and \(s\ge\sqrt{n/2}\) makes the other terms smaller than that power eventually. This threshold depends on no input data.

At each boundary after at least one sweep, the law of \((H,f)\) is invariant under an independent uniform \(g\) by Lemma 43. The next sweep uses fresh switches in the same order. Thus its expected output energy is \[\mathbb E\Phi(H,f)=\mathbb E_{(H,f)}\mathbb E_g\Phi(gH,gf) \le n^{-1/64}\mathbb E\mathcal E(H,f).\] This uses invariance of the boundary law, not invariance of each realized configuration. The first sweep does not increase energy. Iteration proves (78) for every \(b\ge1\). ◻

Proof. Let \(Y_1,\ldots,Y_k\) be the image positions. The entropy chain rule expresses the deficit from \(\log(n)_k\), where \((n)_k=n(n-1)\cdots(n-k+1)\), as \[\sum_{i=1}^k\bigl[\log(n-i+1)-\mathsf H(Y_i\mid Y_1,\ldots,Y_{i-1})\bigr].\] Here \(\mathsf H\) is Shannon entropy. Refining the conditioning to the complete paths of the preceding labels can only lower this conditional entropy. Their endpoint complement has \(m=n-i+1\ge n/4\) sites. For the conditional probability \(p\) there, \(\log z\le z-1\) gives \[D(p\|U_H)=\sum_{x\in H}p(x)\log(mp(x)) \le m\sum_{x\in H}(p(x)-1/m)^2.\] The initial centered tag energy is \(1-1/m\le1\). Applying Theorem 41 at each exposure and summing at most \(n\) contributions, each with \(m\le n\), proves (86). This also covers the empty list.

For completeness, \(D(p\|q)\ge2\|p-q\|_{\mathrm{TV}}^2\) follows by the log-sum inequality applied to \(\{p>q\}\) and its complement. The resulting binary relative entropy, as a function of its first mass, has second derivative at least \(4\), minimum zero at the reference mass, and zero first derivative there. Integrating this bound, with endpoint values obtained by continuity, proves the inequality. With \(b=1+12\cdot64=769\), the entropy bound is \(n^{-10}\) and the claimed variation bound follows. ◻

Proof. The signed-palette lemma [14] gives an absolute constant \(C_{\rm pal}\): every irreducible half-group type \(\beta\) has a palette and a product of trivial or sign characters occurring in it, with \(h\mathcal H(p)\le C_{\rm pal}\log D_\beta\). Choose \(\delta<1/4\) so that \(2\delta C_{\rm pal}\le1/10\), and only then choose \(C_*\) in Proposition 52. Since \(v\le2\delta h\) and \(n^{-4}-\log z=o(1)\), (101) gives \[\nu(gH)\le \frac{2D_\beta^{1/10}}{[S_n:H]}\] for large \(n\). It holds for every placement of these color classes and hence every conjugate in either half-group. More precisely, (101), with \(\varepsilon_n=n^{-4}-\log z=o(1)\) and the chosen \(\delta\), verifies the full entropy-form hypotheses for every palette in the signed-palette transfer [14], whose conclusion is \[\|\widehat\nu(\lambda)\|_{\rm op}\le D_\lambda^{-1/6} \quad\bigl(\lambda\ne(n),(1^n)\bigr).\] Here \(D_\lambda\) is the irreducible degree and \(\widehat\nu(\lambda)=\sum_g\nu(g)\rho_\lambda(g)\) in a unitary model.

The original block has zero mean sign: conditioning on all but one coin in its final layer, flipping that coin composes the endpoint with a transposition. Clipping on settings therefore gives \(|\widehat\nu(\mathrm{sgn})|\le(1-z)/z=o(1)\). For thirty independent factors, Plancherel and \(\|M\|_{\rm HS}\le\sqrt{D_\lambda}\|M\|_{\rm op}\) bound the nontrivial, nonsign contribution by \[\sum_{\lambda\ne(n),(1^n)}D_\lambda^{2-30/3} =\sum_{\lambda\ne(n),(1^n)}D_\lambda^{-8}=o(1),\] using the reciprocal-degree conclusion proved in that theorem. The sign contribution also tends to zero. Thus \(\nu^{*30}\) tends to uniform in total variation. Replacing its thirty factors by \(\mu\) costs at most \(30(1-z)=o(1)\). Each factor has \(C_*d\) physical shuffles, and changing the starting deck translates the group law. This proves the claim. ◻

Proof. We first compare the xor of the two positions with an ideal chain that contracts over blocks of four sweeps. We then control the actual transition error by estimating coincidence and the joint event of coincidence with a repeated partner. Two inverse-\(n\) costs make this error small enough to telescope through the remaining kernels.

Write \(D_s\) for the binary xor of the walker position and the position of the baseline path of \(j\) immediately before layer \(s\). We generate the baseline chronologically, and reveal whether a label is active only when the walker queries it. Apart from \(j\), activity statuses are a uniform sample of \(m-1\) active labels from \(n-1\) possibilities. A partner’s identity is known before the current layer’s fresh coins are sampled, so such adaptive queries preserve sampling without replacement among unqueried labels. At most \(1+t\) labels are queried through time \(t\).

Consider layer \(s\) in direction \(i=i_s\). If \(D_s\notin\{0,e_i\}\), the two distinguished paths use distinct switches. Their new xor bit in coordinate \(i\) is fair, independently of the history, and the other bits are unchanged. If \(D_s=e_i\), the walker is paired with \(j\) and a fair toggle makes the new xor either \(0\) or \(e_i\). If \(D_s=0\), the new xor becomes \(e_i\) precisely when the partner of \(j\) is active and the walker toggles to it.

Define ideal kernels \(Q_s\) by the same rules, replacing the last activity probability by the constant \[p=\frac{m-1}{n-1}.\] They have a common stationary law \[\pi(0)=\frac1m,\qquad \pi(x)=\frac p m\quad(x\ne0).\] Indeed \(1+(n-1)p=m\). The edge \(\{0,e_i\}\) balances because \(\pi(0)p/2=\pi(e_i)/2\), and every other coordinate pair has equal masses and a fair refresh.

We need a uniform contraction estimate for products of these ideal kernels. Call a layer exceptional when its input is \(0\) or \(e_i\). Once a run of consecutive exceptional layers ends, its output is a singleton. That singleton bit cannot disappear until its coordinate is next updated, so there are at least \(d-1\) nonexceptional layers before a new exceptional run. A new run following these layers requires \(d-1\) specified zero outputs of fair refreshed bits and has probability at most \(2^{-(d-1)}\). A run continuing for at least \(d\) layers must keep outputting zero until its last layer; from any specified start its probability is at most \((1-p/2)^{d-2}\). This also covers the first singleton-to-zero move, whose probability \(1/2\) is no larger than \(1-p/2\).

In a block of \(4d\) layers, a union bound therefore gives, uniformly in the starting state, \[\mathbb P\{\hbox{an exceptional layer occurs in the last }d \hbox{ layers}\} \le C d\bigl(2^{-(d-1)}+(1-p/2)^{d-2}\bigr).\] A run that starts early and reaches the last \(d\) layers is long; a later start has the preceding \(d-1\) fair refreshes just described. Couple two ideal chains by common random bits, using the same refreshed bit whenever both are nonexceptional and keeping them together once they agree. If neither has an exception in the last \(d\) layers, all coordinates have been refreshed identically and the endpoints agree. Since \(p\ge\epsilon/2\) for large \(n\), there is an absolute \(\beta>0\) for which every \(4d\)-layer ideal product has total-variation contraction coefficient at most \(n^{-\beta}\).

We now compare the actual xor law \(\gamma_s\) with this ideal chain. Only the case \(D_s=0\) can differ. At an unqueried partner, sampling without replacement changes its conditional activity probability from \(p\) by \(O((1+t)/n)\), uniformly through time \(t=O(d)\). At a previously queried partner use the bound one. Thus \[ \|\gamma_{s+1}-\gamma_sQ_s\|_{\rm TV} \le\mathbb P\{D_s=0,\ \hbox{partner previously queried}\} +O((1+t)/n)\mathbb P\{D_s=0\}. \tag{106}\] The remaining task is to get a second factor \(1/n\) in the first term.

First dispose of trajectories that have never split from \(j\). Define an auxiliary test along the baseline path of \(j\), regardless of whether the actual walker has already left it. Sample an independent potential toggle coin at every layer, using it for the actual walk whenever a toggle is allowed. In each successive block of \(2d\) layers, monitor only the last \(d\) layers. At a monitored layer, query the partner’s activity and use the walker’s toggle coin to test for an active toggle. Reveal no unmonitored activity statuses for this test. If the actual walker never splits, every monitored test fails. We bound this larger event using only the monitored-test history. The partners of \(j\) at these monitored layers are distinct: once a baseline path is paired with \(j\), it leaves with an opposite output bit, and that bit is not updated again during the monitored interval. Condition on the baseline history and monitored queries at the beginning of the block. For any previously queried label and any monitored layer, becoming the partner of \(j\) requires matching the preceding \(d-1\) output bits while using distinct switches. Otherwise a previous shared switch leaves an opposite bit that persists. Sequential exposure of the fresh distinct switches bounds this probability by \(2^{-(d-1)}\). A union bound over the \(d\) layers and \(O(1+t)\) known labels bounds the probability of an old partner by \(O(d(1+t)/n)\).

On a sequence of fresh partner queries the remaining active density is at least \(\epsilon/2\) for large \(n\), since \(t=O(d)\). At each monitored layer an active toggle therefore has conditional probability at least \(\epsilon/4\). The probability of avoiding all such toggles while the partners stay fresh is at most \((1-\epsilon/4)^d\). Repeating this conditional estimate at successive block starts, with no conditioning on unmonitored toggle outcomes, gives \[\mathbb P\{\hbox{no split through }C_1d\} \le\bigl(O(d(1+t)/n)+(1-\epsilon/4)^d\bigr)^{\lfloor C_1/2\rfloor} \le n^{-3}\] for a sufficiently large absolute integer \(C_1\).

Any other coincidence at time \(s\ge C_1d\) has a last collapse layer \(u<s\): its input xor is \(e_{i_u}\), it collapses to zero, and it stays zero through time \(s\). Necessarily \(u\ge d\), since the singleton created at the initial split persists until its next coordinate update. In the \(d-1\) layers \(u-d+1,\ldots,u-1\), the walker and \(j\) use distinct switches and output equal updated bits. If they were coincident in that interval, a subsequent split would leave a bit that could not disappear before \(u\); an earlier partner layer likewise cannot produce a different admissible history. Consequently the contribution from a fixed \(u\) is at most \(2^{-(d-1)}\), and \[ \mathbb P\{D_s=0\}\le n^{-3}+2t/n. \tag{107}\]

For the joint event in (106), fix a last collapse layer \(u\) and let \(E_u\) be the event that the walker collapses at \(u\), stays on \(j\) through time \(s\), and the partner at \(s\) has been queried previously. The first \(1/n\) cost comes from the equal-bit window ending at \(u\); the second comes from the final partner matching \(j\) in the window ending at \(s\). These windows may overlap, so their costs cannot be multiplied by an independence claim.

Start from the true history at \(u-d+1\) and define a sequential law \(\widetilde{\mathbb P}_u\) that is allowed to abort. At each of the next \(d-1\) layers, query the needed status and choose the walker toggle as usual. Abort if the two distinguished switches coincide. Otherwise sample their fresh coins conditional on the resulting output bits being equal; this conditioning has probability exactly \(1/2\). Sample all other switches ordinarily. At layer \(u\), abort unless the two paths are partners, then force the walker to collapse onto \(j\). Thereafter query the needed statuses and force the walker to stay on \(j\) through time \(s\). No conditioning on a future successful completion is used. Every true history contributing to \(E_u\) has likelihood at most \(2^{-(d-1)}\) times its likelihood under \(\widetilde{\mathbb P}_u\): the equalities each cost \(1/2\), and the forced decisions discard only factors at most one. It remains to bound the probability of a previously queried final partner under this law.

Let \(W\) consist of the \(d-1\) layers immediately preceding \(s\). Throughout \(W\) the two distinguished outputs have matching updated bits, either by the equality construction or by coincidence after \(u\). A baseline label \(b\ne j\) that is the partner of \(j\) at \(s\) cannot have touched either distinguished switch during \(W\). At a switch of \(j\) it would leave with the opposite bit. At a switch of the walker it either leaves with the opposite bit or follows the walker; in the latter case it must later leave before time \(s\), again creating an opposite bit. Every coordinate used in \(W\) is different from \(i_s\) and is used only once, so any such bit would persist and preclude partnership at \(s\). It follows also that a previously queried final partner was queried before \(W\): all status queries inside \(W\) concern labels touching the walker’s switch there.

Condition on the simulated history before \(W\). There are only \(O(1+t)\) earlier queried candidates. For each candidate, matching the \(d-1\) required bits without touching either distinguished switch has probability at most \(2^{-(d-1)}\). At each step its separate switch is fresh and independent of the distinguished bit, even when the two distinguished coins are being sampled conditional on equality. Abort conditions can only reduce this probability. Thus the probability of a previously queried final partner under \(\widetilde{\mathbb P}_u\) is \(O((1+t)/n)\). The likelihood comparison now gives \[\mathbb P(E_u)\le 2^{-(d-1)}O((1+t)/n) =O((1+t)/n^2).\]

Sum over \(u<s\) and include the no-split contribution. Together with (107), this proves, for \(s\ge C_1d\), \[\|\gamma_{s+1}-\gamma_sQ_s\|_{\rm TV} =O((1+t)^2/n^2).\] Now follow \(C_1d\) by a fixed number \(b>3/\beta\) of \(4d\)-layer blocks. The ideal product sends any law to within \(n^{-3}\) of \(\pi\). Telescoping the actual errors through the remaining Markov kernels, which contract total variation, costs \(O((1+t)^3/n^2)\). With \(C_0=C_1+4b\) we have \[\|\gamma_t-\pi\|_{\rm TV} \le n^{-3}+O((1+t)^3/n^2),\qquad t=C_0d.\] Since \(\pi(0)=1/m\), this proves (105). ◻

Proof of Proposition 56. Use the entropy chain rule for the uniformly ordered input list. At each rank, reveal in addition the entire paths of the earlier labels; this can only increase the conditional relative entropy from the uniform available endpoint. The remaining active set has size \(m\ge n/16\), and its next label is uniform in that set. By label symmetry of the uniform order, one may fix that next label as \(j\) and take the other active labels uniformly among the remaining labels, exactly as in Lemma 57. For the resulting conditional endpoint law \(q\), \[D(q\Vert U_m)\le m\sum_xq(x)^2-1.\] Equations (104) and (105) bound its mean by \(O(m(1+t)^3/n^2)\). Summing over at most \(n\) ranks gives \(O((1+t)^3)\), and \(t=C_0d\) proves the stated result. ◻

Proof. The prescribed path of card \(a\) is unique: successively replace its input bits by its output bits in sweep order. The three cases in the definition of \(u_{ab}\) describe its interaction with the path of \(b\). The first case has no shared switch, the second has exactly one shared switch with consistent opposite outputs, and the third forces a vertex collision. For \(r=|T|\) prescribed paths, the bits cost \(2^{-dr}\) before identifying shared switches; each consistent shared switch saves a factor two. A collision makes both the probability and the product zero. This proves the formula for \(F_T\). If a vertex is isolated, including or omitting it does not change \(F_T\), so its two terms in the alternating sum cancel.

To bound the alternating sum, consider a compatible subset \(T\) of \(r\le k\) paths. Its product is \(F_T=2^{s_T}\), where \(s_T\) counts their shared switches. The empty subset contributes one; for \(r\ge1\), arrange the output words in a binary prefix tree. At a node with child counts \(a,b\), every shared switch sends one path into each child, so at most \(\min(a,b)\) switches are shared there. The inequality \[\min(a,b)\le\frac{(a+b)\log_2(a+b)-a\log_2a-b\log_2b}{2}\] uses \(0\log_2 0=0\) and follows from concavity of binary entropy, which is at least twice its smaller argument. Sum over all nodes; the right side telescopes to \(r\log_2r/2\), bounding \(s_T\). The product is at most \(r^{r/2}\le k^{k/2}\), and summing its at most \(2^k\) appearances proves (109). ◻

Proof. We use the classical branching and Young rules in the conventions of [17, 4]. The permutation representation on ordered distinct \(k\)-tuples is \(\operatorname{Ind}_{S_{n-k}}^{S_n}\mathbf1\). By branching it contains \(\lambda\) precisely when \(\lambda_1\ge n-k\). When \(k=n-\lambda_1\), its \(\lambda\)-isotypic space is orthogonal to functions omitting any specified coordinate: these carry the \((k-1)\)-tuple representation, which contains no copy of \(\lambda\). Thus each function in this space, extended by zero to tuples with repetitions, has sum zero on varying any one coordinate.

Take two such test functions and use the kernel of Lemma 58. Extend each \(u_{ab}\) arbitrarily on pair repetitions, preserving its dependence on just the two indicated input and output coordinates. Every proper-subset term \(F_T\) vanishes in the bilinear form after integrating an omitted coordinate, so we may replace \(F_{[k]}\) by \(F_*\). Under independent uniform input and output coordinates, each zero-extended function has squared norm \(a_k=(n)_k/n^k\) times its squared norm under the uniform injection law. By (108), the bilinear form has the same factor \(a_k\) relative to the Markov bilinear form. Hence the resulting operator bound transfers without loss to the injection normalization. Acting on functions instead of masses may replace the Fourier matrix by its adjoint, which has the same operator norm.

If there are no isolated vertices, choose a spanning forest in each nontrivial component of the nonzero-edge graph. Its number of edges satisfies \(k/2\le e\le k-1\). For an upper bound there are at most \(k^{2e}\) candidate forests with \(e\) edges and at most \(d^e\) choices of the edge coordinates \(J\). A nonzero edge requires equality of the input suffix after \(J\) and equality of the output prefix before \(J\). For a fixed forest and choices of \(J\), write its requirement indicator as \(A(x)B(y)\). For each bit, the edges imposing equality form a subforest, so there is one independent binary constraint per edge; choose the bits successively from roots to leaves. It follows that \[\mathbb E_x A(x)=2^{-\sum_{\rm edges}(d-J)},\qquad \mathbb E_y B(y)=2^{-\sum_{\rm edges}(J-1)}.\] The kernel \(A(x)B(y)\) has operator norm equal to the geometric mean of these probabilities, namely \((2/n)^{e/2}\). One may also obtain the same value by the row and column bounds in Schur’s test. Taking absolute values of the test functions, using (109), and summing this domination gives for \(k\ge2\) the bound \[2^k k^{k/2} \sum_{\lceil k/2\rceil\le e\le k} \bigl(k^2d\sqrt{2/n}\bigr)^e.\] It is at most \(n^{-k/10}\) uniformly for \(2\le k\le n^{1/20}\) and large \(n\). For example, \(2^k k^{k/2}\le n^{k/20}\) and \(k^2d\sqrt{2/n}\le n^{-3/8}\) eventually, so the displayed sum is at most \(2n^{-11k/80}\le n^{-k/10}\). When \(k=1\), \(F_*=1-1=0\), which is the exact one-card uniformity of a sweep. This proves (110).

Finally a single switch layer is averaging over the subgroup \((S_2)^{n/2}\) supported on its disjoint matching pairs. Young’s rule says its invariant vectors can occur only in shapes dominating \((2^{n/2})\). Such a shape has at most \(n/2\) rows, since the sum of its first \(n/2\) rows must be at least \(n\). Thus every layer projection, and hence the sweep product, vanishes on all taller shapes. ◻

Proof. Choose a uniform partition of the input labels into sixteen equal blocks. Each block complement has the law of the retained domain in Proposition 56; ordering that complement does not affect its relative entropy. Averaging the sum over all sixteen complements therefore selects a deterministic partition with total marginal relative entropy \(O((1+d)^4)\).

The entropy and sparse-degree hybrid theorem [14] applies to this fixed partition and to the law \(\mu\) of \(C_0\) sweeps. Its entropy truncation deletes permutations whose density on any complementary marginal exceeds \(\exp(n^{1/50})\), then normalizes to a law \(\nu\), as in [14]. To check its mass hypothesis directly, for a density \(f\) relative to a probability \(u\), \[\int_{\{f>e^a\}}f\,du \le\frac{D(fu\Vert u)+1/e}{a},\] because the negative part of \(f\log f\) is at most \(1/e\) pointwise. Taking \(a=n^{1/50}\) and summing over the sixteen marginals gives \(\|\nu-\mu\|_{\rm TV}=O((1+d)^4/n^{1/50})=o(1)\). After normalization each complementary coset density is at most \(2\exp(n^{1/50})\) for large \(n\).

The large-degree estimate [14] gives \(\|\widehat\nu(\lambda)\|_{\rm op}\le D_\lambda^{-1/3}\) whenever \(k=n-\lambda_1>n^{1/20}\) and \(\lambda\) has at most \(n/2\) rows. The hybrid theorem [14] also assumes a probability law \(K\) with operator decay \(n^{-k/10}\) for \(1\le k\le n^{1/20}\) and zero transform on taller shapes. Proposition 59 supplies these estimates for one true sweep, separately from the entropy construction.

The theorem controls the exact convolution \(\sigma=\nu^{*12}*K^{*40}\), whose Fourier matrix in our convention is \(\widehat\sigma(\lambda)=\widehat\nu(\lambda)^{12} \widehat K(\lambda)^{40}\). All convolution factors are independent. Its operator norm is at most \(D_\lambda^{-4}\) in the large-deficit range, at most \(n^{-4k}\) in the small-deficit range, and zero above \(n/2\) rows. The Plancherel sum uses \(D_\lambda^2\) times the square of these operator bounds, with ordinary unnormalized Hilbert–Schmidt norms. The degree and partition estimates in [14] sum the large range to \(o(1)\); in the small range \(D_\lambda\le n^k\) from the tuple module, so the contribution at each \(k\) is at most the number of partitions of \(k\) times \(n^{-6k}\), whose sum also tends to zero. The sign shape has more than \(n/2\) rows and is annihilated by \(K\), so no parity bias survives. Cauchy–Schwarz therefore gives total variation tending to zero.

Replacing the twelve factors \(\nu\) by \(\mu\) costs at most \(12\|\nu-\mu\|_{\rm TV}=o(1)\). The resulting law consists of \(12C_0+40\) successive true sweeps, which is \((12C_0+40)d\) physical shuffles. Translation by an initial deck preserves the same distance. ◻

Proof of the entropy bound. Consider the chain-rule term for the \((j+1)\)-st card, \(0\le j\le q-1\); the reference law from \(\mathbf u_q\), given the final positions of the first \(j\) cards, is uniform on the \(M=N-j\) other positions. Further condition on \(\Gamma\), the data of the whole trajectories through time \(T\) of these first \(j\) cards (generated by the shuffles used for \(w\)). Call these \(j\) cards observed cards, and the other labels unobserved. For the fixed list \(I\), write \(p_\Gamma\) for the law of the final position of the next card, whose label we denote by \(X\), given \(\Gamma\). The positions available to \(X\) at the end, complementary to the first \(j\) final positions, form the final available set; write \(u_\Gamma\) for its uniform law. Conditioning additionally as above gives an upper bound on the entropy term by convexity of relative entropy, since the uniform reference here only depends on the first \(j\) final positions. Thus the term, now averaged over \(I\), is bounded by \[ \mathbb E_{I,\Gamma}\mathrm{KL}(p_\Gamma\|u_\Gamma) \ \le\ M\mathbb E_{I,\Gamma}\sum_z p_\Gamma(z)^2-1, \tag{112}\] where \(z\) indexes the final available positions and the last inequality uses \(\log b\le b-1\).

By Lemma 2, conditional on \(I,\Gamma\), switches visited by observed cards have fixed choices, while the coins on pairs of available positions remain independent and fair. We now construct the additional coupling needed to represent the squared mass.

Generate a full shuffle trajectory (the reference trajectory for every label) using all actual switch choices, so \(X\) uses its reference trajectory. We construct a replica path, starting at the same position as \(X\), that will be on reference trajectories of unobserved labels. When at a switch also being used by \(X\), and this switch has two available positions, the replica uses an extra independent fair coin, choosing to follow either \(X\) or its partner in the reference trajectories through this switch. In any other case, the replica follows the reference trajectory of the label at its position through its switch.

The positional path of this replica and the path of \(X\) are independent copies given \(I,\Gamma\). To see it, condition on the past at any stage in this construction. Given \(I,\Gamma\), the single-path transition at an available position is forced if the switch contains an observed card, and otherwise it uses the two outputs with equal probability. If the replica and \(X\) are at different switches, any unforced choices there come from independent fresh coins. If they use the same switch with only one available position, they both have a forced transition. If they use the same switch with two available positions, the rule with the extra coin makes the replica transition uniform independently of the transition of \(X\). Thus the joint positional transitions are products at every step and the kernels in this description only require the respective present positions given \(I,\Gamma\). In particular, writing \(C_s\) for the label tracked by the replica at time \(s\) (\(C_0=X\)), we have \[\mathbb E_{I,\Gamma}\sum_z p_\Gamma(z)^2=\Pr(C_T=X),\] since the reference trajectories of the labels give distinct final positions.

We now average without conditioning on \(\Gamma\). Fix which label \(X\) is, and, in the reference trajectories, let \(J_s\) be the label of the partner of \(X\) at step \(s\), where the steps are indexed \(s=0,\ldots,T-1\). The set of \(M-1\) unobserved labels other than \(X\) in this estimate is uniformly chosen among the other \(N-1\) labels, independently of the reference trajectories, due to the choice of \(I\). Given the sequence \(J_s\) and the unobserved labels, \(C_s\) can only change when it is in \(\{X,J_s\}\) and \(J_s\) is an unobserved label. In this case \(C_{s+1}\) is \(X\) or \(J_s\) each with probability \(1/2\), by the extra coin.

We give estimates for repeats in the partner sequence, over the reference randomness. Write \(b_{i,u}=\Pr(J_i=J_u)\). Then, for \(0\le i<u<T\), \[ \begin{cases} b_{i,u}=0 & 0<u-i<d,\\ b_{i,u}=2/N & u-i=d,\\ b_{i,u}\le (1+2/N)/N & u-i>d. \end{cases} \tag{113}\] Indeed, at step \(i\) the two actual labels \(X,J_i\) have opposite appended bits. These bits preclude a repeat partner for a gap less than \(d\). At \(u\ge i+d\), a repeat requires the appended bits for these two labels at step \(u-d\) to be opposite and those at steps \(u-d+1,\ldots,u-1\) to match, and these conditions suffice. Given opposite bits at \(u-d\), the next \(d-1\) steps have different switches for these labels, so the matching part has probability \(2^{-(d-1)}\). When \(u-d=i\), we have the opposite bits for sure. When \(u-d>i\), the bits there are opposite with probability one if the two are partners at \(u-d\), and \(1/2\) otherwise, making \(b_{i,u}=(1+b_{i,u-d})/N\). For a preceding pair of times \(i<v=u-d\), \(b_{i,v}\) is at most \(2/N\): a smaller gap than \(d\) gives zero, and for gap at least \(d\), the \(d-1\) required bit matches each have conditional probability at most \(1/2\) given the past. Here \(J_i\) is known by the times requiring these matches. This proves (113).

Let \(R_0=T-|\{J_s:0\le s<T\}|\). We also have \[ \Pr(R_0\ge 2)=O(T^4/N^2). \tag{114}\] Indeed, fix two distinct repeat times \(u,v\) and earlier indices \(i<u\), \(h<v\), and ask for \(J_u=J_i\) and \(J_v=J_h\). By (113), both gaps must be at least \(d\). Let \(\mathcal F_s\) contain all reference switch coins at steps strictly before \(s\). The partner \(J_s\) is \(\mathcal F_s\)-measurable. In particular \(J_i\) is already known before the interval \([u-d+1,u-1]\) of \(d-1\) required bit matches, and the analogous statement holds for \(J_h\) and \([v-d+1,v-1]\).

If these intervals overlap, then \(|u-v|<d\). On the joint repeat event the two earlier labels must differ: otherwise the same label would be a partner at both \(u\) and \(v\), contradicting (113). At an overlap step impose this inequality as part of the event being bounded; it is measurable before that step. The three distinct labels \(X,J_i,J_h\) must append the same bit. If any two occupy one switch the event is impossible, because the two true outputs are opposite. Otherwise three independent fair switch coins give the event probability \(1/4\). At a step in just one matching interval the probability is at most \(1/2\). Iterating these bounds in chronological order gives \(2^{-2(d-1)}=4/N^2\) for the fixed quadruple \((i,u,h,v)\). The union bound over \(O(T^4)\) quadruples proves (114).

We have controlled the frequency of repeated partners. It remains to average which distinct partners belong to the hidden set. This step is where the uniform random input list enters.

Let \[\delta=\frac{M-1}{N-1},\qquad \eta=1-\frac{\delta}{2}.\] Here \(\delta\ge 1/L\). Given \(J_s\), mark each distinct label in the sequence according to whether it is unobserved. The probabilities of these mark patterns are upper bounded by those for independent marks of chance \(\delta\), times a common factor \[c_T=\frac{(N-1)^T}{(N-1)_T}=1+O(T^2/N)\] for large \(d\). In fact for \(k\) distinct labels with \(b\) specified to be unobserved labels and \(k-b\) to be observed, the true probability is \((M-1)_b(N-M)_{k-b}/(N-1)_k\), and \(k\le T=o(\sqrt N)\).

Suppose \(R_0\le 1\). The independent-marks bound (before the factor \(c_T\)) for never leaving \(X\), i.e. \(C_s=X\) throughout, is at most \(\eta^{T-1}\), using a step with each of at least \(T-1\) distinct partners. If \(C_s\) does leave \(X\) and \(C_T=X\), there must be a repeat \(J_i=J_u\), which for \(R_0\le 1\) is the only one. At \(i\) it must switch from \(X\) to the repeated label, and at \(u\) back to \(X\). There can be no other departure. The independent-marks probability for this behavior given such a sequence is \[\frac{\delta}{4}\,\eta^{i+T-1-u}.\] Here we used the mark of the repeated label and two particular coin results there; all the steps requiring no departure before \(i\) or after \(u\) have different partners, also different from the repeated one.

Combining this with (113) and (114), \[\begin{aligned} \Pr(C_T=X) &\le O(T^4/N^2)+c_T\left[\eta^{T-1} +\frac{\delta}{4}\sum_{i<u}\eta^{i+T-1-u} b_{i,u}\right]\\ &\le O(T^4/N^2)+c_T\left[\eta^{T-1} +\frac{1+2/N}{\delta N} +\frac{\delta}{4N}\,T\eta^{T-1-d}\right]. \end{aligned}\] Indeed the non-special bound \((1+2/N)/N\) gives the middle term by a double geometric sum since \(\sum_{l\ge 0}\eta^l=2/\delta\), and an additional bound of \(1/N\) can be included for gaps \(d\). We have \(\eta^{T-1-d}\le N^{-4}\) for large \(d\), by \(A=64L\), and \(M/(\delta N)=1+O(1/N)\). Consequently \[M\Pr(C_T=X)-1\ \le\ O(T^4/N)\] uniformly in \(j\), under the averaging used in (112). Each conditional entropy term is therefore \(O(T^4/N)\). There are \(q\le N\) terms, so their sum is \(O(T^4)=O(d^4)\), proving (111). ◻

Proof. Use the representation on ordered distinct \(k\)-tuples, with a group element taking the coordinate vector for \(\boldsymbol x\) to that for \(g\boldsymbol x\). The law \(\kappa=q_d^{*d}\) is the true-sweep law \(K\) of Lemma 58: after \(d\) physical shuffles the moving frame returns to the identity. For ordered distinct \(\boldsymbol x,\boldsymbol y\), use that lemma’s kernels \[F_S(\boldsymbol x,\boldsymbol y)=N^{|S|}\Pr_\kappa(g x_a=y_a\text{ for }a\in S), \qquad F_\circ=F_*=\sum_{S\subseteq[k]}(-1)^{k-|S|}F_S.\] The averaged matrix for \(\kappa\) has entries (output \(\boldsymbol y\), input \(\boldsymbol x\)) given by \(F_{\{1,\ldots,k\}}/N^k\). When projecting on the output side to \(\lambda\)-type, we can replace \(F_{\{1,\ldots,k\}}\) by \(F_\circ\): the other terms map into functions of proper subsets of output positions only. The space for any such subset is a copy of a tuple module on fewer entries, not containing \(\lambda\) by branching. Also \(\lambda\) does occur in our \(k\)-tuple module, and the projected \(\kappa\)-matrix includes at least one copy of \(\widehat\kappa(\lambda)\). Consequently, by taking the Hilbert-Schmidt bound before applying the output projection to the replacement matrix, \[ \|\widehat\kappa(\lambda)\|_{\mathrm{HS}}^2 \le \left(\frac{(N)_k}{N^k}\right)^2 \mathbb E_{\boldsymbol x,\boldsymbol y} \left|F_\circ(\boldsymbol x,\boldsymbol y)\right|^2, \tag{121}\] where each of \(\boldsymbol x,\boldsymbol y\) is separately a uniform tuple with distinct positions and they are independent.

By Lemma 58, \(|F_\circ|\le2^kk^{k/2}\), and \(F_\circ\) vanishes when the graph of shared prescribed switches has an isolated vertex. Unlike the operator estimate in Proposition 59, (121) requires the probability of the remaining pairs of tuples, rather than a bound on their bilinear form. For \(k=1\), \(F_\circ\) already vanishes by isolation. For \(k\ge 2\), if there are no isolated vertices then the graph contains a spanning forest with no isolated vertices, having at least \(k/2\) and at most \(k-1\) edges. Consider first drawing all positions of the two tuples independently with replacement. A shared switch in direction \(i\) requires agreement of the length-\((d-i)\) input suffixes and the length-\((i-1)\) output prefixes. Given the data at one vertex, a fresh vertex forms an edge to it with probability at most \(2d/N\), by summing over the steps the probabilities of suffix and prefix agreement. Thus for any particular forest the probability that all its edges are present is at most \((2d/N)^{\#\text{edges}}\), by drawing along the trees. Conditioning each tuple to have distinct positions costs a factor at most 2 for large \(d\) in our size range. Summing over forests (at most \(k^{2k+1}\), by counting edge lists) bounds the probability in (121) that \(F_\circ\ne 0\) by \[2 k^{2k+1}(2d/N)^{k/2}.\] Together with the size bound this yields (120), since factors \(k^{O(k)}d^{O(k)}\) are only \(\exp(O(k\log d))\) here, compared to \(N^{k/2}\) in the probability denominator. ◻

Completion of Theorem 61. Let \(B=80\) and \(\theta=v^{*B}* w\), of mass \(m^B\) and dominated pointwise by the true law \(w^{*(B+1)}\). For \(\log D_\lambda>d^8\), (117) gives \[\|\widehat\theta(\lambda)\|_{\mathrm{HS}}^2\le D_\lambda^{-B/2}\] for large \(d\), by convolution multiplication and Hilbert-Schmidt submultiplicativity, using also \(\|\widehat w(\lambda)\|_{\mathrm{op}}\le 1\) since it averages unitaries. It follows from (118) that \[\sum_{\lambda:\log D_\lambda>d^8}D_\lambda \|\widehat\theta(\lambda)\|_{\mathrm{HS}}^2 \le C \exp\big((33-B/2)d^8\big)=o(1).\] At smaller dimensions, excluding the trivial representation, we have either the vanishing for \(\kappa\) above (hence for \(\theta\)), or the bounds (120) with \(k\ge 1\), and \(\|\widehat v(\lambda)\|_{\mathrm{op}}\le 1\). In the latter case \(D_\lambda\le N^k\) since the \(k\)-tuple representation contains \(\lambda\), and \(w=\kappa^{*A}\), so \[D_\lambda \|\widehat\theta(\lambda)\|_{\mathrm{HS}}^2 \le N^k\big(N^{-k/10}\big)^{2A}.\] Summing this over these diagrams gives \(o(1)\) (the count for first row \(N-k\) is at most \(\exp(3\sqrt k)\)).

Writing \(U_G\) for uniform on \(G\), Cauchy-Schwarz and Plancherel give \[\|\theta-m^B U_G\|_1^2 \le \sum_{\lambda\ \mathrm{nontrivial}}D_\lambda\|\widehat\theta(\lambda)\|_{\mathrm{HS}}^2 =o(1),\] with \(\ell^1\) on group masses. Hence TV distance for \(w^{*(B+1)}\) from uniform is bounded by \(1-m^B+\tfrac12\|\theta-m^B U_G\|_1\), tending to zero. This law uses \((B+1)A d\) complete shuffles, proving the asserted time \(81\cdot16384d=1327104d\). Translation of the initial deck preserves the distance to uniform, so the convergence is uniform over starting decks. ◻