betaFeedback

WorksMathematics

Cutoff and a Gaussian-shift profile for the Rudvalis shuffle

Abstract

The Rudvalis shuffle removes the top card and reinserts it uniformly at random in one of the bottom two positions. Hildebrand proved the classical upper bound O(n3log⁡n)O(n^3\log n), and Wilson later proved the sharp lower coefficient 1/(8π2)1/(8π^2), establishing the correct order but leaving the leading upper constant, cutoff, and the cutoff profile open. We prove that the full labelled shuffle has total-variation cutoff at n3log⁡n8π2 \frac{n^3\log n}{8π^2} with a window of order n3n^3. The upper bound is obtained by writing one deterministic rotation of the shuffle as a nonnormal sweep of adjacent averaging projections, comparing that sweep to a weighted interchange generator, and controlling the entire regular-representation heat trace. The key sharp-window ingredients are heat-kernel smoothing through the Octopus Inequality, zero extension of deletion-harmonic ordered-tuple functions, a representation-theoretic multiplicity payment, and a sectorwise entrance estimate that disposes of all large Young-diagram deficits. For the profile, an exact complex one-card eigenfunction yields a deck statistic whose surviving first Fourier mode converges to a Gaussian shift. A matching full-deck L2L^2 bound then shows that this one-dimensional Gaussian likelihood ratio asymptotically exhausts all remaining information, giving the exact total-variation profile.

Introduction and historical context

The shuffle and the long-standing sharp-constant problem

The Rudvalis shuffle is one of the simplest examples of a card shuffle whose global mixing is much slower than the visible motion of a single step might suggest. From a deck of nn labelled cards, remove the top card and place it either at the bottom or immediately above the bottom card, each with probability 1/21/2. The model was proposed by Arunas Rudvalis and was recorded in Diaconis’s monograph on group representations and probability [2]. We number positions from top to bottom.

The early quantitative theory was developed by Hildebrand, whose thesis established an O(n3log⁡n)O(n^3 \log n) total-variation upper bound [7]. Diaconis and Saloff-Coste subsequently developed comparison methods for random walks on finite groups and studied closely related symmetric variants of the Rudvalis dynamics [3, 4]. Wilson’s 2003 paper supplied the decisive lower-bound advance: for every fixed ε>0\varepsilon> 0, at time

1−o(1)8π2n3log⁡n\frac{1-o(1)}{8\pi^2}n^3 \log n

the original Rudvalis shuffle remains at total-variation distance at least 1−ε1-\varepsilon from uniform [13 Theorem 1]. Thus the order Θ(n3log⁡n)\Theta(n^3 \log n) was known, but the upper and lower leading constants did not match. Wilson’s method also clarified why the problem is delicate: the relevant one-card mode is complex and its phase rotates quickly, while its modulus decays only on the much longer scale n3n^3 [13]. Jonasson later gave a streamlined route to the same order of lower bound using an nn-step viewpoint [9], and Goel studied the broader family of top-to-bottom-kk shuffles [5].

A different line of work studies hydrodynamic and fluctuation limits of particle projections of Rudvalis-type shuffles. Gonçalves, Jara, Marinho and Moreira obtained such scaling limits and, in their 2023 paper, explicitly noted that matching mixing-time bounds for the original Rudvalis shuffle were still unknown [6]. Their work also emphasizes a useful conceptual separation: diffusive or hydrodynamic information about a fixed projection does not by itself control the full labelled permutation.

The present argument closes the sharp upper-bound gap and goes further to identify the cutoff window and profile. A recent ingredient is the use of the Octopus Inequality of Caputo, Liggett and Richthammer [1], in a heat-kernel smoothing comparison of the type that also appears in recent work of Hermon, Kozma and Salez on the exclusion process [8]. We use only the comparison inequality derived from the Octopus Inequality; no exclusion-process cutoff theorem is imported into the Rudvalis shuffle.

Main result

Let πn\pi_n be the uniform probability measure on Sn\mathfrak{S}_n, let μt\mu_t be the law of the deck after tt elementary Rudvalis moves from a deterministic initial deck, and define

dn(t)=∥μt−πn∥TV.d_n(t)=\|\mu_t-\pi_n\|_{\mathrm{TV}}.

Because the shuffle is a random walk on the group Sn\mathfrak{S}_n, translation of the initial deck merely translates the law, and dn(t)d_n(t) does not depend on the deterministic starting permutation.

For probability measures μ≪πn\mu\ll\pi_n, define the chi-square divergence

χ2(μ,πn)=Eπn[(dμdπn−1)2].\chi^2(\mu,\pi_n)=\mathbb{E}_{\pi_n}\left[\left(\frac{d\mu}{d\pi_n}-1\right)^2\right].

We abbreviate χn2(t)=χ2(μt,πn)\chi_n^2(t)=\chi^2(\mu_t,\pi_n).

Theorem 1.1 (Cutoff profile). For each fixed s∈Rs \in\mathbb{R}, put

tn(s)=⌊n38π2(log⁡n+2s)⌋.t_n(s)=\left\lfloor\frac{n^3}{8\pi^2}(\log n+2s)\right\rfloor.

Then

dn(tn(s))⟶2Φ(e−s2)−1=erf⁡(e−s2),(1)d_n(t_n(s))\longrightarrow2\Phi\left(\frac{e^{-s}}{\sqrt{2}}\right)-1=\operatorname{erf}\left(\frac{e^{-s}}{2}\right), \tag*{(1)}
χn2(tn(s))⟶exp⁡(2e−2s)−1.(2)\chi_n^2(t_n(s))\longrightarrow\exp(2e^{-2s})-1. \tag*{(2)}

Here Φ\Phi is the standard normal distribution function and erf⁡(x)=2π∫0xe−u2 du\operatorname{erf}(x)=\frac{2}{\sqrt{\pi}}\int_0^x e^{-u^2}\,du.

The profile is best understood as a Gaussian-shift profile. The total-variation profile itself is not a Gaussian density. At the cutoff window, one real Fourier statistic has limiting law N(0,1)N(0,1) under stationarity and N(2e−s,1)N(\sqrt{2}e^{-s},1) under the shuffled deck. The total-variation distance between those two normal laws is exactly the right side of (1).

Corollary 1.2 (Sharp mixing time and window). For every fixed ε∈(0,1)\varepsilon\in(0,1),

tmix(ε)=n3log⁡n8π2−n34π2log⁡(2erf⁡−1(ε))+o(n3).t_{\mathrm{mix}}(\varepsilon)=\frac{n^3\log n}{8\pi^2}-\frac{n^3}{4\pi^2}\log\left(2\operatorname{erf}^{-1}(\varepsilon)\right)+o(n^3).

In particular,

tmix(ε)=(18π2+o(1))n3log⁡n,t_{\mathrm{mix}}(\varepsilon)=\left(\frac{1}{8\pi^2}+o(1)\right)n^3\log n,

and the cutoff window has order n3n^3. With the conventional centering tn=n3log⁡n/(8π2)t_n=n^3\log n/(8\pi^2), a natural window scale is wn=n3/(4π2)w_n=n^3/(4\pi^2).

Proof. The function F(s)=erf⁡(e−s/2)F(s)=\operatorname{erf}(e^{-s}/2) is continuous and strictly decreasing, with F(s)→1F(s)\to1 as s→−∞s\to-\infty and F(s)→0F(s)\to0 as s→+∞s\to+\infty. Solving F(s)=εF(s)=\varepsilon gives s=−log⁡(2erf⁡−1(ε))s=-\log(2\operatorname{erf}^{-1}(\varepsilon)). Monotonicity of total-variation distance in time and Theorem 1.1 then bracket the level-ε\varepsilon hitting time between any two nearby fixed window parameters, yielding the stated expansion.

Why the constant 1/(82) appears

The proof makes the constant transparent. One full turn of the deterministic rotation consists of nn elementary moves and becomes, in a rotating coordinate frame, a product

K=Pn−1⋯P0,Pi=I+U(i,i+1)2,K=P_{n-1}\cdots P_0,\qquad P_i=\frac{I+U_{(i,i+1)}}{2},

of adjacent averaging projections around the cycle. We compare this nonnormal product to the positive weighted interchange operator

LQ=Q−1A0+∑i=1n−1Ai,Ai=I−Pi.L_Q=Q^{-1}A_0+\sum_{i=1}^{n-1}A_i,\qquad A_i=I-P_i.

The endpoint comparison has the asymptotically sharp constant

K∗LQK⪯cQ(I−K∗K),cQ=1+5/Q4⟶14.K^*L_QK\preceq c_Q(I-K^*K),\qquad c_Q=\frac{1+5/Q}{4}\longrightarrow\frac{1}{4}.

On the other hand the first nonzero one-card eigenvalue of LQL_Q is asymptotic to 2π2/n22\pi^2/n^2. Hence the critical static heat-trace time is n2log⁡n/(2π2)n^2\log n/(2\pi^2). Multiplication by the endpoint factor 1/41/4 gives n2log⁡n/(8π2)n^2\log n/(8\pi^2) sweeps, and multiplying by nn moves per sweep gives the physical time n3log⁡n/(8π2)n^3\log n/(8\pi^2).

Architecture of the proof

The proof separates naturally into an upper-bound problem and a profile-identification problem. The upper-bound problem is genuinely full-deck: it must control all n!n! configurations and all irreducible components of the regular representation. The profile problem is finer. Once the full-deck remainder is known to be small at the n3n^3 window scale, one must identify the residual mode, prove its Gaussian limit, and then show that no other asymptotically detectable information survives.

The first simplification is geometric. A Rudvalis move contains a deterministic cyclic displacement together with a single fair local randomization. Observing the chain after complete rotations and passing to a rotating coordinate frame removes the deterministic drift. One obtains the systematic adjacent-projection sweep

K=Pn−1⋯P0,Pi=I+U(i,i+1)2.K = P_{n-1}\cdots P_0,\qquad P_i = \frac{I+U_{(i,i+1)}}{2}.

This operator is not self-adjoint, so its powers cannot be studied by the usual reversible spectral theorem. The role of the weighted interchange operator

LQ=Q−1A0+∑i=1n−1AiL_Q = Q^{-1}A_0+\sum_{i=1}^{n-1} A_i

is precisely to supply a reversible comparison object. A local three-site calculation relates the Dirichlet energy of the endpoint KFKF to the norm dissipated by the projection sweep. From this one obtains a resolvent comparison for the singular values of KK. This is the mechanism that transports static heat-trace estimates for LQL_Q back to the original directed shuffle without treating KK as if it were reversible.

