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 , and Wilson later proved the sharp lower coefficient , 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 with a window of order . 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 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 labelled cards, remove the top card and place it either at the bottom or immediately above the bottom card, each with probability . 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 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 , at time
the original Rudvalis shuffle remains at total-variation distance at least from uniform [13 Theorem 1]. Thus the order 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 [13]. Jonasson later gave a streamlined route to the same order of lower bound using an -step viewpoint [9], and Goel studied the broader family of top-to-bottom- 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 be the uniform probability measure on , let be the law of the deck after elementary Rudvalis moves from a deterministic initial deck, and define
Because the shuffle is a random walk on the group , translation of the initial deck merely translates the law, and does not depend on the deterministic starting permutation.
For probability measures , define the chi-square divergence
We abbreviate .
Theorem 1.1 (Cutoff profile). For each fixed , put
Then
Here is the standard normal distribution function and .
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 under stationarity and 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 ,
In particular,
and the cutoff window has order . With the conventional centering , a natural window scale is .
Proof. The function is continuous and strictly decreasing, with as and as . Solving gives . Monotonicity of total-variation distance in time and Theorem 1.1 then bracket the level- 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 elementary moves and becomes, in a rotating coordinate frame, a product
of adjacent averaging projections around the cycle. We compare this nonnormal product to the positive weighted interchange operator
The endpoint comparison has the asymptotically sharp constant
On the other hand the first nonzero one-card eigenvalue of is asymptotic to . Hence the critical static heat-trace time is . Multiplication by the endpoint factor gives sweeps, and multiplying by moves per sweep gives the physical time .
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 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 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
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
is precisely to supply a reversible comparison object. A local three-site calculation relates the Dirichlet energy of the endpoint to the norm dissipated by the projection sweep. From this one obtains a resolvent comparison for the singular values of . This is the mechanism that transports static heat-trace estimates for back to the original directed shuffle without treating 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 of the corresponding partition. For small and intermediate deficits, deletion-harmonic functions on ordered injective -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 , with 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 , rather than paying the full dimension at the final cutoff time. Combining the harmonic-tuple estimate for moderate with the block entrance and rough gap for large 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 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 . With a suitable choice of , smoothing scale, and deficit threshold, the full regular trace at
has the precise leading contribution coming from the two lowest one-card modes. After transfer through the nonnormal resolvent estimate, this yields
The remaining task is to identify the random variable that exhausts this budget. The one-card sweep has an exact eigenvalue determined by
and its associated complex Fourier eigenfunction lifts to a normalized statistic of the entire deck. At time this statistic retains a deterministic mean of order . 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 . The martingale central limit theorem then gives a Gaussian shift: under stationarity the relevant real statistic converges to , whereas from the ordered deck it converges to .
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 , matching the full-deck limiting 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 are recalled explicitly and cited to Sagan [12].
Definitions, notation, and background
Markov-chain distances and cutoff
For probability measures on a finite set ,
If is strictly positive and , the chi-square divergence is
Cauchy–Schwarz gives
Both distances contract when the same Markov kernel is applied to both measures. For , the total-variation mixing time is
A sequence of chains exhibits total-variation cutoff at locations with windows and profile if
for each fixed real , where and . Standard background on mixing and cutoff may be found in [11, 10].
The group action and the rotating-frame sweep
Let act on deck positions on the right. For , let denote the corresponding unitary operator on functions on any permutation representation:
In particular, on this is the right regular representation. Every transposition satisfies .
Let be the cyclic positional shift that moves the top card to the bottom, and let interchange the bottom two positions. One Rudvalis move is or , each with probability ; 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 with indices understood modulo , and set
After elementary Rudvalis moves, and after conjugating by the deterministic rotating frame, the Markov operator is
Consequently estimates for are estimates for the original shuffle after elementary moves. Reversing the orientation of the deck replaces by a conjugate or transpose, which has the same singular values.
Proof. Write one step as , where is the fair average at the bottom seam. Using to move the averaging operator through a rotation, expand
Since , the deterministic rotations cancel. The conjugates of the bottom seam by successive powers of are exactly the 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 , the notation
means for every vector . This is the Loewner or quadratic-form order. If , the min–max principle implies that the ordered eigenvalues of do not exceed the corresponding ordered eigenvalues of .
For an operator , are its singular values, the square roots of the eigenvalues of . The Hilbert–Schmidt norm is
We will use the Schatten–Hölder inequality in the simple form
This is important because is not normal: one cannot replace singular-value arguments by powers of a Loewner inequality.
The regular representation and partitions of $n`
A partition is a nonincreasing sequence with sum . Its Young diagram has boxes in row ; denotes the conjugate partition obtained by exchanging rows and columns. The irreducible complex representations of are indexed by partitions . We denote the irreducible module by and its dimension by .
The regular representation decomposes as
Therefore, if an operator is built from the group action and hence respects this decomposition,
The integer
will be called the first-row deficit. It measures how far is from the trivial representation and is the natural parameter in the trace estimates below.
If , let denote the number of standard Young tableaux of shape . Equivalently, . Young branching implies that the permutation representation on ordered injective -tuples,
contains exactly copies of . We will also use
which is simply the dimension identity for the regular representation of . These facts, the branching rule, and the content formula used later are standard; see [12].
For , let
be the ordered injective tuples. For each coordinate , the deletion marginal is obtained by summing over all allowed values of , with the remaining coordinates fixed. The deletion-harmonic space is
Each intertwines the action of , so is invariant. The role of is to retain precisely enough copies of the deficit- irreducibles while forcing every coordinate to be mean zero after zero extension to .
A notation guide
The symbols that recur most often are collected here.
| Symbol | Meaning |
| one-elementary-move Rudvalis Markov operator. | |
| one full rotating-frame sweep, equal to and corresponding to elementary moves. | |
| , | adjacent averaging projection and its loss projection . |
| self-adjoint weighted interchange operator with one weak cycle edge of weight . | |
| one-card operator corresponding to . | |
| regular-representation heat trace . | |
| part of that trace coming from partitions with first-row deficit . | |
| deletion-harmonic functions on ordered injective -tuples. | |
| exact one-card eigenvalue of one elementary Rudvalis move near . | |
| corresponding eigenvalue after one sweep. | |
| 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 , put
For an integer , define
Its one-card positive operator has jump rates on ordinary edges and on the weak edge. Hence is symmetric stochastic.
Octopus smoothing and harmonic zero extension
For a symmetric stochastic matrix put
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 , in every unitary representation,
Proof. Write and . The octopus inequality at , multiplied by the total off-diagonal incident weight, gives
Adding the terms with exactly one of equal to gives
Sum in to get . Apply this repeatedly to for , and let increase. The octopus inequality in the regular representation implies it in every irreducible and hence every unitary direct sum.
Let be the ordered injective -tuples of sites. Let be the common kernel of the deletion marginals, each marginal summing over the allowed values of the deleted coordinate. Use counting weight on both and the full product . Zero extension is then isometric and maps into . Deletion intertwines every site permutation, so is invariant for every interchange operator.
Set , , and on the product. Let be the one-card eigenvalues.
Lemma 3.2 (Exact collision identity and trace bound). For every tuple function ,
where is the tracked-label exchange energy and . Consequently,
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 and give the displayed killing term. Edges between collision tuples contribute zero. These observations give the identity and, by Lemma 3.1, the inequality
On the product spectrum is the multiset with every . If are the ordered eigenvalues on , min–max on the isometric image of the first eigenvectors gives . 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 , write , and call its first-row deficit. Define
Lemma 3.3 (Multiplicity and gap). For every ,
Proof. Write . Young branching in gives copies of . Every deletion target has first row at least , so all these copies are harmonic. A standard tableau of shape is determined injectively by the set of its entries below the first row and the standardized lower tableau. Thus . This proves (4).
For an ordinary -site path set
Express as an adjacent word of length . Telescoping the unitary word and applying Cauchy–Schwarz gives a quadratic-form comparison. The total coefficient at edge is at most
Since , this yields . The central transposition scalar on is
Indeed every row is at most , so the negative row sum is at most . These standard branching and content identities are recorded, for example, in [12]. Deleting the weak edge of leaves an ordinary -site path, proving (5).
Lemma 3.4 (Path trace). For every ,
Proof. The tableau bound and give . Apply the gap in Lemma 3.3, include the trivial representation, and sum the exponential series. For the claimed bound also holds.
The sweep endpoint, resolvent, and Gamma transfer
Lemma 3.5 (Nonnormal-safe transfer). For every integer and ,
Proof. Put , , , and . Orthogonality at each individual projection gives . For neighboring transpositions , let denote
the orthogonal projector onto the sign representation of the three-site subgroup they generate, namely
A direct multiplication in the group algebra gives
This is verified directly in the six-element group algebra. If , the alternating part of vanishes, and the identity with reversed gives . For , later disjoint projections commute with , hence
The required preceding-average hypothesis holds for . Thus , while . At the seam,
so . Weighting this edge by proves (6).
The operator is a contraction, implying . Ordered eigenvalue comparison bounds each squared singular value. Schatten–Hölder then gives
Convolution transitivity implies . Finally, for Gamma with shape and rate one, . Split the resulting expected trace at , use its monotonicity and , and apply .
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 and every ,
Also, with ,
Proof. Delete the weak edge. On the remaining ordinary path choose a vertex where , with unnormalized counting norm. Along the unique path from that vertex to , telescope and apply Cauchy–Schwarz:
The diagonal of the spectral projection onto eigenvalues at most is therefore at most . Integration against 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 .
For (10), replace the weak edge by 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 -cycle.
A block entrance estimate in each deficit sector
Lemma 4.2 (Sectorwise entrance). For sufficiently large , put
Uniformly in and ,
Consequently for ,
Proof. Partition the ordinary path into consecutive blocks of sizes , and discard the interblock edges. On the ordered-tuple module, min–max gives
The block subgroup orbits are specified by assigning a block to each tracked label, so there are at most orbits. An orbit with occupancies is the product of the ordered -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
Here and . Combine with (4) and the fact that the harmonic trace is at most the whole tuple trace. Finally split the exponential at in each deficit- eigenvalue and use (5).
Small, intermediate, and large deficits at the exact window
Proposition 4.3 (Sharp static upper profile). Put . For any bounded sequence ,
Proof. Write and choose the explicit auxiliary parameters
They are not claimed optimal. Lemma 4.1 gives . For ,
The first two subdivision eigenvalues are at least , while every eigenvalue with index at least three is at least . Since and ,
The errors in the displayed exponents are absolute, not only relative to . This follows from at the two lower spectral bounds; monotonicity handles every higher eigenvalue without expanding it individually.
Combining (3), (4), and (13) gives a sequence such that, uniformly for ,
Therefore the sum in this entire range has limsup at most .
For , use Lemma 4.2 and . Since ,
For these , the logarithm of the bracket is at most
For large it is at most . Summing the resulting bound over at most 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
In particular the full-deck densities have bounded norm at every fixed window parameter.
Proof. Use Lemma 3.5 with and . Then
because and . The Gamma error is at most . Apply Proposition 4.3. □
An exact eigenfunction and its elementary-move noise
Here positions are numbered as in the deck definition.
Lemma 5.1 (Spectral root and eigenvector). For all sufficiently large there is a root of
with
Define , , and choose close to zero. Then
There is an exact one-card eigenfunction with eigenvalue such that
and
Proof. On the analytic branch at zero,
The equation with right side has a unique solution in a disk of radius about : solve it by the contraction on this disk, with sufficiently large. One substitution gives the stated expansion. In particular eventually.
Before normalization set
For positions a card moves deterministically one place up. At positions and the one-card operator averages the values at . 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 .
At the first sites it differs from by , before a normalization factor ; at the last site the difference is . Thus its squared sum is (in fact ). Also , giving the boundary difference bound. The sweep eigenvalue assertions follow by multiplying by and subtracting its phase.
Suppress the subscript and put . Define the complex deck statistic
It satisfies
An elementary without-replacement calculation gives
For example the covariance of two distinct permuted -values is minus their population second moment divided by ; expanding the two sums proves all formulas.
If , let . Conditional on the deck, the two possible outcomes differ by
Hence the centered innovation is , each sign with probability , and
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 , put
We need concentration of these conditional quantities, not just their stationary means.
Lemma 6.1 (Permutation edge-sum variance). Let be bounded complex numbers, with a uniform bound independent of . Let be a graph with at most indexed edges, allowing repetition, no loops, and degrees counting multiplicity. For deterministic complex weights and a uniform random permutation ,
where either or , and 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 . For two disjoint edges and , let and be two independent ordered pairs sampled uniformly without replacement from the population . Their joint law conditioned on the four sampled indices being distinct is exactly the law of . The probability that the two pairs share an index is at most . Since is uniformly bounded, conditioning changes any expectation of the product of the two edge observables by . Without the conditioning the two edge observables are independent, so the covariance for disjoint edges is . There are at most 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 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 elementary moves as an edge between its two initial positions. This graph has edges, no loops, and
The graph depends on the coins and the initial positions, not on the actual card labels.
Proof. During the first moves, the top cards are successively the cards initially at positions . At move 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 edges form a tree with a bottom residence time dominated by a geometric random variable of success probability .
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 ; 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 for the tree. The last move adds an edge between distinct existing vertices. Its increase of the degree-square sum is at most , which suffices. All these statements concern positions and coins alone.
Proposition 6.3 (Conditional covariance concentration). Uniformly over decks,
Their stationary means are
Moreover,
Proof. Iteration of the exact one-step eigenfunction relation gives
The uniform innovation bound proves the first inequality in (21). Conditional orthogonality of distinct martingale innovations gives
The remaining uniform bounds follow because the prefactors are and there are bounded summands. At stationarity, expansion of and conditional centering of 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 for the unscaled sum. Conditional expectation over coins is an contraction. Multiplying by the prefactor yields a standard deviation , as asserted.
A Gaussian shift at the cutoff window
Take any integer sequence
and define the real statistic at this observation time by
The phase is deterministic and is part of the observable, not extra randomization of the shuffle.
Proposition 7.1 (Both marginal Gaussian limits). Under and under the shuffle law after elementary moves, respectively,
Proof. Observe the chain every moves and write . Let Then
where is a real martingale difference. Its maximum absolute value is at most . The predictable variance sum is
It is nonnegative and uniformly bounded, since (21) and bound both absolute sums.
Replacing conditional variances near the observation time. Fix and set . For the late indices , the density of has bounded norm depending only on . Indeed its earliest time is , to which Corollary 4.4 applies; distance subsequently contracts under the Markov operator. Cauchy–Schwarz and (23) give
Summing against the geometric weights in (27) gives total expected error at most . For the early indices , the uniform bounds (21) give a total absolute contribution at most , and the same bound holds for the corresponding stationary means. Thus first taking and then justifies replacement by stationary means in .
For a stationary initial state, the same replacement holds directly for all indices, without the late-time density argument. The replacement of the sum equals
The absolute value of the replacement sum is at most , by (22), (19), and . Consequently in under either initial law.
An elementary bounded-increment martingale CLT. For completeness, if real martingale differences have maximum size , predictable variance sum , and in probability, then their sum tends to . To see this, fix real , put , , and expand conditionally:
because . Multiplying by gives a one-step compensated error . Since , , and therefore , telescoping expectations yields . The compensated exponentials are uniformly bounded in modulus by . Boundedness and convergence of give the characteristic function limit . Applying this result to (27) proves the centered Gaussian limit.
From the identity start, the initial term is . From stationarity it tends to zero in , since is bounded and . 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 may be very large; the limits are taken with fixed first. This is enough for the error to vanish.
From the scalar limit to the full-deck profile
Lemma 8.1 (Gaussian likelihood-ratio saturation). Let with likelihood ratio , and let be a real statistic. Suppose, for fixed ,
Then
Moreover under converges in distribution to , where .
Proof. The Gaussian likelihood ratio is . For let , a bounded continuous function. The two weak limits and the squared-norm bound imply
Thus is approximated in the iterated sense by these bounded functions of the statistic. The inequality
gives the TV limit, because the Gaussian TV distance is . The same approximations give convergence in distribution of and the lower bound , matching the hypothesis.
This proof uses bounded truncations. It does not silently assume convergence of exponential moments of , nor a direct untruncated approximation by . □
Proof. First take sweep times with . Use , , and . Corollary 4.4 gives , and Proposition 7.1 gives the two marginal Gaussian limits. Lemma 8.1 proves both profiles at sweep times.
The root expansion implies
and the error is . More precisely the desired integer elementary time lies between neighboring sweep times whose normalized parameters tend to the same . Both TV and chi-square contract under further elementary moves. Squeeze between these sweep times; the proofs above allow . 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 , , choose with , and set
Iterating the elementary innovations over the final moves gives, on every trajectory,
Also and uniformly. Therefore and differ by 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 converges in law to
Its logarithm therefore converges in law to . Also
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 . For relative entropy, is bounded below and grows strictly slower than at infinity. The uniformly bounded second moments give uniform integrability of , and its limiting expectation is .
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 , with Wilson identifying the lower constant [7, 13]. Theorem 1.1 supplies the matching upper constant, proves cutoff, identifies the 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- 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 . Thus one copy relaxes on the order- sweep scale, equivalently elementary moves. The ordered deck begins with a coherent sum of copies, of size after normalization. Reducing this signal to order one requires an additional factor in the exponent, producing the mixing scale.
The limiting likelihood ratio under stationarity is lognormal:
Its second moment is , 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 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 is an auxiliary comparison object. The proof therefore has two additional layers: a nonnormal endpoint/resolvent transfer from to , 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 with multiplicity . 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 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- 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]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.
- [3]P. Diaconis and L. Saloff-Coste, Comparison techniques for random walk on finite groups, Ann. Probab. 21 (1993), no. 4, 2131–2156.DOI
- [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.
- [5]S. Goel, Analysis of top to bottom-k shuffles, Ann. Appl. Probab. 16 (2006), no. 1, 30–55. doi:10.1214/105051605000000062.
- [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
- [7]M. Hildebrand, Rates of Convergence of Some Random Processes on Finite Groups, Ph.D. thesis, Harvard University, 1990.
- [8]J. Hermon, G. Kozma, and J. Salez, Universality of cutoff for the Exclusion Process, arXiv:2609.31187, 2026.arxiv.org/abs/2609.31187
- [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
- [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
- [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.
- [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
- [13]D. B. Wilson, Mixing time of the Rudvalis shuffle, Electron. Commun. Probab. 8 (2003), 77–85. doi:10.1214/ECP.v8-1071.DOI