The main full-deck difficulty is representation-theoretic multiplicity. A bound for one card, or even for a fixed number of labelled cards, does not by itself control the regular representation. We therefore group irreducible representations by the first-row deficit r=n−λ1r=n-\lambda_1 of the corresponding partition. For small and intermediate deficits, deletion-harmonic functions on ordered injective rr-tuples contain enough copies of every relevant irreducible. The comparison becomes effective only after smoothing the one-card kernel. At the smoothed scale, zero extension from injective tuples to the full product incurs an explicit collision penalty of order r2p∗r^2p_*, with p∗p_* the largest smoothed transition probability, instead of the exponentially large extension losses that arise at the original nearest-neighbor scale. Young branching then pays the regular-representation multiplicities with the correct factorial factor.

Large deficits require a different idea. A crude spectral gap is strong enough once the effective dimension has first been reduced. We accomplish this with a short heat-trace entrance estimate obtained by cutting the path into blocks and restricting the regular representation to the corresponding Young subgroup. This produces a sectorwise bound that depends on the deficit rr, rather than paying the full dimension n!n! at the final cutoff time. Combining the harmonic-tuple estimate for moderate rr with the block entrance and rough gap for large rr closes the entire regular heat trace.

To work at the exact cutoff window, rather than at a fixed positive multiplicative slack, the weak-edge parameter QQ must tend slowly to infinity. This removes the seam loss in the sweep-to-interchange comparison. The required uniformity is supplied by a heat-kernel bound for the smoothed one-card chain that is independent of QQ. With a suitable choice of QQ, smoothing scale, and deficit threshold, the full regular trace at

n22π2(log⁡n+2s)\frac{n^2}{2\pi^2}(\log n+2s)

has the precise leading contribution coming from the two lowest one-card modes. After transfer through the nonnormal resolvent estimate, this yields

lim sup⁡n→∞χn2(tn(s))≤exp⁡(2e−2s)−1.\limsup_{n\to\infty}\chi_n^2(t_n(s)) \le\exp(2e^{-2s})-1.

The remaining task is to identify the random variable that exhausts this L2L^2 budget. The one-card sweep has an exact eigenvalue determined by

λn−2(2λ−1)=1,\lambda^{n-2}(2\lambda-1)=1,

and its associated complex Fourier eigenfunction lifts to a normalized statistic of the entire deck. At time tn(s)t_n(s) this statistic retains a deterministic mean of order e−se^{-s}. A one-sweep martingale decomposition reduces its fluctuations to bounded increments. The key quantitative input is concentration of the conditional one-sweep covariance, proved by encoding the top–bottom interactions during a sweep in a random tree whose degree-square sum has expectation of order nn. The martingale central limit theorem then gives a Gaussian shift: under stationarity the relevant real statistic converges to N(0,1)N(0,1), whereas from the ordered deck it converges to N(2e−s,1)N(\sqrt{2}e^{-s},1).

A one-dimensional Gaussian limit alone would give only a lower bound on the full-deck total-variation distance. The sharp chi-square bound supplies the missing converse. The Gaussian shift has likelihood ratio with second moment exactly exp⁡(2e−2s)\exp(2e^{-2s}), matching the full-deck limiting L2L^2 budget. A bounded-truncation argument therefore forces the full likelihood ratio to become asymptotically measurable with respect to the single Gaussian statistic. This saturation step rules out any additional surviving information and identifies the complete total-variation profile.

The only deep external comparison input is the Octopus Inequality [1]. All other estimates needed to pass from that comparison to the Rudvalis profile are proved below. Standard representation-theoretic facts about SnS_n are recalled explicitly and cited to Sagan [12].

Definitions, notation, and background

Markov-chain distances and cutoff

For probability measures μ,ν\mu,\nu on a finite set Ω\Omega,

∥μ−ν∥TV=12∑x∈Ω∣μ(x)−ν(x)∣=max⁡A⊆Ω∣μ(A)−ν(A)∣.\lVert\mu-\nu\rVert_{\mathrm{TV}}=\frac{1}{2}\sum_{x\in\Omega}\lvert\mu(x)-\nu(x)\rvert=\max_{A\subseteq\Omega}\lvert\mu(A)-\nu(A)\rvert.

If π\pi is strictly positive and μ≪π\mu\ll\pi, the chi-square divergence is

χ2(μ,π)=∑x(μ(x)−π(x))2π(x)=Eπ[(dμdπ−1)2].\chi^2(\mu,\pi)=\sum_x\frac{(\mu(x)-\pi(x))^2}{\pi(x)}=\mathbb{E}_{\pi}\left[\left(\frac{\mathrm{d}\mu}{\mathrm{d}\pi}-1\right)^2\right].

Cauchy–Schwarz gives

∥μ−π∥TV≤12χ2(μ,π).\lVert\mu-\pi\rVert_{\mathrm{TV}}\leq\frac{1}{2}\sqrt{\chi^2(\mu,\pi)}.

Both distances contract when the same Markov kernel is applied to both measures. For 0<ε<10<\varepsilon<1, the total-variation mixing time is

tmix(ε)=min⁡{t:dn(t)≤ε}.t_{\mathrm{mix}}(\varepsilon)=\min\{t:d_n(t)\leq\varepsilon\}.

A sequence of chains exhibits total-variation cutoff at locations tnt_n with windows wn=o(tn)w_n=o(t_n) and profile FF if

dn(⌊tn+swn⌋)⟶F(s)d_n(\lfloor t_n+sw_n\rfloor)\longrightarrow F(s)

for each fixed real ss, where F(−∞)=1F(-\infty)=1 and F(+∞)=0F(+\infty)=0. Standard background on mixing and cutoff may be found in [11, 10].

The group action and the rotating-frame sweep

Let Sn\mathcal{S}_n act on deck positions on the right. For g∈Sng \in\mathcal{S}_n, let UgU_g denote the corresponding unitary operator on functions on any permutation representation:

(Ugf)(σ)=f(σg).(U_gf)(\sigma)=f(\sigma g).

In particular, on C[Sn]\mathbb{C}[\mathcal{S}_n] this is the right regular representation. Every transposition ss satisfies Us∗=Us=Us−1U_s^*=U_s=U_s^{-1}.

Let ρ\rho be the cyclic positional shift that moves the top card to the bottom, and let τ\tau interchange the bottom two positions. One Rudvalis move is ρ\rho or τρ\tau\rho, each with probability 1/21/2; changing the convention for right versus left multiplication merely transposes the operator and does not affect any singular-value or mixing estimate below. Thus, after fixing a convention, the one-step operator can be written as a deterministic rotation composed with one fair two-site average.

Lemma 2.1 (One full rotation is an adjacent-projection sweep). Let si=(i,i+1)s_i=(i,i+1) with indices understood modulo nn, and set

Pi=I+Usi2,Ai=I−Pi.P_i=\frac{I+U_{s_i}}{2}, \qquad A_i=I-P_i.

After nn elementary Rudvalis moves, and after conjugating by the deterministic rotating frame, the Markov operator is

K=Pn−1Pn−2⋯P0.K=P_{n-1}P_{n-2}\cdots P_0.

Consequently estimates for KmK^m are estimates for the original shuffle after nmnm elementary moves. Reversing the orientation of the deck replaces KK by a conjugate or transpose, which has the same singular values.

Proof. Write one step as UρPU_\rho P, where P=(I+Uτ)/2P=(I+U_\tau)/2 is the fair average at the bottom seam. Using UρPUρ−1U_\rho P U_\rho^{-1} to move the averaging operator through a rotation, expand

(UρP)n=Uρn(Uρ−(n−1)PUρn−1)⋯(Uρ−1PUρ)P.(U_\rho P)^n=U_\rho^n\left(U_\rho^{-(n-1)}PU_\rho^{n-1}\right)\cdots\left(U_\rho^{-1}PU_\rho\right)P.

Since ρn=e\rho^n=e, the deterministic rotations cancel. The conjugates of the bottom seam by successive powers of ρ\rho are exactly the nn adjacent transpositions around the cycle, in cyclic order. Relabelling the starting edge gives the displayed product. □

Linear-algebra conventions

All finite-dimensional inner products are complex Hilbert-space inner products, linear in the second variable. For self-adjoint operators B,CB,C, the notation

B⪯CB\preceq C

means ⟨f,Bf⟩≤⟨f,Cf⟩\langle f,Bf\rangle\le\langle f,Cf\rangle for every vector ff. This is the Loewner or quadratic-form order. If 0⪯B⪯C0\preceq B\preceq C, the min–max principle implies that the ordered eigenvalues of BB do not exceed the corresponding ordered eigenvalues of CC.

For an operator MM, s1(M)≥s2(M)≥⋯s_1(M)\ge s_2(M)\ge\cdots are its singular values, the square roots of the eigenvalues of MM∗MM^*. The Hilbert–Schmidt norm is

∥M∥HS2=Tr⁡(MM∗)=∑jsj(M)2.\lVert M\rVert_{\mathrm{HS}}^2=\operatorname{Tr}(MM^*)=\sum_j s_j(M)^2.

We will use the Schatten–Hölder inequality in the simple form

∥Mm∥HS2≤∑jsj(M)2m.\|M^m\|_{\mathrm{HS}}^2 \le\sum_j s_j(M)^{2m}.

This is important because KK is not normal: one cannot replace singular-value arguments by powers of a Loewner inequality.

The regular representation and partitions of $n`

A partition λ⊢n\lambda\vdash n is a nonincreasing sequence λ1≥λ2≥⋯≥0\lambda_1 \ge\lambda_2 \ge\cdots\ge0 with sum nn. Its Young diagram has λi\lambda_i boxes in row ii; λ′\lambda' denotes the conjugate partition obtained by exchanging rows and columns. The irreducible complex representations of Sn\mathfrak{S}_n are indexed by partitions λ⊢n\lambda\vdash n. We denote the irreducible module by VλV_\lambda and its dimension by dλd_\lambda.

The regular representation decomposes as

C[Sn]≅⨁λ⊢ndλVλ.\mathbb{C}[\mathfrak{S}_n] \cong\bigoplus_{\lambda\vdash n} d_\lambda V_\lambda.

Therefore, if an operator is built from the group action and hence respects this decomposition,

Tr⁡C[Sn]T=∑λ⊢ndλTr⁡VλT.\operatorname{Tr}_{\mathbb{C}[\mathfrak{S}_n]} T = \sum_{\lambda\vdash n} d_\lambda\operatorname{Tr}_{V_\lambda} T.

The integer

r=n−λ1r=n-\lambda_1

will be called the first-row deficit. It measures how far VλV_\lambda is from the trivial representation (n)(n) and is the natural parameter in the trace estimates below.

If ν⊢r\nu\vdash r, let fνf^\nu denote the number of standard Young tableaux of shape ν\nu. Equivalently, fν=dim⁡Vνf^\nu=\dim V_\nu. Young branching implies that the permutation representation on ordered injective rr-tuples,

C[Ωn,r]≅Ind⁡Sn−rSn1,\mathbb{C}[\Omega_{n,r}] \cong\operatorname{Ind}_{\mathfrak{S}_{n-r}}^{\mathfrak{S}_n} \mathbf{1},

contains exactly fνf^\nu copies of V(n−r,ν)V_{(n-r,\nu)}. We will also use

∑ν⊢r(fν)2=r!,\sum_{\nu\vdash r}(f^\nu)^2=r!,

which is simply the dimension identity for the regular representation of Sr\mathfrak{S}_r. These facts, the branching rule, and the content formula used later are standard; see [12].

For 1≤r≤n−11\le r\le n-1, let

Ωn,r={(x1,…,xr)∈[n]r:xa≠xb for a≠b}\Omega_{n,r}=\{(x_1,\ldots,x_r)\in[n]^r:x_a\ne x_b\text{ for }a\ne b\}

be the ordered injective tuples. For each coordinate aa, the deletion marginal CaFC_aF is obtained by summing FF over all allowed values of xax_a, with the remaining coordinates fixed. The deletion-harmonic space is

Hn,r=⋂a=1rker⁡Ca.H_{n,r}=\bigcap_{a=1}^{r}\ker C_a.

Each CaC_a intertwines the action of Sn\mathfrak{S}_n, so Hn,rH_{n,r} is invariant. The role of Hn,rH_{n,r} is to retain precisely enough copies of the deficit-rr irreducibles while forcing every coordinate to be mean zero after zero extension to [n]r[n]^r.

A notation guide

The symbols that recur most often are collected here.

SymbolMeaning
RRone-elementary-move Rudvalis Markov operator.
KKone full rotating-frame sweep, equal to Pn−1⋯P0P_{n-1}\cdots P_0 and corresponding to nn elementary moves.
PiP_i, AiA_iadjacent averaging projection (I+Usi)/2(I+U_{s_i})/2 and its loss projection I−PiI-P_i.
LQL_Qself-adjoint weighted interchange operator with one weak cycle edge of weight 1/Q1/Q.
ℓQ\ell_Qone-card operator corresponding to LQL_Q.
Zn,Q(t)Z_{n,Q}(t)regular-representation heat trace Tr⁡C[Sn]e−tLQ\operatorname{Tr}_{\mathbb{C}[S_n]}e^{-tL_Q}.
Tn,r(t)T_{n,r}(t)part of that trace coming from partitions with first-row deficit rr.
Hn,rH_{n,r}deletion-harmonic functions on ordered injective rr-tuples.
λn\lambda_nexact one-card eigenvalue of one elementary Rudvalis move near e2πi/ne^{2\pi i/n}.
Λn=λnn\Lambda_n=\lambda_n^ncorresponding eigenvalue after one sweep.
Z(σ)Z(\sigma)normalized complex deck statistic obtained by pairing label and position copies of the one-card eigenfunction.

Table 1.

Symmetric comparison and transfer to the Rudvalis sweep

For cycle sites Z/nZ\mathbb{Z}/n\mathbb{Z}, put

si=(i,i+1),Pi=(I+Usi)/2,Ai=I−Pi,K=Pn−1⋯P0.s_i=(i,i+1),\qquad P_i=(I+U_{s_i})/2,\qquad A_i=I-P_i,\qquad K=P_{n-1}\cdots P_0.

For an integer Q≥1Q\ge1, define

LQ=Q−1A0+∑i=1n−1Ai,cQ=1+5/Q4,Zn,Q(t)=Tr⁡C[Sn]e−tLQ.L_Q=Q^{-1}A_0+\sum_{i=1}^{n-1}A_i,\qquad c_Q=\frac{1+5/Q}{4},\qquad Z_{n,Q}(t)=\operatorname{Tr}_{\mathbb{C}[S_n]}e^{-tL_Q}.

Its one-card positive operator ℓQ\ell_Q has jump rates 1/21/2 on ordinary edges and 1/(2Q)1/(2Q) on the weak edge. Hence P=I−ℓQP=I-\ell_Q is symmetric stochastic.

Octopus smoothing and harmonic zero extension

For a symmetric stochastic matrix PP put

L(P)=∑x<yP(x,y)(I−U(xy)).\mathcal{L}(P)=\sum_{x<y}P(x,y)(I-U_{(xy)}).

The following consequence of the octopus theorem [1] is also Proposition 3 of [8]. We use only its interchange comparison, not an exclusion cutoff theorem.

Lemma 3.1 (Dynamical comparison). For every τ≥0\tau\ge0, in every unitary representation,

L(e−τ(I−P))⪯τL(P).\mathcal{L}\left(e^{-\tau(I-P)}\right)\preceq\tau\mathcal{L}(P).

Proof. Write Dxy=I−U(xy)D_{xy}=I-U_{(xy)} and Dxx=0D_{xx}=0. The octopus inequality at oo, multiplied by the total off-diagonal incident weight, gives

(1−P(o,o))∑xP(o,x)Dox⪰12∑x,y≠oP(o,x)P(o,y)Dxy.\left(1-P(o,o)\right)\sum_x P(o,x)D_{ox}\succeq\frac{1}{2}\sum_{x,y\ne o}P(o,x)P(o,y)D_{xy}.

Adding the terms with exactly one of x,yx,y equal to oo gives

∑xP(o,x)Dox⪰12∑x,yP(o,x)P(o,y)Dxy.\sum_x P(o,x)D_{ox}\succeq\frac{1}{2}\sum_{x,y}P(o,x)P(o,y)D_{xy}.

Sum in oo to get 2L(P)⪰L(P2)2\mathcal{L}(P)\succeq\mathcal{L}(P^2). Apply this repeatedly to (1−τ/2k)I+(τ/2k)P\left(1-\tau/2^k\right)I+\left(\tau/2^k\right)P for 2k≥τ2^k\ge\tau, and let kk increase. The octopus inequality in the regular representation implies it in every irreducible and hence every unitary direct sum.

Let Ωn,r\Omega_{n,r} be the ordered injective rr-tuples of sites. Let Hn,rH_{n,r} be the common kernel of the rr deletion marginals, each marginal summing over the allowed values of the deleted coordinate. Use counting weight n−rn^{-r} on both Ωn,r\Omega_{n,r} and the full product [n]r[n]^r. Zero extension J0J_0 is then isometric and maps Hn,rH_{n,r} into (1⊥)⊗r(1^\perp)^{\otimes r}. Deletion intertwines every site permutation, so Hn,rH_{n,r} is invariant for every interchange operator.

Set pτ=e−τLQp_\tau=e^{-\tau L_Q}, p∗=max⁡x,ypτ(x,y)p_*=\max_{x,y}p_\tau(x,y), and Aτ=∑a=1r(I−pτ)aA_\tau=\sum_{a=1}^r(I-p_\tau)_a on the product. Let 0=γ0<γ1≤⋯≤γn−10=\gamma_0<\gamma_1\le\cdots\le\gamma_{n-1} be the one-card eigenvalues.

Lemma 3.2 (Exact collision identity and trace bound). For every tuple function FF,

⟨J0F,AτJ0F⟩=⟨F,L(pτ)F⟩−Eswap(F)+n−r∑x∈Ωn,rVτ(x)∣F(x)∣2,\langle J_0F,A_\tau J_0F\rangle=\langle F,\mathcal{L}(p_\tau)F\rangle-\mathcal{E}_{\mathrm{swap}}(F)+n^{-r}\sum_{x\in\Omega_{n,r}}V_\tau(x)|F(x)|^2,

where Eswap≥0\mathcal{E}_{\mathrm{swap}}\ge0 is the tracked-label exchange energy and Vτ(x)=∑a≠bpτ(xa,xb)≤r(r−1)p∗V_\tau(x)=\sum_{a\ne b}p_\tau(x_a,x_b)\le r(r-1)p_*. Consequently,

Tr⁡Hn,re−tLQ≤exp⁡(tτr(r−1)p∗)[∑k=1n−1exp⁡{−tτ(1−e−τγk)}]r.(3)\operatorname{Tr}_{H_{n,r}}e^{-tL_Q}\le\exp\left(\frac{t}{\tau}r(r-1)p_*\right)\left[\sum_{k=1}^{n-1}\exp\left\{-\frac{t}{\tau}\left(1-e^{-\tau\gamma_k}\right)\right\}\right]^r. \tag*{(3)}

Proof. In the product Dirichlet form, a jump between two injective tuples is exactly a tracked-label-to-hole move. A jump from an injective tuple to a collision has terminal value zero; its two orientations cancel the form’s factor 1/21/2 and give the displayed killing term. Edges between collision tuples contribute zero. These observations give the identity and, by Lemma 3.1, the inequality

⟨J0F,AτJ0F⟩≤τ⟨F,LQF⟩+r(r−1)p∗∥F∥2.\langle J_0F,A_\tau J_0F\rangle\le\tau\langle F,L_QF\rangle+r(r-1)p_*\lVert F\rVert^2.

On (1⊥)⊗r(1^\perp)^{\otimes r} the product spectrum is the multiset ξ=∑a(1−e−τγka)\xi=\sum_a(1-e^{-\tau\gamma_{k_a}}) with every ka≥1k_a\ge1. If λj\lambda_j are the ordered eigenvalues on Hn,rH_{n,r}, min–max on the isometric image of the first jj eigenvectors gives τλj+r(r−1)p∗≥ξj\tau\lambda_j+r(r-1)p_*\ge\xi_j. Exponentiate these scalar inequalities, sum, and enlarge the sum to the full product spectrum. This proves (3).

Regular multiplicities and a rough sector gap

For a partition λ⊢n\lambda\vdash n, write dλ=dim⁡Vλd_\lambda=\dim V_\lambda, and call r=n−λ1r=n-\lambda_1 its first-row deficit. Define

Tn,r(t)=∑λ:n−λ1=rdλTr⁡Vλe−tLQ.T_{n,r}(t)=\sum_{\lambda:n-\lambda_1=r}d_\lambda\operatorname{Tr}_{V_\lambda}e^{-tL_Q}.

Lemma 3.3 (Multiplicity and gap). For every 1≤r≤n−11 \le r \le n-1,

Tn,r(t)≤(nr)Tr⁡Hn,re−tLQ,(4)T_{n,r}(t) \le\binom{n}{r}\operatorname{Tr}_{H_{n,r}} e^{-tL_Q}, \tag*{(4)}
LQ∣Vλ⪰r2n2Iwhen n−λ1=r.(5)L_Q|_{V_\lambda} \succeq\frac{r}{2n^2}I \quad\text{when } n-\lambda_1=r. \tag*{(5)}

Proof. Write λ=(n−r,ν)\lambda=(n-r,\nu). Young branching in C[Ωn,r]=Ind⁡Sn−rSn1\mathbb{C}[\Omega_{n,r}]=\operatorname{Ind}_{\mathfrak{S}_{n-r}}^{\mathfrak{S}_n}\mathbf{1} gives fνf^\nu copies of VλV_\lambda. Every deletion target has first row at least n−r+1n-r+1, so all these copies are harmonic. A standard tableau of shape λ\lambda is determined injectively by the set of its rr entries below the first row and the standardized lower tableau. Thus dλ≤(nr)fνd_\lambda\le\binom{n}{r}f^\nu. This proves (4).

For an ordinary bb-site path set

Lbpath=12∑i=1b−1(I−U(i,i+1)),Cb=∑i<j(I−U(ij)).L_b^{\mathrm{path}}=\frac{1}{2}\sum_{i=1}^{b-1}(I-U_{(i,i+1)}),\qquad C_b=\sum_{i<j}(I-U_{(ij)}).

Express (i,j)(i,j) as an adjacent word of length 2(j−i)−12(j-i)-1. Telescoping the unitary word and applying Cauchy–Schwarz gives a quadratic-form comparison. The total coefficient at edge kk is at most

4∑i≤k<j(j−i)=2bk(b−k)≤b3/2.4\sum_{i\le k<j}(j-i)=2bk(b-k)\le b^3/2.

Since ∥(I−Us)F∥2=2⟨F,(I−Us)F⟩\lVert(I-U_s)F\rVert^2=2\langle F,(I-U_s)F\rangle, this yields Cb⪯b3LbpathC_b\preceq b^3L_b^{\mathrm{path}}. The central transposition scalar on VλV_\lambda is

cλ=(b2)−∑i(λi2)+∑j(λj′2)≥br/2,r=b−λ1.c_\lambda=\binom{b}{2}-\sum_i\binom{\lambda_i}{2}+\sum_j\binom{\lambda'_j}{2}\ge br/2,\qquad r=b-\lambda_1.

Indeed every row is at most b−rb-r, so the negative row sum is at most b(b−r−1)/2b(b-r-1)/2. These standard branching and content identities are recorded, for example, in [12]. Deleting the weak edge of LQL_Q leaves an ordinary nn-site path, proving (5).

Lemma 3.4 (Path trace). For every u≥0u\ge0,

Zbpath(u):=Tr⁡C[Sb]e−uLbpath≤exp⁡(b2e−u/(2b2)).Z_b^{\mathrm{path}}(u):=\operatorname{Tr}_{\mathbb{C}[\mathfrak{S}_b]}e^{-uL_b^{\mathrm{path}}}\le\exp\left(b^2e^{-u/(2b^2)}\right).

Proof. The tableau bound and ∑ν⊢r(fν)2=r!\sum_{\nu\vdash r}(f^\nu)^2=r! give ∑λ:b−λ1=rdλ2≤b2r/r!\sum_{\lambda:b-\lambda_1=r}d_\lambda^2\le b^{2r}/r!. Apply the gap in Lemma 3.3, include the trivial representation, and sum the exponential series. For b=1b=1 the claimed bound also holds.

The sweep endpoint, resolvent, and Gamma transfer

Lemma 3.5 (Nonnormal-safe transfer). For every integer m≥1m\ge1 and 0<ω<10<\omega<1,

K∗LQK⪯cQ(I−K∗K),(6)K^*L_QK\preceq c_Q(I-K^*K), \tag*{(6)}
χn2(nm)≤Tr⁡(I+LQ/cQ)−m−1(7)\chi_n^2(nm)\le\operatorname{Tr}(I+L_Q/c_Q)^{-m}-1 \tag*{(7)}
≤Zn,Q((1−ω)m/cQ)−1+(n!−1)e−mω2/2.(8)\le Z_{n,Q}((1-\omega)m/c_Q)-1+(n!-1)e^{-m\omega^2/2}. \tag*{(8)}

Proof. Put g0=Fg_0=F, gi+1=Pigig_{i+1}=P_ig_i, di=Aigid_i=A_ig_i, and G=KFG=KF. Orthogonality at each individual projection gives D:=∥F∥2−∥G∥2=∑i∥di∥2D:=\lVert F\rVert^2-\lVert G\rVert^2=\sum_i\lVert d_i\rVert^2. For neighboring transpositions s,ts,t, let CstC_{st} denote

the orthogonal projector onto the sign representation of the three-site subgroup they generate, namely

Cst=16∑g∈⟨s,t⟩sgn⁡(g)Ug.C_{st} = \frac{1}{6}\sum_{g\in\langle s,t\rangle}\operatorname{sgn}(g)U_g.

A direct multiplication in the group algebra gives

AsAtAs=14As+34Cst.A_sA_tA_s = \frac{1}{4}A_s+\frac{3}{4}C_{st}.

This is verified directly in the six-element group algebra. If Pshh=hP_{\mathrm{sh}}h=h, the alternating part of hh vanishes, and the identity with s,ts,t reversed gives ∥AsAth∥2=∥Ath∥2/4\lVert A_sA_th\rVert^2=\lVert A_th\rVert^2/4. For 1≤i≤n−21\le i\le n-2, later disjoint projections commute with AiA_i, hence

AiG=−Pn−1⋯Pi+2AiAi+1di+1.A_iG=-P_{n-1}\cdots P_{i+2}A_iA_{i+1}d_{i+1}.

The required preceding-average hypothesis holds for h=gi+1h=g_{i+1}. Thus ∑i=1n−2∥AiG∥2≤D/4\sum_{i=1}^{n-2}\lVert A_iG\rVert^2\le D/4, while An−1G=0A_{n-1}G=0. At the seam,

A0G=−Pn−2⋯P2A0d1−A0dn−1,∥A0G∥≤12∥d1∥+∥dn−1∥,A_0G=-P_{n-2}\cdots P_2A_0d_1-A_0d_{n-1},\qquad\lVert A_0G\rVert\le\frac{1}{2}\lVert d_1\rVert+\lVert d_{n-1}\rVert,

so ∥A0G∥2≤5D/4\lVert A_0G\rVert^2\le5D/4. Weighting this edge by 1/Q1/Q proves (6).

The operator (I+LQ/cQ)1/2K(I+L_Q/c_Q)^{1/2}K is a contraction, implying KK∗⪯(I+LQ/cQ)−1KK^*\preceq(I+L_Q/c_Q)^{-1}. Ordered eigenvalue comparison bounds each squared singular value. Schatten–Hölder then gives

∥Km∥HS2≤∑jsj(K)2m≤Tr⁡(I+LQ/cQ)−m.\lVert K^m\rVert_{\mathrm{HS}}^2\le\sum_j s_j(K)^{2m}\le\operatorname{Tr}(I+L_Q/c_Q)^{-m}.

Convolution transitivity implies 1+χn2(nm)=∥Km∥HS21+\chi_n^2(nm)=\lVert K^m\rVert_{\mathrm{HS}}^2. Finally, for UmU_m Gamma with shape mm and rate one, (1+x)−m=Ee−xUm(1+x)^{-m}=\mathbb{E}e^{-xU_m}. Split the resulting expected trace at (1−ω)m(1-\omega)m, use its monotonicity and Z(0)=n!Z(0)=n!, and apply P(Um<(1−ω)m)≤e−mω2/2\mathbb{P}(U_m<(1-\omega)m)\le e^{-m\omega^2/2}.

A sharp-window full-deck chi-square bound

Two improvements remove the fixed-slack restriction without an unproved uniformity assertion.

A heat-kernel bound uniform in the weak-edge weight

Lemma 4.1 (Uniform kernel and subdivision bounds). For every integer Q≥1Q\ge1 and every τ>0\tau>0,

max⁡x,ye−τℓQ(x,y)≤1n+2πτ.(9)\max_{x,y}e^{-\tau\ell_Q}(x,y)\le\frac{1}{n}+\sqrt{\frac{2\pi}{\tau}}. \tag*{(9)}

Also, with N=n+Q−1N=n+Q-1,

γj≥2sin⁡2(π⌈j/2⌉N),1≤j≤n−1.(10)\gamma_j\ge2\sin^2\left(\frac{\pi\lceil j/2\rceil}{N}\right),\qquad1\le j\le n-1. \tag*{(10)}

Proof. Delete the weak edge. On the remaining ordinary path choose a vertex where ∣f∣2≤∥f∥22/n\lvert f\rvert^2\le\lVert f\rVert_2^2/n, with unnormalized counting norm. Along the unique path from that vertex to xx, telescope ∣f∣2\lvert f\rvert^2 and apply Cauchy–Schwarz:

∣f(x)∣2≤∥f∥22n+2∥f∥2(∑path∣∇f∣2)1/2≤∥f∥22n+22 ∥f∥2⟨f,ℓQf⟩.\lvert f(x)\rvert^2\le\frac{\lVert f\rVert_2^2}{n}+2\lVert f\rVert_2\left(\sum_{\mathrm{path}}\lvert\nabla f\rvert^2\right)^{1/2}\le\frac{\lVert f\rVert_2^2}{n}+2\sqrt{2}\,\lVert f\rVert_2\sqrt{\langle f,\ell_Qf\rangle}.

The diagonal of the spectral projection onto eigenvalues at most uu is therefore at most n−1+22un^{-1}+2\sqrt{2u}. Integration against τe−τu\tau e^{-\tau u} gives the diagonal bound (9). Positive semidefiniteness of the heat kernel bounds every off-diagonal entry by the geometric mean of the two diagonal entries. This argument never pays QQ.

For (10), replace the weak edge by QQ ordinary edges. Linear interpolation on the inserted path preserves the one-card counting energy and increases counting norm. This injective map, applied to initial spectral subspaces including constants, gives the ordered eigenvalue comparison with the ordinary NN-cycle.

A block entrance estimate in each deficit sector

Lemma 4.2 (Sectorwise entrance). For sufficiently large nn, put

b=⌊n12log⁡n⌋,B=⌈n/b⌉,u=n2.b=\left\lfloor\frac{n}{\sqrt{12\log n}}\right\rfloor,\qquad B=\lceil n/b\rceil,\qquad u=n^2.

Uniformly in Q≥1Q\ge1 and 1≤r≤n−11\le r\le n-1,

Tn,r(u)≤(nr)Bre−n−4.(11)T_{n,r}(u)\le\binom{n}{r}B^r e^{-n^{-4}}. \tag*{(11)}

Consequently for t≥ut\ge u,

Tn,r(t)≤en−4(nr)Brexp⁡(−(t−u)r2n2).(12)T_{n,r}(t)\le e^{n^{-4}}\binom{n}{r}B^r\exp\left(-\frac{(t-u)r}{2n^2}\right). \tag*{(12)}

Proof. Partition the ordinary path into BB consecutive blocks of sizes bi≤bb_i\le b, and discard the interblock edges. On the ordered-tuple module, min–max gives

Tr⁡Ωn,re−uLQ≤Tr⁡Ωn,re−uLblocks.\operatorname{Tr}_{\Omega_{n,r}}e^{-uL_Q}\le\operatorname{Tr}_{\Omega_{n,r}}e^{-uL_{\mathrm{blocks}}}.

The block subgroup orbits are specified by assigning a block to each tracked label, so there are at most BrB^r orbits. An orbit with occupancies kik_i is the product of the ordered kik_i-tuple modules inside the blocks. Each such permutation module has irreducible multiplicities at most their dimensions, so its heat trace is at most the corresponding regular trace. Thus

Tr⁡Ωn,re−uLblocks≤Br∏iZbipath(u)≤Brexp⁡(∑ibi2e−n2/(2bi2))≤Bre−n−4.\operatorname{Tr}_{\Omega_{n,r}}e^{-uL_{\mathrm{blocks}}}\le B^r\prod_i Z^{\mathrm{path}}_{b_i}(u)\le B^r\exp\left(\sum_i b_i^2e^{-n^2/(2b_i^2)}\right)\le B^re^{-n^{-4}}.

Here ∑ibi2≤n2\sum_i b_i^2\le n^2 and n2/(2bi2)≥6log⁡nn^2/(2b_i^2)\ge6\log n. Combine with (4) and the fact that the harmonic trace is at most the whole tuple trace. Finally split the exponential at uu in each deficit-rr eigenvalue and use (5).

Small, intermediate, and large deficits at the exact window

Proposition 4.3 (Sharp static upper profile). Put Qn=⌈(log⁡n)2⌉Q_n=\lceil(\log n)^2\rceil. For any bounded sequence sn→ss_n\to s,

lim sup⁡n→∞[Zn,Qn(n22π2(log⁡n+2sn))−1]≤exp⁡(2e−2s)−1.\limsup_{n\to\infty}\left[Z_{n,Q_n}\left(\frac{n^2}{2\pi^2}(\log n+2s_n)\right)-1\right]\le\exp(2e^{-2s})-1.

Proof. Write L=log⁡n+2snL=\log n+2s_n and choose the explicit auxiliary parameters

a=n−1/250,τ=an22π2,Rn=⌊n99/100⌋,t=n2L2π2.a=n^{-1/250},\qquad\tau=\frac{a n^2}{2\pi^2},\qquad R_n=\left\lfloor n^{99/100}\right\rfloor,\qquad t=\frac{n^2L}{2\pi^2}.

They are not claimed optimal. Lemma 4.1 gives p∗≤n−1(1+2π3/2a−1/2)p_* \le n^{-1}(1+2\pi^{3/2}a^{-1/2}). For r≤Rnr\le R_n,

1rtτr(r−1)p∗≤LaRnn(1+2π3/2a−1/2)=O(n−1/250log⁡n)=o(1).(13)\frac{1}{r}\frac{t}{\tau}r(r-1)p_* \le\frac{L}{a}\frac{R_n}{n}(1+2\pi^{3/2}a^{-1/2})=O(n^{-1/250}\log n)=o(1). \tag*{(13)}

The first two subdivision eigenvalues are at least (2π2/n2)(1−O(Qn/n))(2\pi^2/n^2)(1-O(Q_n/n)), while every eigenvalue with index at least three is at least (8π2/n2)(1−O(Qn/n))(8\pi^2/n^2)(1-O(Q_n/n)). Since alog⁡n→0a\log n\to0 and (Qn/n)log⁡n→0(Q_n/n)\log n\to0,

zn:=∑k=1n−1exp⁡[−La(1−e−τγk)]z_n:=\sum_{k=1}^{n-1}\exp\left[-\frac{L}{a}(1-e^{-\tau\gamma_k})\right]
≤2exp⁡(−L+o(1))+(n−3)exp⁡(−4L+o(1))=2e−2s+o(1)n.\le2\exp(-L+o(1))+(n-3)\exp(-4L+o(1))=\frac{2e^{-2s}+o(1)}{n}.

The o(1)o(1) errors in the displayed exponents are absolute, not only relative to LL. This follows from 1−e−x=x+O(x2)1-e^{-x}=x+O(x^2) at the two lower spectral bounds; monotonicity handles every higher eigenvalue without expanding it individually.

Combining (3), (4), and (13) gives a sequence An→2e−2sA_n\to2e^{-2s} such that, uniformly for 1≤r≤Rn1\le r\le R_n,

Tn,r(t)≤Anrr!.T_{n,r}(t)\le\frac{A_n^r}{r!}.

Therefore the sum in this entire range has limsup at most exp⁡(2e−2s)−1\exp(2e^{-2s})-1.

For r>Rnr>R_n, use Lemma 4.2 and (nr)≤(en/r)r\binom{n}{r}\le(en/r)^r. Since B≍log⁡nB\asymp\sqrt{\log n},

Tn,r(t)≤en−4[enBrexp⁡(−log⁡n+2sn4π2+12)]r.T_{n,r}(t)\le e^{n^{-4}}\left[\frac{enB}{r}\exp\left(-\frac{\log n+2s_n}{4\pi^2}+\frac{1}{2}\right)\right]^r.

For these rr, the logarithm of the bracket is at most

−κlog⁡n+12log⁡log⁡n+Os(1),κ=14π2−1100>0.-\kappa\log n+\frac{1}{2}\log\log n+O_s(1),\qquad\kappa=\frac{1}{4\pi^2}-\frac{1}{100}>0.

For large nn it is at most −κlog⁡n/2-\kappa\log n/2. Summing the resulting bound over at most nn deficits gives a quantity tending to zero. Every nontrivial shape is covered. □

Corollary 4.4 (Full-deck chi-square upper profile). For any integer sequence

mn=n28π2(log⁡n+2s+o(1)),m_n=\frac{n^2}{8\pi^2}(\log n+2s+o(1)),
lim sup⁡nχn2(nmn)≤exp⁡(2e−2s)−1.(14)\limsup_n\chi_n^2(nm_n)\le\exp(2e^{-2s})-1. \tag*{(14)}

In particular the full-deck densities have bounded L2(π)L^2(\pi) norm at every fixed window parameter.

Proof. Use Lemma 3.5 with Qn=⌈(log⁡n)2⌉Q_n=\lceil(\log n)^2\rceil and ω=n−1/4\omega=n^{-1/4}. Then

(1−ω)mncQn=n22π2(log⁡n+2s+o(1)),\frac{(1-\omega)m_n}{cQ_n}=\frac{n^2}{2\pi^2}(\log n+2s+o(1)),

because (log⁡n)/Qn→0(\log n)/Q_n\to0 and ωlog⁡n→0\omega\log n\to0. The Gamma error is at most exp⁡[nlog⁡n−Θ(n3/2log⁡n)]→0\exp[n\log n-\Theta(n^{3/2}\log n)]\to0. Apply Proposition 4.3. □

An exact eigenfunction and its elementary-move noise

Here positions are numbered 1,…,n1,\ldots,n as in the deck definition.

Lemma 5.1 (Spectral root and eigenvector). For all sufficiently large nn there is a root λn=ezn\lambda_n=e^{z_n} of

λnn−2(2λn−1)=1(15)\lambda_n^{n-2}(2\lambda_n-1)=1 \tag*{(15)}

with

zn=2πin−4π2n3+O(n−4).z_n=\frac{2\pi i}{n}-\frac{4\pi^2}{n^3}+O(n^{-4}).

Define Λn=λnn\Lambda_n=\lambda_n^n, γn=−log⁡∣Λn∣\gamma_n=-\log|\Lambda_n|, and choose θn=arg⁡Λn\theta_n=\arg\Lambda_n close to zero. Then

γn=4π2n2+O(n−3),θn=O(n−3).\gamma_n=\frac{4\pi^2}{n^2}+O(n^{-3}),\qquad\theta_n=O(n^{-3}).

There is an exact one-card eigenfunction ϕn\phi_n with eigenvalue λn\lambda_n such that

∑xϕn(x)=0,∑x∣ϕn(x)∣2=n,max⁡x∣ϕn(x)∣≤2,(16)\sum_x\phi_n(x)=0,\qquad\sum_x|\phi_n(x)|^2=n,\qquad\max_x|\phi_n(x)|\leq2, \tag*{(16)}

and

∣ϕn(n)−ϕn(n−1)∣=O(n−1),∣∑xϕn(x)2∣=O(1).(17)|\phi_n(n)-\phi_n(n-1)|=O(n^{-1}),\qquad\left|\sum_x\phi_n(x)^2\right|=O(1). \tag*{(17)}

Proof. On the analytic branch at zero,

(n−2)z+log⁡(2ez−1)=nz−z2+O(z3).(n-2)z+\log(2e^z-1)=nz-z^2+O(z^3).

The equation with right side 2πi2\pi i has a unique solution in a disk of radius C/n3C/n^3 about 2πi/n2\pi i/n: solve it by the contraction z↦[2πi−{log⁡(2ez−1)−2z}]/nz\mapsto[2\pi i-\{\log(2e^z-1)-2z\}]/n on this disk, with CC sufficiently large. One substitution gives the stated expansion. In particular ∣λn∣<1|\lambda_n|<1 eventually.

Before normalization set

ϕn(x)=λn−(x−1)(1≤x≤n−1),ϕn(n)=1.\phi_n(x)=\lambda_n^{-(x-1)}\quad(1\leq x\leq n-1),\qquad\phi_n(n)=1.

For positions 2,…,n−12,\ldots,n-1 a card moves deterministically one place up. At positions 11 and nn the one-card operator averages the values at n−1,nn-1,n. Equation (15) therefore gives the eigenfunction relation at every site. The one-card matrix is doubly stochastic, so the eigenfunction has zero sum. Normalize its squared norm to nn.

At the first n−1n-1 sites it differs from e−2πi(x−1)/ne^{-2\pi i(x-1)/n} by O(n−2)O(n^{-2}), before a normalization factor 1+O(n−2)1+O(n^{-2}); at the last site the difference is O(n−1)O(n^{-1}). Thus its squared sum is O(1)O(1) (in fact O(n−1)O(n^{-1})). Also ϕn(n−1)=(2λn−1)ϕn(n)\phi_n(n-1)=(2\lambda_n-1)\phi_n(n), giving the boundary difference bound. The sweep eigenvalue assertions follow by multiplying znz_n by nn and subtracting its 2πi2\pi i phase.

Suppress the subscript nn and put aj=ϕ(j)‾a_j=\overline{\phi(j)}. Define the complex deck statistic

Z(σ)=1n∑x=1naσ(x)ϕ(x).(18)Z(\sigma)=\frac{1}{\sqrt n}\sum_{x=1}^n a_{\sigma(x)}\phi(x). \tag*{(18)}

It satisfies

RZ=λZ,Z(id)=n.RZ=\lambda Z,\qquad Z(\mathrm{id})=\sqrt n.

An elementary without-replacement calculation gives

EπZ=0,vn:=Eπ∣Z∣2=nn−1,qn:=EπZ2=∣∑xϕ(x)2∣2n(n−1)=O(n−2).(19)\mathbb{E}_{\pi}Z=0,\qquad v_n:=\mathbb{E}_{\pi}|Z|^2=\frac{n}{n-1},\qquad q_n:=\mathbb{E}_{\pi}Z^2=\frac{\left|\sum_x\phi(x)^2\right|^2}{n(n-1)}=O(n^{-2}). \tag*{(19)}

For example the covariance of two distinct permuted aa-values is minus their population second moment divided by n−1n-1; expanding the two sums proves all formulas.

If Zt=Z(σt)Z_t=Z(\sigma_t), let ηt+1=Zt+1−λZt\eta_{t+1}=Z_{t+1}-\lambda Z_t. Conditional on the deck, the two possible outcomes differ by

Δ(σ)=dϕn(aσ(1)−aσ(n)),dϕ=ϕ(n)−ϕ(n−1).\Delta(\sigma)=\frac{d_\phi}{\sqrt{n}}\left(a_{\sigma(1)}-a_{\sigma(n)}\right),\qquad d_\phi=\phi(n)-\phi(n-1).

Hence the centered innovation is ±Δ(σ)/2\pm\Delta(\sigma)/2, each sign with probability 1/21/2, and

E(∣ηt+1∣2∣σt)=∣dϕ∣24n∣aσt(1)−aσt(n)∣2,∣ηt+1∣≤Cn−3/2.(20)\mathbb{E}\left(|\eta_{t+1}|^2\mid\sigma_t\right)=\frac{|d_\phi|^2}{4n}\left|a_{\sigma_t(1)}-a_{\sigma_t(n)}\right|^2,\qquad|\eta_{t+1}|\le Cn^{-3/2}. \tag*{(20)}

The corresponding conditional second moment, without conjugation, is obtained by squaring both complex differences.

Concentration of the one-sweep conditional variance

For a sweep starting at σ\sigma, put

ξ=Z(σn)−ΛZ(σ0),bn(σ)=E(∣ξ∣2∣σ0=σ),cn(σ)=E(ξ2∣σ0=σ).\xi=Z(\sigma_n)-\Lambda Z(\sigma_0),\qquad b_n(\sigma)=\mathbb{E}(|\xi|^2\mid\sigma_0=\sigma),\qquad c_n(\sigma)=\mathbb{E}(\xi^2\mid\sigma_0=\sigma).

We need concentration of these conditional quantities, not just their stationary means.

Lemma 6.1 (Permutation edge-sum variance). Let a1,…,ana_1,\ldots,a_n be bounded complex numbers, with a uniform bound independent of nn. Let GG be a graph with at most nn indexed edges, allowing repetition, no loops, and degrees counting multiplicity. For deterministic complex weights ∣we∣≤1|w_e|\le1 and a uniform random permutation σ\sigma,

Eπ∣∑ewe{h(aσ(ie),aσ(je))−hˉ}∣2≤C(n+∑vdeg⁡G(v)2),\mathbb{E}_{\pi}\left|\sum_e w_e\{h(a_{\sigma(i_e)},a_{\sigma(j_e)})-\bar h\}\right|^2\le C\left(n+\sum_v\deg_G(v)^2\right),

where either h(u,v)=∣u−v∣2h(u,v)=|u-v|^2 or h(u,v)=(u−v)2h(u,v)=(u-v)^2, and hˉ\bar h is its common mean over two distinct population indices.

Proof. Each individual term is uniformly bounded. Pairs of edges sharing a vertex have bounded covariance, and their number is at most a constant times ∑vdeg⁡(v)2\sum_v\deg(v)^2. For two disjoint edges e={i,j}e=\{i,j\} and e′={k,ℓ}e'=\{k,\ell\}, let (X1,X2)(X_1,X_2) and (Y1,Y2)(Y_1,Y_2) be two independent ordered pairs sampled uniformly without replacement from the population {a1,…,an}\{a_1,\ldots,a_n\}. Their joint law conditioned on the four sampled indices being distinct is exactly the law of (aσ(i),aσ(j),aσ(k),aσ(ℓ))(a_{\sigma(i)},a_{\sigma(j)},a_{\sigma(k)},a_{\sigma(\ell)}). The probability that the two pairs share an index is at most 4/(n−1)4/(n-1). Since hh is uniformly bounded, conditioning changes any expectation of the product of the two edge observables by O(1/n)O(1/n). Without the conditioning the two edge observables are independent, so the covariance for disjoint edges is O(1/n)O(1/n). There are at most n2n^2 ordered pairs of disjoint edges. Expanding the squared absolute value of the weighted sum, and combining the disjoint-edge estimate with the shared-vertex count, proves the assertion. The same argument applies to complex weights and to the complex-valued observable (u−v)2(u-v)^2 by applying it to real and imaginary parts, or directly to complex covariance.

Lemma 6.2 (The graph exposed by one Rudvalis sweep). For a fixed sequence of fair insertion coins, view each top–bottom pair encountered during the first nn elementary moves as an edge between its two initial positions. This graph has nn edges, no loops, and

Ecoins∑vdeg⁡(v)2≤Cn.\mathbb{E}_{\mathrm{coins}}\sum_{v}\deg(v)^2 \le Cn.

The graph depends on the coins and the initial positions, not on the actual card labels.

Proof. During the first n−1n-1 moves, the top cards are successively the cards initially at positions 1,2,…,n−11,2,\ldots,n-1. At move jj the bottom card is either the initial last card or one of the already processed top cards. Join the next new vertex to this bottom vertex. A bottom insertion makes the new vertex the bottom; a second-from-bottom insertion leaves the old bottom unchanged. Thus these n−1n-1 edges form a tree with a bottom residence time dominated by a geometric random variable of success probability 1/21/2.

For a nonroot vertex, its degree is one plus its number of later children. It acquires children only if its insertion made it bottom, an event of probability 1/21/2; the ensuing child count is dominated by the same geometric variable, with first and second moments two and six. Its expected squared degree is therefore at most six. The root has the same upper bound. This gives at most 6n6n for the tree. The last move adds an edge between distinct existing vertices. Its increase of the degree-square sum is at most 4n4n, which suffices. All these statements concern positions and coins alone.

Proposition 6.3 (Conditional covariance concentration). Uniformly over decks,

∣ξ∣≤Cn−1/2,0≤bn≤Cn−2,∣cn∣≤Cn−2.(21)|\xi| \le Cn^{-1/2}, \qquad0 \le b_n \le Cn^{-2}, \qquad|c_n| \le Cn^{-2}. \tag*{(21)}

Their stationary means are

b‾n=(1−∣Λ∣2)vn,c‾n=(1−Λ2)qn.(22)\overline{b}_n=(1-|\Lambda|^2)v_n,\qquad\overline{c}_n=(1-\Lambda^2)q_n. \tag*{(22)}

Moreover,

∥bn−b‾n∥L2(π)+∥cn−c‾n∥L2(π)=O(n−5/2).(23)\left\|b_n-\overline{b}_n\right\|_{L^2(\pi)}+\left\|c_n-\overline{c}_n\right\|_{L^2(\pi)}=O(n^{-5/2}). \tag*{(23)}

Proof. Iteration of the exact one-step eigenfunction relation gives

ξ=∑j=0n−1λn−1−jηj+1.\xi=\sum_{j=0}^{n-1}\lambda^{n-1-j}\eta_{j+1}.

The uniform innovation bound proves the first inequality in (21). Conditional orthogonality of distinct martingale innovations gives

bn(σ)=∣dϕ∣24n∑j=0n−1∣λ∣2(n−1−j)E[∣aσj(1)−aσj(n)∣2∣σ0=σ].(24)b_n(\sigma)=\frac{|d_\phi|^2}{4n}\sum_{j=0}^{n-1}|\lambda|^{2(n-1-j)}\mathbb{E}\left[|a_{\sigma_j}(1)-a_{\sigma_j}(n)|^2\mid\sigma_0=\sigma\right]. \tag*{(24)}
cn(σ)=dϕ24n∑j=0n−1λ2(n−1−j)E[(aσj(1)−aσj(n))2∣σ0=σ].(25)c_n(\sigma)=\frac{d_\phi^2}{4n}\sum_{j=0}^{n-1}\lambda^{2(n-1-j)}\mathbb{E}\left[(a_{\sigma_j}(1)-a_{\sigma_j}(n))^2\mid\sigma_0=\sigma\right]. \tag*{(25)}

The remaining uniform bounds follow because the prefactors are O(n−3)O(n^{-3}) and there are nn bounded summands. At stationarity, expansion of Zn=ΛZ0+ξZ_n=\Lambda Z_0+\xi and conditional centering of ξ\xi give (22). For (23), condition on all sweep coins and apply Lemma 6.1 to the graph in Lemma 6.2. The weights in (24) or (25) are deterministic and have modulus at most one. The conditional mean over the uniform initial permutation is independent of the graph, because every edge joins two distinct positions. Average the variance bound over coins to obtain O(n)O(n) for the unscaled sum. Conditional expectation over coins is an L2L^2 contraction. Multiplying by the O(n−3)O(n^{-3}) prefactor yields a standard deviation O(n−5/2)O(n^{-5/2}), as asserted.

A Gaussian shift at the cutoff window

Take any integer sequence

mn=log⁡n/2+s+o(1)γn,s∈R,m_n = \frac{\log n/2+s+o(1)}{\gamma_n}, \qquad s\in\mathbb{R},

and define the real statistic at this observation time by

Wn,m(σ)=2 ℜ ⁣(e−imθnZ(σ)).(26)W_{n,m}(\sigma)=\sqrt{2}\,\Re\!\left(e^{-im\theta_n}Z(\sigma)\right). \tag*{(26)}

The phase is deterministic and is part of the observable, not extra randomization of the shuffle.

Proposition 7.1 (Both marginal Gaussian limits). Under π\pi and under the shuffle law after nmnnm_n elementary moves, respectively,

Wn,mn ⟹ N(0,1),Wn,mn ⟹ N ⁣(2e−s,1).W_{n,m_n}\ \Longrightarrow\ N(0,1), \qquad W_{n,m_n}\ \Longrightarrow\ N\!\left(\sqrt{2}e^{-s},1\right).

Proof. Observe the chain every nn moves and write σ[k]=σkn\sigma^{[k]}=\sigma_{kn}. Let ξk=Z(σ[k])−ΛZ(σ[k−1]).\xi_k=Z(\sigma^{[k]})-\Lambda Z(\sigma^{[k-1]}). Then

Wn,m(σ[m])=2 ℜ ⁣(e−imθΛmZ(σ[0]))+∑k=1mXn,k,W_{n,m}(\sigma^{[m]})=\sqrt{2}\,\Re\!\left(e^{-im\theta}\Lambda^m Z(\sigma^{[0]})\right)+\sum_{k=1}^{m}X_{n,k},

where Xn,k=2 ℜ ⁣(e−imθΛm−kξk)X_{n,k}=\sqrt{2}\,\Re\!\left(e^{-im\theta}\Lambda^{m-k}\xi_k\right) is a real martingale difference. Its maximum absolute value is at most Cn−1/2Cn^{-1/2}. The predictable variance sum is

Vn=∑k=1m∣Λ∣2(m−k)bn(σ[k−1])+ℜ∑k=1me−2imθΛ2(m−k)cn(σ[k−1]).(27)V_n=\sum_{k=1}^{m}|\Lambda|^{2(m-k)}b_n(\sigma^{[k-1]}) +\Re\sum_{k=1}^{m}e^{-2im\theta}\Lambda^{2(m-k)}c_n(\sigma^{[k-1]}). \tag*{(27)}

It is nonnegative and uniformly bounded, since (21) and 1−∣Λ∣2≍n−21-|\Lambda|^2\asymp n^{-2} bound both absolute sums.

Replacing conditional variances near the observation time. Fix A>0A>0 and set M=⌈A/γn⌉M=\lceil A/\gamma_n\rceil. For the late indices k>m−Mk>m-M, the density of σ[k−1]\sigma^{[k-1]} has bounded L2(π)L^2(\pi) norm depending only on s,As,A. Indeed its earliest time is (log⁡n/2+s−A+o(1))/γn(\log n/2+s-A+o(1))/\gamma_n, to which Corollary 4.4 applies; L2L^2 distance subsequently contracts under the Markov operator. Cauchy–Schwarz and (23) give

E∣bn(σ[k−1])−bˉn∣+E∣cn(σ[k−1])−cˉn∣≤Cs,An−5/2.\mathbb{E}|b_n(\sigma^{[k-1]})-\bar b_n|+\mathbb{E}|c_n(\sigma^{[k-1]})-\bar c_n|\le C_{s,A}n^{-5/2}.

Summing against the geometric weights in (27) gives total expected error at most Cs,An−1/2→0C_{s,A}n^{-1/2}\to0. For the early indices k≤m−Mk\le m-M, the uniform bounds (21) give a total absolute contribution at most Ce−2ACe^{-2A}, and the same bound holds for the corresponding stationary means. Thus first taking n→∞n\to\infty and then A→∞A\to\infty justifies replacement by stationary means in L1L^1.

For a stationary initial state, the same replacement holds directly for all indices, without the late-time density argument. The replacement of the bb sum equals

bˉn∑k=1m∣Λ∣2(m−k)=vn(1−∣Λ∣2m)⟶1.\bar b_n\sum_{k=1}^{m}|\Lambda|^{2(m-k)}=v_n(1-|\Lambda|^{2m})\longrightarrow1.

The absolute value of the replacement cc sum is at most ∣cˉn∣/(1−∣Λ∣2)=o(1)|\bar c_n|/(1-|\Lambda|^2)=o(1), by (22), (19), and ∣1−Λ2∣=O(n−2)|1-\Lambda^2|=O(n^{-2}). Consequently Vn→1V_n\to1 in L1L^1 under either initial law.

An elementary bounded-increment martingale CLT. For completeness, if real martingale differences XkX_k have maximum size δn→0\delta_n \to0, predictable variance sum Vn≤CV_n \le C, and Vn→1V_n \to1 in probability, then their sum tends to N(0,1)N(0,1). To see this, fix real uu, put Sj=∑k≤jXkS_j=\sum_{k\le j}X_k, Vj=∑k≤jE(Xk2∣Fk−1)V_j=\sum_{k\le j}\mathbb{E}(X_k^2\mid\mathcal{F}_{k-1}), and expand conditionally:

E(eiuXk∣Fk−1)=1−u22vk+Ou(δnvk),\mathbb{E}(e^{iuX_k}\mid\mathcal{F}_{k-1})=1-\frac{u^2}{2}v_k+O_u(\delta_n v_k),

because E(∣Xk∣3∣Fk−1)≤δnvk\mathbb{E}(|X_k|^3\mid\mathcal{F}_{k-1})\le\delta_n v_k. Multiplying by eu2vk/2=1+u2vk/2+Ou(vk2)e^{u^2v_k/2}=1+u^2v_k/2+O_u(v_k^2) gives a one-step compensated error Ou(δnvk+vk2)O_u(\delta_n v_k+v_k^2). Since vk≤δn2v_k\le\delta_n^2, ∑kvk≤C\sum_k v_k\le C, and therefore ∑kvk2≤Cδn2\sum_kv_k^2\le C\delta_n^2, telescoping expectations yields Eexp⁡(iuSm+u2Vm/2)=1+o(1)\mathbb{E}\exp(iuS_m+u^2V_m/2)=1+o(1). The compensated exponentials are uniformly bounded in modulus by eu2C/2e^{u^2C/2}. Boundedness and convergence of VmV_m give the characteristic function limit e−u2/2e^{-u^2/2}. Applying this result to (27) proves the centered Gaussian limit.

From the identity start, the initial term is 2n∣Λ∣m→2e−s\sqrt{2n}|\Lambda|^m\to\sqrt{2}e^{-s}. From stationarity it tends to zero in L2L^2, since Eπ∣Z∣2\mathbb{E}_{\pi}|Z|^2 is bounded and ∣Λ∣2m=O(1/n)|\Lambda|^{2m}=O(1/n). This proves both assertions. □

Remark 7.2 (No circular mixing premise). The late-time density bound comes solely from the independently proved full-deck chi-square upper bound. It does not assume the profile, a Gaussian approximation, or a coupling to stationarity. The constant Cs,AC_{s,A} may be very large; the limits are taken with AA fixed first. This is enough for the n−1/2n^{-1/2} error to vanish.

From the scalar limit to the full-deck profile

Lemma 8.1 (Gaussian likelihood-ratio saturation). Let Qn≪PnQ_n\ll P_n with likelihood ratio LnL_n, and let YnY_n be a real statistic. Suppose, for fixed a∈Ra\in\mathbb{R},

Yn⟹N(0,1)(Pn),Yn⟹N(a,1)(Qn),lim sup⁡nEPnLn2≤ea2.Y_n\Longrightarrow N(0,1)\quad(P_n),\qquad Y_n\Longrightarrow N(a,1)\quad(Q_n),\qquad\limsup_{n}\mathbb{E}_{P_n}L_n^2\le e^{a^2}.

Then

∥Qn−Pn∥TV⟶2Φ(∣a∣/2)−1,EPnLn2⟶ea2.\lVert Q_n-P_n\rVert_{\mathrm{TV}}\longrightarrow2\Phi(|a|/2)-1,\qquad\mathbb{E}_{P_n}L_n^2\longrightarrow e^{a^2}.

Moreover LnL_n under PnP_n converges in distribution to exp⁡(aG−a2/2)\exp(aG-a^2/2), where G∼N(0,1)G\sim N(0,1).

Proof. The Gaussian likelihood ratio is ℓ(y)=eay−a2/2\ell(y)=e^{ay-a^2/2}. For M>0M>0 let gM(y)=min⁡{M,ℓ(y)}g_M(y)=\min\{M,\ell(y)\}, a bounded continuous function. The two weak limits and the squared-norm bound imply

lim sup⁡nEPn(Ln−gM(Yn))2≤ea2−2EN(a,1)gM+EN(0,1)gM2\limsup_n\mathbb{E}_{P_n}(L_n-g_M(Y_n))^2\le e^{a^2}-2\mathbb{E}_{N(a,1)}g_M+\mathbb{E}_{N(0,1)}g_M^2
=EN(0,1)(ℓ−gM)2⟶0(M→∞).=\mathbb{E}_{N(0,1)}(\ell-g_M)^2\longrightarrow0\qquad(M\to\infty).

Thus LnL_n is approximated in the iterated L2L^2 sense by these bounded functions of the statistic. The inequality

∣12EPn∣Ln−1∣−12EPn∣gM(Yn)−1∣∣≤12∥Ln−gM(Yn)∥L2(Pn)\left|\frac{1}{2}\mathbb{E}_{P_n}|L_n-1|-\frac{1}{2}\mathbb{E}_{P_n}|g_M(Y_n)-1|\right|\le\frac{1}{2}\lVert L_n-g_M(Y_n)\rVert_{L^2(P_n)}

gives the TV limit, because the Gaussian TV distance is 2Φ(∣a∣/2)−12\Phi(|a|/2)-1. The same approximations give convergence in distribution of LnL_n and the lower bound lim inf⁡∥Ln∥2≥∥ℓ∥2\liminf\lVert L_n\rVert_2\ge\lVert\ell\rVert_2, matching the hypothesis.

This proof uses bounded truncations. It does not silently assume convergence of exponential moments of YnY_n, nor a direct untruncated L2L^2 approximation by ℓ(Yn)\ell(Y_n). □

Proof. First take sweep times with m=(log⁡n/2+s+o(1))/γnm=(\log n/2+s+o(1))/\gamma_n. Use Pn=πP_n=\pi, Qn=μnmQ_n=\mu_{nm}, Yn=Wn,mY_n=W_{n,m} and a=2e−sa=\sqrt{2}e^{-s}. Corollary 4.4 gives lim sup⁡EπLn2≤e2e−2s=ea2\limsup\mathbb{E}_{\pi}L_n^2\le e^{2e^{-2s}}=e^{a^2}, and Proposition 7.1 gives the two marginal Gaussian limits. Lemma 8.1 proves both profiles at sweep times.

The root expansion implies

nγn(log⁡n2+s)=n38π2(log⁡n+2s)+O(n2log⁡n).\frac{n}{\gamma_n}\left(\frac{\log n}{2}+s\right)=\frac{n^3}{8\pi^2}(\log n+2s)+O(n^2\log n).

and the error is o(n3)o(n^3). More precisely the desired integer elementary time lies between neighboring sweep times whose normalized parameters tend to the same ss. Both TV and chi-square contract under further elementary moves. Squeeze between these sweep times; the proofs above allow sn→ss_n\to s. This establishes (1)–(2).

For the likelihood-ratio statement below, we also record the scalar limit at nonsweep times rather than relying only on monotonicity. Write t=nm+jt=nm+j, 0≤j<n0\le j<n, choose αn=arg⁡λn\alpha_n=\arg\lambda_n with nαn=2π+θnn\alpha_n=2\pi+\theta_n, and set

Wn,telem(σ)=2 ℜ(e−itαnZ(σ)).W^{\mathrm{elem}}_{n,t}(\sigma)=\sqrt{2}\,\Re\left(e^{-it\alpha_n}Z(\sigma)\right).

Iterating the elementary innovations over the final jj moves gives, on every trajectory,

∣e−itαnZ(σt)−∣λn∣je−inmαnZ(σnm)∣≤Cn−1/2.\left|e^{-it\alpha_n}Z(\sigma_t)-|\lambda_n|^j e^{-inm\alpha_n}Z(\sigma_{nm})\right|\le Cn^{-1/2}.

Also 1−∣λn∣j=O(n−2)1-|\lambda_n|^j=O(n^{-2}) and ∣Z(σ)∣≤Cn|Z(\sigma)|\le C\sqrt{n} uniformly. Therefore Wn,telem(σt)W^{\mathrm{elem}}_{n,t}(\sigma_t) and Wn,m(σnm)W_{n,m}(\sigma_{nm}) differ by O(n−1/2)O(n^{-1/2}) uniformly. Under either identity or stationary initialization the same two Gaussian limits follow. Lemma 8.1, with the chi-square upper bound just obtained by squeezing, consequently applies directly at every stated elementary time as well.

Corollary 8.2 (Log-likelihood and relative entropy). At the times of Theorem 1.1, the likelihood ratio under π\pi converges in law to

exp⁡(2e−sG−e−2s).\exp\left(\sqrt{2}e^{-s}G-e^{-2s}\right).

Its logarithm therefore converges in law to N(−e−2s,2e−2s)N(-e^{-2s},2e^{-2s}). Also

D(μtn(s)∥π)⟶e−2s.D(\mu_{t_n(s)}\Vert\pi)\longrightarrow e^{-2s}.

This is a window-scale entropy profile, not a uniform nonlinear entropy contraction theorem.

Proof. Use Lemma 8.1. The limiting likelihood ratio is strictly positive, so the logarithm is a permissible continuous mapping, with any zero likelihoods treated as −∞-\infty. For relative entropy, xlog⁡xx\log x is bounded below and grows strictly slower than x2x^2 at infinity. The uniformly bounded second moments give uniform integrability of Lnlog⁡LnL_n\log L_n, and its limiting expectation is a2/2=e−2sa^2/2=e^{-2s}.

Consequences, comparison with earlier work, and reproducibility

What the theorem adds to the classical picture

Hildebrand’s upper bound and Wilson’s lower bound established the order Θ(n3log⁡n)\Theta(n^3\log n), with Wilson identifying the lower constant 1/(8π2)1/(8\pi^2) [7, 13]. Theorem 1.1 supplies the matching upper constant, proves cutoff, identifies the n3n^3 window, and determines the entire total-variation and chi-square profiles. In particular, the leading-order lower bound no longer has to be imported from Wilson: it follows from the negative-ss side of the profile itself. Wilson’s theorem remains the historical source of the sharp coefficient on the lower-bound side.

The mechanism also explains the logarithmic separation between one-card and full-deck relaxation. The slowly decaying Fourier mode has sweep contraction ∣Λn∣=exp⁡{−4π2/n2+O(n−3)}|\Lambda_n| = \exp\{-4\pi^2/n^2 + O(n^{-3})\}. Thus one copy relaxes on the order-n3n^3 sweep scale, equivalently n3n^3 elementary moves. The ordered deck begins with a coherent sum of nn copies, of size n\sqrt{n} after normalization. Reducing this signal to order one requires an additional factor 12log⁡n\frac{1}{2}\log n in the exponent, producing the n3log⁡nn^3\log n mixing scale.

The limiting likelihood ratio under stationarity is lognormal:

Ls=exp⁡(2e−sG−e−2s),G∼N(0,1).L_s = \exp\left(\sqrt{2}e^{-s}G-e^{-2s}\right), \qquad G \sim N(0,1).

Its second moment is exp⁡(2e−2s)\exp(2e^{-2s}), which matches the limiting chi-square divergence plus one. Its total-variation distance from one is the Gaussian-shift distance in (1). This equality of the full-deck L2L^2 budget with the one-dimensional Gaussian likelihood is the reason a single statistic determines the entire profile here.

Relation to exclusion and interchange methods

The smoothing step is closely related in spirit to the recent use of the Octopus Inequality in exclusion-process comparison [8]. There is, however, an important distinction. The Rudvalis sweep is nonnormal and is not itself an exclusion or interchange process. The reversible interchange operator LQL_Q is an auxiliary comparison object. The proof therefore has two additional layers: a nonnormal endpoint/resolvent transfer from KK to LQL_Q, and a full regular-representation trace estimate that pays all labelled multiplicities. These layers are what allow a reversible spectral estimate to control the original directed shuffle.

The representation-theoretic organization is also different from a fixed-density exclusion problem. The regular representation contains every partition λ⊢n\lambda\vdash n with multiplicity dλd_\lambda. The deletion-harmonic tuple spaces cover all small-to-intermediate first-row deficits with the correct factorial payment, while the sectorwise entrance estimate handles the remaining large deficits without ever paying the raw dimension n!n! at the cutoff window.

Computational checks

The proof is analytic and does not rely on numerical certification. For reproducibility, the ancillary script checks/verify_rudvalis_profile.py checks the finite-dimensional identities used in the argument on small symmetric groups and tuple modules. It verifies, among other items, the collision-energy identity, the octopus-derived matrix comparison, the endpoint and resolvent inequalities, the exact one-card eigenfunction, and the conditional covariance formulas. These checks are useful for normalization and sign errors but are not substitutes for the all-nn proofs above.

Acknowledgments

The author thanks Persi Diaconis for suggesting the problem, amongst many other interesting card shuffling problems. Gpt-6 astra pro was used extensively for derivations and polishing.

References

  1. [1]P. Caputo, T. M. Liggett, and T. Richthammer, Proof of Aldous’ spectral gap conjecture, J. Amer. Math. Soc. 23 (2010), no. 3, 831–851. doi:10.1090/S0894-0347-10-00659-4. P. Diaconis, Group Representations in Probability and Statistics, IMS Lecture Notes–Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988.
  2. [3]P. Diaconis and L. Saloff-Coste, Comparison techniques for random walk on finite groups, Ann. Probab. 21 (1993), no. 4, 2131–2156.DOI
  3. [4]P. Diaconis and L. Saloff-Coste, Random walks on finite groups: a survey of analytic techniques, in Probability Measures on Groups and Related Structures XI, World Scientific, 1995, pp. 44–75.
  4. [5]S. Goel, Analysis of top to bottom-k shuffles, Ann. Appl. Probab. 16 (2006), no. 1, 30–55. doi:10.1214/105051605000000062.
  5. [6]P. Gonçalves, M. Jara, R. Marinho, and D. Moreira, Scaling limits for Rudvalis card shuffles, Adv. in Appl. Math. 150 (2023), Article 102558. doi:10.1016/j.aam.2023.102558.DOI
  6. [7]M. Hildebrand, Rates of Convergence of Some Random Processes on Finite Groups, Ph.D. thesis, Harvard University, 1990.
  7. [8]J. Hermon, G. Kozma, and J. Salez, Universality of cutoff for the Exclusion Process, arXiv:2609.31187, 2026.arxiv.org/abs/2609.31187
  8. [9]J. Jonasson, The overhand shuffle mixes in Θ(n² log n) steps, Ann. Appl. Probab. 16 (2006), no. 1, 231–243. doi:10.1214/105051605000000692.DOI
  9. [10]H. Lacoin, Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion, Ann. Probab. 44 (2016), no. 2, 1426–1487. doi:10.1214/15-AOP1004.DOI
  10. [11]D. A. Levin and Y. Peres, with contributions by E. L. Wilmer, Markov Chains and Mixing Times, 2nd ed., American Mathematical Society, Providence, RI, 2017.
  11. [12]B. E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd ed., Graduate Texts in Mathematics, vol. 203, Springer, New York, 2001. doi:10.1007/978-1-4757-6804-6.DOI
  12. [13]D. B. Wilson, Mixing time of the Rudvalis shuffle, Electron. Commun. Probab. 8 (2003), 77–85. doi:10.1214/ECP.v8-1071.DOI

Paper details

vlnc:W_4cpqxdck
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents