betaFeedback

WorksMathematics

Adhesive riffle shuffles: one-parameter models and mixing bounds

Abstract

We compare four simple shuffles with one adhesion parameter pp: a card-weighted sticky riffle, a block-weighted riffle, a midpoint-interpolation shuffle, and a correlated-label inverse riffle. Independent surviving contacts create contiguous blocks; no force or energy constants are fitted. We give polynomial upper bounds with explicit dependence on pp, common adjacency-survival lower bounds, and a sharper information lower bound for interpolation. For fixed deck size n≥4n\ge4, the mixing time diverges as Θ((1−p)−1)Θ((1-p)^{-1}) for the three cut-first models, but as Θ((1−p)−2)Θ((1-p)^{-2}) for the correlated-label model. The latter distinction comes from whether one or two additional contact breaks are needed to escape cyclic rotations. For even nn, unglued interpolation retains the lower bound Ω(nlog⁡n)Ω(\sqrt n\log n) and upper bound O(n5/2log⁡n)O(n^{5/2}\log n). We distinguish proved bounds from conjectured scales, recover classical riffle cutoff under sufficiently small perturbations, and explain precisely where established results on clumpy shuffles apply. The fixed-parameter asymptotic orders of the new cut-first families and their possible cutoff remain unresolved.

Status and scope. This is an AI-assisted working manuscript, not a refereed publication. The bounds proved here are the bounds established in this draft, not claims of optimality in nn or of best-known results for every related shuffle. Standard spectral inputs and external mixing theorems are identified. Finite computations are diagnostics, not proofs of asymptotic statements. The historical survey is selective, checked through October 18, 2026; there is no claim of priority, experimental calibration, or exhaustive literature coverage. The parameter pp is fixed; latent contact and label randomness is refreshed every round. Persistent electrical charge is outside the Markov models studied here.

Introduction and historical context

From a physical shuffle to a random walk

The question “how many shuffles suffice?” is not well posed until the shuffle law, the notion of randomness, and the distance from a target law have been specified. A labelled deck has n!n! possible orders. A label-independent shuffling rule is a random walk on Sn\mathcal{S}_n, and uniform measure is stationary because each individual move is a permutation. Stationarity alone says neither that the walk reaches every order nor how quickly it forgets its initial state. Modern treatments organize these questions through mixing times, coupling, stopping times, entropy, and spectral analysis; see Aldous–Diaconis [2] and Levin–Peres [17]. Diaconis–Fulman [7] give a broad account of the mathematics of card shuffling.

Two benchmarks illustrate why the mechanism matters. The random-transposition walk chooses positions throughout the deck, while adjacent-transposition walks move cards locally. Diaconis–Shahshahani [11] established sharp mixing for random transpositions using representation theory. For local shuffling, Wilson [26] developed sharp-scale bounds and Lacoin [15] proved cutoff for the adjacent-transposition shuffle. The time conventions in these papers differ: one discrete adjacent update per round is not the same clock as independent rate-one updates at every edge. We will specify our clocks whenever comparing chains.

Riffle shuffling and cutoff

The classical Gilbert–Shannon–Reeds (GSR) model draws K∼Bin⁡(n,1/2)K \sim\operatorname{Bin}(n,1/2), cuts off the first KK cards, and then chooses uniformly among the (nK)\binom{n}{K} interleavings preserving both packet orders. Its equivalent binary-word description gives nn independent fair input bits. The historical model and equivalent constructions are discussed by Aldous–Diaconis [2], who trace the model to Gilbert and Shannon in 1955 and Reeds in 1981, and by Diaconis–Fulman [7]. Here “Reeds” refers to Jim Reeds, not to Reed–Solomon error-correcting codes. In the forward construction the next packet is selected by its remaining card count, not by a fixed fair coin.

Bayer–Diaconis [5] analyzed the distribution through rising sequences and established the sharp transition at 32log⁡2n\frac{3}{2}\log_2 n shuffles. The familiar slogan about seven shuffles is a finite-deck summary, not a statement that seven steps produce exact uniformity. The distinction between gradual convergence and an asymptotically abrupt transition is the cutoff phenomenon.

Card-shuffling problems helped make cutoff a central question in finite Markov-chain theory. The random-transposition analysis of Diaconis–Shahshahani [11] and the stopping-time approach of Aldous–Diaconis [2] supplied complementary algebraic and probabilistic methods. Diaconis’s survey [8] places shuffling alongside urn models and other walks, including examples with no cutoff. Polynomial mixing, a spectral gap, or a plausible entropy threshold alone does not establish a sharp transition.

Lalley [16] connected riffle permutations to symbolic and interval dynamical systems and related randomization to entropy. This viewpoint motivates studying geometric interleaving rules, but random point configurations in a geometric representation must not be confused with resetting packets to deterministic equally spaced grids. The two constructions need not have the same law.

Recent work of Sellke, Shi, and Wang [24] proves cutoff for broad classes of cut-size distributions. Their interleaving is still uniformly random conditional on the cut. Thus randomness of the cut alone is not the assumption that distinguishes their setting from ours: it is the conditional interleaving law. Their theorem does not supply an upper bound for the chain studied here.

Perfect shuffles, Thorp shuffling, and sparse randomness

A perfect shuffle interlaces equal packets in a prescribed alternating pattern. Such permutations have rich algebraic structure but do not, by themselves, constitute a mixing mechanism. Diaconis, Graham, and Kantor [9] study the groups generated by perfect shuffles. Thorp’s work on nonrandom shuffling and faro [25] is an early motivation for distinguishing realistic or structured shuffling from uniform random permutations.

In the Thorp shuffle, the deck is cut exactly in half, and each corresponding pair of cards is ordered by an independent fair coin. Conditional on an exactly balanced cut, our shuffle is precisely this operation. Morris’s first polynomial-in-log nn bound appeared in work originating at STOC 2005 and published in 2008 [18]. Morris [19] obtained O(log⁡4n)O(\log^4 n) for arbitrary even nn by an entropy method for shuffles built from random pair exchanges. For n=2dn = 2^d, Morris [20] subsequently obtained O(d3)O(d^3).

An October 3, 2026 preprint of Jiang [12] reports a full-deck upper bound of order d5/3d^{5/3} for the power-of-two Thorp shuffle. This recent preprint is included for bibliographic currency; its proof is not audited or used here. In particular, our argument does not depend on the best available Thorp mixing bound.

Comparison methods and the present contribution

Comparison of Dirichlet forms and spectra is a standard way to transfer mixing estimates between walks on groups; Diaconis–Saloff-Coste [10] provide a foundational treatment. Our application has a nonreversible complication: the proportional shuffle is not a reversible walk, so controlling only the eigenvalues of an additive symmetrization would not suffice. We instead control its one-step squared-norm deficit on invariant spectral subspaces.

A second ingredient comes from a different subject. The detectability lemma, introduced by Aharonov, Arad, Landau, and Vazirani [1], bounds products of local projections. We use the arbitrary-order version of Anshu, Arad, and Vidick [4] to compare parallel swap layers with the sum of their individual swap projections. The state space here is classical; only the Hilbert-space inequality is borrowed.

For unglued interpolation, the model-specific observations are an exact tie count and a two-cut geometric identity. The identity turns the balanced-cut matching and one conjugate matching into a Hamiltonian cycle. It permits a polynomial upper bound without waiting for a long uninterrupted run of balanced cuts. We also obtain an information-concentration lower bound, stronger than a fixed-error entropy inequality. The substantial gap between the two bounds is part of the conclusion, not a suppressed technical issue.

For the adhesive extensions, local alternatives supply fair-swap projections along a path. A separate comparison uses rotations and one-break insertions when adhesion is strong. The model atlas and bounds come first; the unglued proof develops the common spectral tools; § 8–§ 11 then give the parameter-dependent arguments. This organization distinguishes baseline results, uniform bounds, and genuinely sharp fixed-deck parameter exponents.

Physics motivates blocks, not an uncalibrated force law

Surface-charge correlations can contribute to adhesion between insulating surfaces [23]. Experiments on insulating polymers also link charge to friction [6], while the mechanics of interleaved paper exhibits strong geometry-dependent friction amplification [3]. These are motivations for allowing coherent groups of cards, not measurements of a playing-card shuffle. Sticking need not be electrical, and a net positive or negative charge per card does not describe all surface-charge effects. We do not insert a thermal Boltzmann factor into a macroscopic, hand-driven process.

Our coarse-graining keeps just one probability: pp is the chance that an existing neighboring contact survives the release attempt. Broken contacts permit, but do not force, separation in the output. Humidity, coating, pressure, and handling would affect an experimentally fitted pp; they are not extra mathematical parameters here. Independent contacts, equal card thickness, and complete refresh between shuffles are simplifying assumptions, not consequences of electrostatics. The cut-first models also impose the cut independently of adhesion. Persistent charge would require an enlarged state space and a new stationarity argument.

Clumpy shuffles and the cut-law distinction

Jonasson and Morris [13] prove O(log⁡4n)O(\log^4 n) mixing for a riffle driven by a stationary, symmetric two-state Markov word, with any fixed nondegenerate transition probability. Their paper cites earlier work by Wager on an extremely clumpy regime; we have not independently checked that thesis and make no novelty claim in this regime. Our correlated-label family below is exactly their model, up to inversion and parameterization. Our other three families keep a binomial cut and are different chains. In particular, their polylogarithmic theorem is not an upper bound for those cut-first families.

Contiguous random packets also appear in the overhand-shuffle literature. Pemantle [22] proved bounds between orders n2n^2 and n2log⁡nn^2 \log n; Jonasson [14] established the latter as the correct order for that model. Its packet-reversal mechanism is different from preserving two packets while interleaving their blocks. Palomares’s 2025 REU report [21] studies the Markovian rule under the name “geometric model,” with a neatness parameter and finite-deck spectral calculations. That use of “geometric” refers to run lengths, not our deterministic midpoint grids. Neither resemblance transfers a mixing theorem to the cut-first models.

A model atlas: one adhesion parameter, four rules

Throughout the extension let p∈[0,1]p \in[0,1] and q=1−pq = 1-p. These are not two parameters. Card identities never affect the rule. All random choices are fresh at each shuffle. The parameter pp is contact survival, not the probability that two successive output cards come from the same packet.

The common cut-first mechanism

The families CpC_p, BpB_p, IpI_p first draw K∼Bin⁡(n,1/2)K \sim\operatorname{Bin}(n,1/2) and form packets of KK and n−Kn-K cards. Empty cuts are the identity. At each internal packet gap independently, keep the bond with probability pp. The connected components are blocks; each block keeps its internal order. Conditional on 0<K<n0 < K < n,

B=2+Bin⁡(n−2,q),EB=2+(n−2)q.(1)B = 2 + \operatorname{Bin}(n-2,q), \qquad\mathbb{E}B = 2 + (n-2)q. \tag*{(1)}

Before boundary truncation, block lengths have law P(L=ℓ)=qpℓ−1\mathbb{P}(L=\ell)=qp^{\ell-1} and mean 1/q1/q for p<1p<1.

Definition 2.1 (Card-weighted release: CpC_p). With A,BA,B cards left in the packets, choose the next left block with probability A/(A+B)A/(A+B) and otherwise the next right block. Release the whole selected block and subtract its length from the packet count. Equivalently, after each individual card immediately update the counts. If both packets remain nonempty, test the next bond on the last-used side: with probability pp continue on that side, and with probability qq make a fresh card-weighted GSR choice. Thus, with At,BtA_t,B_t measured after tt drops and HtH_t the last side, the next-left probability is

p1{Ht=L}+qAtAt+Bt(AtBt>0).(2)p\mathbf{1}_{\{H_t=L\}}+q\frac{A_t}{A_t+B_t}\qquad(A_tB_t>0). \tag*{(2)}

An empty packet cannot supply another card; the first drop has no previous side and uses K/nK/n. A failed bond can still be followed by a fresh choice of the same side.

Definition 2.2 (Block-weighted release: BpB_p). With r,sr,s blocks remaining, choose the next left block with probability r/(r+s)r/(r+s). Conditional on the packet partitions, all order-preserving block interleavings are equally likely. Blocks of unequal lengths have equal selection weight. This is deliberately not card-weighted GSR. Nor is its cut binomial in the number of blocks: the initial cut was made in cards.

Definition 2.3 (Midpoint release: IpI_p). A block at packet positions a,…,ba,\ldots,b in a packet of mm cards has key (a+b−1)/(2m)(a+b-1)/(2m). Merge blocks in increasing key order. Independent fair coins resolve equal keys, and each block is emitted intact. The keys use card positions, not block ranks. This is a release schedule approximation, not an independently calibrated mechanical clock.

Diagram showing the shared cut and bond law for the three cut-first families

Figure 1. The three cut-first families share precisely the same cut and bond law. Only the block interleaver changes.

For example, consider packet blocks [1, 2, 3, 4] and [5], [6], [7], [8]. The first-left probability is 1/2 for CpC_p and 1/5 for BpB_p. The rule IpI_p instead gives 5, 6, 1, 2, 3, 4, 7, 8 deterministically. This example is conditional on a partition; it introduces no new parameter.

The correlated-label benchmark has a different cut

Definition 2.4 (Markov inverse riffle: MpM_p). On the uncut deck keep each neighboring bond independently with probability pp, give each resulting block an independent fair binary label, and stably place label 0 before label 1. Equivalently, start with a fair label and, at each next position, repeat the label with probability (1+p)/2(1+p)/2.

The label-switch indicators in this construction are independent Bernoulli(q/2q/2). In the corresponding forward shuffle the number of zeros is the cut size. Its variance is

Var⁡(K)=n4+12∑d=1n−1(n−d)pd(3)\operatorname{Var}(K)=\frac{n}{4}+\frac{1}{2}\sum_{d=1}^{n-1}(n-d)p^d \tag*{(3)}

because label correlations at distance dd equal pdp^d. Except at p=0p=0, this cut is not binomial. Reversing iid permutation increments preserves the distance to uniform, so forward and inverse versions have identical mixing times. This is the connection with [13].

FamilyWhat is randomized?At p=0p=0At p=1p=1
CpC_pCard-weighted block choicesGSRRotations only
BpB_pUniform block interleavingGSRRotations only
IpI_pBonds and midpoint tie coinsOriginal interpolationRotations only
MpM_pCorrelated binary labelsInverse GSRIdentity only

Table 1. All four families have at most one adjustable parameter. The infinitesimal continuous jitter considered later is an equivalent implementation of I0I_0, not a fifth tunable model.

Every family is a walk with iid, label-independent permutation increments, so uniform measure is stationary. The upper bounds below prove convergence for p<1p<1 on even decks, and for 0<p<10<p<1 on odd decks as well. At p=0p = 0, the GSR families mix on either parity; our upper arguments leave odd-deck interpolation untreated. At p=1p = 1, the rotation subgroup is proper when n≥3n \ge3, so stationarity does not imply convergence from a fixed deck.

Reading the bounds

Use total variation from a specified starting order, uniform target measure, and one complete shuffle per time unit. Write

Λn,ε=log⁡n+log⁡(1/ε),L(n,p)=1+log⁡+(nq)q,log⁡+x=max⁡{0,log⁡x}.\Lambda_{n,\varepsilon} = \log n + \log(1/\varepsilon), \qquad L(n,p) = \frac{1 + \log_{+}(nq)}{q}, \qquad\log_{+} x = \max\{0,\log x\}.

At p=1p = 1 mixing on Gn\mathcal{G}_n fails for n≥3n \ge3. The following table concerns p<1p < 1. Constants in OO and Ω\Omega are absolute unless a subscript says otherwise. Lower bounds concern ε=1/4\varepsilon= 1/4; upper bounds allow 0<ε≤1/20 < \varepsilon\le1/2. The polynomial cut-first upper bounds assume even n≥4n \ge4; the common rotation bound below also covers odd n≥4n \ge4 when 0<p<10 < p < 1.

The entropy quantity hˉn,p\bar{h}_{n,p} is explicit in (23). The Markov bound holds for all n≥4n \ge4; for fixed p<1p < 1 the stronger external bound Op(log⁡4n)O_p(\log^4 n) is available from [13].

Three refinements are important when interpreting Table 2. First, for all cut-first families and 0<p<10 < p < 1 we prove

FamilyLower bound established hereParameter-explicit polynomial upper bound
CpC_pΩ(L(n,p))\Omega(L(n,p))O(n7/2q−6Λn,ε)O(n^{7/2}q^{-6}\Lambda_{n,\varepsilon})
BpB_pΩ(L(n,p))\Omega(L(n,p))O(n3(1+npq)q−6Λn,ε)O(n^3(1+npq)q^{-6}\Lambda_{n,\varepsilon})
IpI_p, p>0p > 0Ω(max⁡{L(n,p),nlog⁡n/hˉn,p})\Omega(\max\{L(n,p),n\log n/\bar{h}_{n,p}\})O(n5/2Λn,εq4min⁡{p2,q2})O\left(\frac{n^{5/2}\Lambda_{n,\varepsilon}}{q^4\min\{p^2,q^2\}}\right)
I0I_0Ω(nlog⁡n)\Omega(\sqrt{n}\log n)O(n5/2Λn,ε)O(n^{5/2}\Lambda_{n,\varepsilon})
MpM_pΩ(max⁡{L(n,p),(nq2)−1})\Omega(\max\{L(n,p),(nq^2)^{-1}\})O(n2q−2Λn,ε)O(n^2q^{-2}\Lambda_{n,\varepsilon})

Table 2. Proved bounds, not proposed sharp scales.

tmix(ε)≤Cn3(npn−2+1qpn−3)Λn,ε.(4)t_{\mathrm{mix}}(\varepsilon) \le C n^3\left(\frac{n}{p^{n-2}}+\frac{1}{q p^{n-3}}\right)\Lambda_{n,\varepsilon}. \tag*{(4)}

This is particularly useful when nqnq is bounded, and must not be used as a fixed-pp polynomial bound. Second, interpolation also satisfies

tmixIp(ε)≤Cn5/2q−(n−2)Λn,εfor even n.(5)t_{\mathrm{mix}}^{I_p}(\varepsilon) \le C n^{5/2}q^{-(n-2)}\Lambda_{n,\varepsilon} \quad\text{for even } n. \tag*{(5)}

Take the minimum of all applicable upper bounds, not their sum. Third, at p=0p = 0 the classical GSR families have the much sharper 32log⁡2n+Oε(1)\frac{3}{2}\log_2 n + O_\varepsilon(1) bound and cutoff [5]. The constants in the table are deliberately conservative.

Theorem 2.5 (Sharp adhesion exponents at fixed deck size). Fix n≥4n \ge4 and 0<ε≤1/40 < \varepsilon\le1/4. As p↑1p \uparrow1,

tmixFp(ε)=Θn,ε((1−p)−1),F∈{C,B,I},t_{\mathrm{mix}}^{F_p}(\varepsilon) = \Theta_{n,\varepsilon}((1-p)^{-1}), \qquad F \in\{C,B,I\},
tmixMp(ε)=Θn,ε((1−p)−2).t_{\mathrm{mix}}^{M_p}(\varepsilon) = \Theta_{n,\varepsilon}((1-p)^{-2}).

The nn-dependent constants are not asserted to be sharp. These are fixed-nn parameter asymptotics, not a cutoff assertion.

The proof is given after the uniform upper and lower estimates. In the joint regime nq≤cnq \le c, (4) improves the cut-first upper bound to Oc(n3q−1Λn,ε)O_c(n^3q^{-1}\Lambda_{n,\varepsilon}) for sufficiently large nn. Its lower counterpart is Ω(q−1)\Omega(q^{-1}). For the Markov model the corresponding bounds are Ω((nq2)−1)\Omega((nq^2)^{-1}) and O(n2q−2Λn,ε)O(n^2q^{-2}\Lambda_{n,\varepsilon}). Large gaps in nn remain visible.

The unglued interpolation model and its bounds

Midpoint interpolation

Number the positions 1,…,n1,\ldots,n. Given a cut kk with 0<k<n0<k<n, write the two packets as A1,…,AkA_1,\ldots,A_k and B1,…,Bn−kB_1,\ldots,B_{n-k}, in their current orders. Assign coordinates

xi=i−1/2k,yj=j−1/2n−k.(6)x_i=\frac{i-1/2}{k}, \qquad y_j=\frac{j-1/2}{n-k}. \tag*{(6)}

Merge by increasing coordinate. Whenever xi=yjx_i=y_j, use an independent fair coin to decide whether AiA_i or BjB_j comes first. Cuts 00 and nn are the identity. Coordinates and random choices are reset at every round.

Definition 3.1. The binomial-cut proportional shuffle is the preceding merge with independent cuts K∼Bin⁡(n,1/2)K\sim\operatorname{Bin}(n,1/2) at successive rounds. The name is descriptive, not a claim that this is established terminology.

There are at most two cards at any coordinate, and distinct ties involve disjoint cards. The packet orders are always preserved. The midpoint convention matters: different endpoint or rounding conventions can yield different chains and different invariants.

Proposition 3.2 (Equivalence with infinitesimal jitter). Fix 0<ϵn<n−20<\epsilon_n<n^{-2}. Add independent Uniform⁡(−ϵn,ϵn)\operatorname{Uniform}(-\epsilon_n,\epsilon_n) perturbations to all coordinates in (6) before merging. The resulting shuffle has exactly the law of independent fair tie-breaking.

Proof. A nonzero difference of cross-packet coordinates is an integer multiple of 1/(2k(n−k))1/(2k(n-k)), hence has magnitude at least 2/n22/n^2. The difference between two perturbations is smaller than 2/n22/n^2, so no strict cross-packet comparison changes. Within a packet the spacing is at least 1/n1/n, which likewise cannot be reversed. At a tie, exchangeability of the two continuous perturbations gives either order with probability 1/21/2. Disjoint tied pairs use disjoint noises, giving independence.

Remark 3.3. Independent two-point noises ±ϵn\pm\epsilon_n leave a tie unresolved with probability 1/21/2. Stable left-first sorting would then favor the left card with probability 3/43/4. One can instead give each tied pair opposite signs, with one fair coin choosing the signs. That is again exactly our model. Noise large enough to change non-tied comparisons is a different model; none of the main results silently assumes such additional noise.

Distances and conventions

Let πn\pi_n be uniform measure on Sn\mathfrak{S}_n and let XtX_t start from the identity deck. Set

dn(t)=12∑σ∈Sn∣P(Xt=σ)−πn(σ)∣,tmix(n)(ε)=min⁡{t:dn(t)≤ε}.d_n(t)=\frac{1}{2}\sum_{\sigma\in\mathfrak{S}_n}\left|\mathbb{P}(X_t=\sigma)-\pi_n(\sigma)\right|,\qquad t_{\mathrm{mix}}^{(n)}(\varepsilon)=\min\{t:d_n(t)\le\varepsilon\}.

Every deterministic starting order has the same distance by translation. Entropies use base-two logarithms; unmarked log denotes the natural logarithm. The unglued interpolation results in the next five sections concern even n→∞n\to\infty; the extension states its size restrictions separately.

Theorem 3.4 (Main bounds). Let nn be even and let Tn(k)T_n(k) be the number of ties at cut kk. Define

hn=H(K)+ETn(K),an=log⁡2(n!)hn.h_n = \mathrm{H}(K) + \mathrm{E} T_n(K), \qquad a_n = \frac{\log_2(n!)}{h_n}.

Then:

  1. hn∼n/(2π)h_n \sim\sqrt{n/(2\pi)} and an∼2πnlog⁡2na_n \sim\sqrt{2\pi n}\log_2 n.

  2. For every fixed δ∈(0,1)\delta\in(0,1),

dn(⌊(1−δ)an⌋)⟶1.d_n(\lfloor(1-\delta)a_n\rfloor) \longrightarrow1.
  1. For n≥4n \ge4 and 0<ε≤1/20 < \varepsilon\le1/2, a universal constant CC satisfies

tmix(n)(ε)≤Cn5/2(log⁡n+log⁡(1/ε)).t_{\mathrm{mix}}^{(n)}(\varepsilon) \le C n^{5/2}\bigl(\log n+\log(1/\varepsilon)\bigr).

The constants in the upper bound are not optimized.

The third assertion follows from a more general statement. Write PkP_k for the specified fair-tie merge conditional on cut kk.

Theorem 3.5 (Two-cut criterion). Let n=2m≥4n=2m\ge4 and let P=∑k=0nqkPkP=\sum_{k=0}^{n}q_kP_k for an arbitrary cut law with β=min⁡(qm,qm+1)>0\beta=\min(q_m,q_{m+1})>0. Then

tmix(ε)≤Cn2β(log⁡n+log⁡(1/ε)),0<ε≤1/2.(7)t_{\mathrm{mix}}(\varepsilon)\le C\frac{n^2}{\beta}\bigl(\log n+\log(1/\varepsilon)\bigr), \qquad0<\varepsilon\le1/2. \tag*{(7)}

No assumption on the remaining cut probabilities is needed.

For the binomial law, qm=2−n(nm)≍n−1/2q_m=2^{-n}\binom{n}{m}\asymp n^{-1/2} and qm+1=qmm/(m+1)q_{m+1}=q_m m/(m+1), which gives Theorem 3.4(3). The case n=2n=2 is a two-state chain and is elementary.

The lower bound already confirms a qualitative difference from the benchmarks: this even-deck chain mixes asymptotically more slowly than both GSR riffle shuffling and the Thorp shuffle. Indeed, its Ω(nlog⁡n)\Omega(\sqrt{n}\log n) lower bound exceeds both the GSR logarithmic scale [5] and the general-even Thorp upper bound O(log⁡4n)O(\log^4 n) [19]. This comparison is asymptotic, not a numerical prediction for a 52-card deck.

Tie arithmetic and the entropy of one round

Lemma 4.1 (Exact tie count). For 0<k<n0<k<n, put g=gcd⁡(k,n−k)g=\gcd(k,n-k), a=k/ga=k/g, and b=(n−k)/gb=(n-k)/g. Then

Tn(k)={g,a and b are both odd,0,otherwise.(8)T_n(k)= \begin{cases} g, & a\text{ and }b\text{ are both odd},\\ 0, & \text{otherwise}. \end{cases} \tag*{(8)}

Also Tn(0)=Tn(n)=0T_n(0)=T_n(n)=0.

Proof. The tie equation is b(2i−1)=a(2j−1)b(2i-1)=a(2j-1). Since aa and bb are coprime, both must be odd for a solution. If they are odd, the solutions are 2i−1=aℓ2i-1=a\ell and 2j−1=bℓ2j-1=b\ell, with ℓ=1,3,…,2g−1\ell=1,3,\ldots,2g-1. There are exactly gg solutions.

For n=2mn = 2m, Tn(m)=mT_n(m) = m. A nonzero tie count requires g∣mg \mid m, so

Tn(k)≤gcd⁡(k,m),Tn(k)≤∣k−m∣(k≠m).(9)T_n(k) \le\gcd(k,m), \qquad T_n(k) \le|k-m| \quad(k \ne m). \tag*{(9)}

The latter follows because a positive gg divides both kk and mm. If nn is odd there are no ties at all. If n=2dn = 2^d, every interior cut has Tn(k)=2v2(k)T_n(k) = 2^{v_2(k)}.

Lemma 4.2 (The balanced cut dominates). For n=2mn = 2m and pn=P(K=m)p_n = \mathbb{P}(K = m),

0≤ETn(K)−mpn≤∑r∣mφ(r)r≤τ(m).(10)0 \le\mathbb{E}T_n(K) - mp_n \le\sum_{r\mid m}\frac{\varphi(r)}{r} \le\tau(m). \tag*{(10)}

where φ\varphi is Euler’s totient and τ\tau counts positive divisors. Consequently,

hn=mpn+O(log⁡n+τ(m))∼n2π.h_n = mp_n + O(\log n + \tau(m)) \sim\sqrt{\frac{n}{2\pi}}.

Proof. Write pj=P(K=m+j)p_j = \mathbb{P}(K = m + j). The positive-index sequence is decreasing and pj=p−jp_j = p_{-j}. For every divisor rr of mm, grouping rr consecutive positive indices gives

P(K≠m, r∣K)=2∑ℓ=1m/rpℓr≤2r∑j=1mpj≤1r.\mathbb{P}(K \ne m,\ r\mid K) = 2\sum_{\ell=1}^{m/r}p_{\ell r} \le\frac{2}{r}\sum_{j=1}^{m}p_j \le\frac{1}{r}.

Use (9) and gcd⁡(k,m)=∑r∣m, r∣kφ(r)\gcd(k,m) = \sum_{r\mid m,\ r\mid k}\varphi(r) to obtain (10). Also H(K)≤log⁡2(n+1)\mathrm{H}(K) \le\log_2(n+1). The elementary divisor bound τ(m)=mo(1)\tau(m) = m^{o(1)}, or just τ(m)=O(m1/4)\tau(m) = O(m^{1/4}), makes the error o(n)o(\sqrt{n}). For completeness, the latter estimate follows by writing m=∏ppapm = \prod_p p^{a_p}: for p≥16p \ge16, ap+1≤2ap≤pap/4a_p + 1 \le2^{a_p} \le p^{a_p/4}, while the finitely many smaller primes contribute a bounded factor to ∏(ap+1)/pap/4\prod(a_p+1)/p^{a_p/4}. Finally Stirling’s formula gives pn=2−2m(2mm)∼(πm)−1/2p_n = 2^{-2m}\binom{2m}{m} \sim(\pi m)^{-1/2}. □

Remark 4.3 (Input entropy is not automatically deck entropy). The effective seed for one step consists of the cut and the tie coins. Its entropy is exactly hnh_n. Different seeds may produce the same permutation, so the entropy of the one-step permutation is only bounded above by hnh_n. After tt rounds the deck entropy is at most thnth_n. There is no assertion that all input information is retained efficiently.

The exactly balanced cut occurs with probability of order n−1/2n^{-1/2} and uses n/2n/2 coins. These relatively rare, high-entropy rounds dominate the leading entropy budget. Thus it would be incorrect to count only n+1n+1 possible moves per round, as one could for deterministic tie rules.

A strong information lower bound

An entropy inequality alone gives a fixed-error lower bound. Concentration of the information of the entire input history gives distance tending to one, which is the stronger conclusion needed for the lower side of a possible cutoff.

Lemma 5.1 (Information moments). Let qk=P(K=k)q_k = \mathbb{P}(K = k) and define

Zn=−log⁡2qK+Tn(K).Z_n = -\log_2 q_K + T_n(K).

Then EZn=hn\mathbb{E}Z_n = h_n and Var⁡(Zn)=O(n3/2)\operatorname{Var}(Z_n) = O(n^{3/2}) for even nn.

Proof. Conditional on K=kK = k, each tie-coin string has probability 2−Tn(k)2^{-T_n(k)}, which proves the mean assertion. For a variable on MM possible values, its surprisal A=−log⁡2P(K)A = -\log_2 \mathbb{P}(K) satisfies P(A≥u)≤M2−u\mathbb{P}(A \ge u) \le M2^{-u}. Integrating this tail with M=n+1M = n + 1 gives EA2=O(log⁡2n)\mathbb{E}A^2 = O(\log^2 n). By (9),

ETn(K)2≤m2pn+E(K−m)2=m2pn+n/4=O(n3/2).\mathbb{E}T_n(K)^2 \le m^2p_n + \mathbb{E}(K-m)^2 = m^2p_n + n/4 = O(n^{3/2}).

Now use (A+T)2≤2A2+2T2(A+T)^2 \le2A^2 + 2T^2.

Proof of Theorem 3.4(1)–(2). Part (1) follows from Lemma 4.2 and Stirling’s formula for n!n!. Put Ln=log⁡2(n!)L_n = \log_2(n!) and t=⌊(1−δ)Ln/hn⌋t = \lfloor(1-\delta)L_n/h_n\rfloor. The information of a full history of cuts and tie coins is

It=∑s=1tZn,s,I_t = \sum_{s=1}^{t} Z_{n,s},

a sum of independent copies. Hence

EIt≤(1−δ)Ln,Var⁡(It)=O(n2log⁡n).\mathbb{E}I_t \le(1-\delta)L_n,\qquad\operatorname{Var}(I_t) = O(n^2\log n).

Chebyshev’s inequality implies

P(It≤(1−δ/2)Ln)≥1−O((δ2log⁡n)−1).\mathbb{P}\left(I_t \le(1-\delta/2)L_n\right) \ge1-O\left((\delta^2\log n)^{-1}\right).

Every history in this event has probability at least 2−(1−δ/2)Ln2^{-(1-\delta/2)L_n}, so there are at most 2(1−δ/2)Ln2^{(1-\delta/2)L_n} such histories. Their resulting decks form a set FnF_n with the same cardinality bound. Therefore

P(Xt∈Fn)→1,πn(Fn)≤(n!)−δ/2→0,\mathbb{P}(X_t \in F_n)\to1,\qquad\pi_n(F_n)\le(n!)^{-\delta/2}\to0,

and total variation tends to one.

Proposition 5.2 (A finite-deck entropy bound). If dn(t)≤ε≤1/2d_n(t)\le\varepsilon\le1/2, then

t≥(1−ε)log⁡2(n!)−H2(ε)hn.t\ge\frac{(1-\varepsilon)\log_2(n!)-H_2(\varepsilon)}{h_n}.

where H2(u)=−ulog⁡2u−(1−u)log⁡2(1−u)H_2(u)=-u\log_2u-(1-u)\log_2(1-u).

Proof. Couple XtX_t to a uniform permutation with disagreement probability dn(t)d_n(t). Conditioning on the disagreement indicator bounds the missing entropy by H2(ε)+εlog⁡2(n!)H_2(\varepsilon)+\varepsilon\log_2(n!). Combine this with H(Xt)≤thnH(X_t)\le th_n.

Two cuts produce a cycle of random-swap locations

Let n=2m≥4n=2m\ge4. A permutation dkd_k will mean the output list of the midpoint merge at cut kk, with all ties resolved left before right. Thus dkd_k maps an output position to its input position. Permutations compose as functions: (uv)(i)=u(v(i))(uv)(i)=u(v(i)).

Let MM be the balanced input matching

M={{i,m+i}:1≤i≤m}.M=\{\{i,m+i\}:1\le i\le m\}.

Write HMH_M for the group generated by these disjoint transpositions, put b=dmb=d_m, c=dm+1c=d_{m+1}, and set R=cb−1R=cb^{-1}.

Lemma 6.1 (Two-cut geometry). The following hold.

  1. The conditional permutation at cut mm is hbhb, with hh uniform on HMH_M.

  1. At cut m+1m+1 there is either no tie or one tie, and any tie is an edge of MM.

  1. MM and M′=RMR−1M' = RMR^{-1} are disjoint perfect matchings whose union is a Hamiltonian cycle on the nn input positions.

Proof. The first assertion is the definition of the balanced merge. At cut m+1m+1, the packet sizes are m+1m+1 and m−1m-1. If mm is odd, Lemma 4.1 gives no tie. If mm is even, there is exactly one, between input positions m/2+1m/2+1 and 3m/2+13m/2+1, an edge of MM.

For the last assertion, b−1Mbb^{-1}Mb pairs consecutive output positions. Thus M′M' consists of consecutive pairs in the list cc. Set r=⌊(m−1)/2⌋r=\lfloor(m-1)/2\rfloor. Direct comparison of midpoint coordinates shows that those pairs are

{j,m+1+j},1≤j≤r,{r+1,r+2},{m+1+j,j+2},r+1≤j≤m−1.\begin{aligned} &\{j,m+1+j\}, &&1\le j\le r,\\ &\{r+1,r+2\},\\ &\{m+1+j,j+2\}, &&r+1\le j\le m-1. \end{aligned}

One way to check the list is to note that BjB_j lies between AjA_j and Aj+1A_{j+1} when 2j<m2j<m, and between Aj+1A_{j+1} and Aj+2A_{j+2} when 2j>m2j>m. At equality the prescribed left-first convention places Aj+1A_{j+1} first.

Contract each edge {i,m+i}\{i,m+i\} of MM to vertex ii. The displayed pairs become exactly {1,2},{2,3},…,{m−1,m},{m,1}\{1,2\},\{2,3\},\ldots,\{m-1,m\},\{m,1\}. For m=2m=2 this is the two-edge cycle as a multigraph. Hence the original union of the two matchings is connected and two-regular, and is therefore one cycle of length nn. □

Alternating cycle of random-swap locations for n=8

Figure 2. For n=8n=8, the balanced cut 4 and adjacent cut 5 produce the alternating cycle 1, 5, 8, 4, 7, 3, 2, 6, 1. This is a geometric identity between matchings, not an assumption that balanced cuts occur consecutively.

This also proves irreducibility for any cut law charging mm and m+1m+1: the group generated by the support contains HMH_M, bb, and cc, hence RR and all transpositions in M∪M′M\cup M'. Transpositions along a connected graph generate Sn\mathfrak{S}_n. For the binomial chain, the identity has positive probability, so aperiodicity follows immediately. The quantitative argument below also handles the two-cut law without an explicit identity atom.

A polynomial upper bound

Operators and the nonreversible deficit

Work in ℓ2(πn)\ell^2(\pi_n) and let Ugf(σ)=f(σg)U_gf(\sigma)=f(\sigma g). Then UgUh=UghU_gU_h=U_{gh} and UgU_g is unitary. For a matching NN, define its averaging projection

CN=∏e∈NI+Uτe2.C_N=\prod_{e\in N}\frac{I+U_{\tau_e}}{2}.

The factors commute; CNC_N is the orthogonal projection onto invariance under independently swapping the matched pairs.

Let PP be the transition operator in Theorem 3.5 and Q=P∗Q=P^* its adjoint. Put A=CMA=C_M and B=CM′=URAUR−1B=C_{M'}=U_RAU_R^{-1}. Conditional on the two distinguished cuts,

Q0=Ub−1A,Q1=Uc−1E,Q_0=U_{b-1}A,\qquad Q_1=U_{c-1}E,

where E=IE=I or E=(I+Uτ)/2E=(I+U_\tau)/2 for a transposition τ∈M\tau\in M. In particular EA=AEA=A, and ∥(I−E)f∥2≤∥(I−A)f∥2\lVert(I-E)f\rVert_2\le\lVert(I-A)f\rVert_2.

Define the nonnegative norm deficit

D(f)=∥f∥22−∥Qf∥22.D(f)=\lVert f\rVert_2^2-\lVert Qf\rVert_2^2.

For any mixture Q=∑kqkQkQ=\sum_k q_kQ_k of contractions, the variance identity gives

D(f)=∑kqk(∥f∥22−∥Qkf∥22)+∑kqk∥Qkf−Qf∥22.(11)D(f)=\sum_k q_k\left(\lVert f\rVert_2^2-\lVert Q_kf\rVert_2^2\right)+\sum_k q_k\lVert Q_kf-Qf\rVert_2^2. \tag*{(11)}

Lemma 7.1 (Control of two parallel layers). With S=(A+B)/2S=(A+B)/2 and β=min⁡(qm,qm+1)\beta=\min(q_m,q_{m+1}),

⟨f,(I−S)f⟩≤16βD(f).(12)\langle f,(I-S)f\rangle\le\frac{16}{\beta}D(f). \tag*{(12)}

Proof. Put a=∥(I−A)f∥2a=\lVert(I-A)f\rVert_2 and c0=∥Q0f−Q1f∥2c_0=\lVert Q_0f-Q_1f\rVert_2. Equation (11) implies

a2≤D(f)/β,c02≤2D(f)/β.a^2\le D(f)/\beta,\qquad c_0^2\le2D(f)/\beta.

For the second inequality, retain the two distinguished terms of the weighted variance and minimize their common center; their coefficient is qmqm+1/(qm+qm+1)≥β/2q_mq_{m+1}/(q_m+q_{m+1})\ge\beta/2.

Multiplication by UcU_c shows c0=∥URAf−Ef∥2c_0=\lVert U_RAf-Ef\rVert_2. Consequently

∥(UR−I)f∥2≤c0+2a,∥(UR−I)f∥22≤12D(f)/β.\lVert(U_R-I)f\rVert_2\le c_0+2a,\qquad\lVert(U_R-I)f\rVert_2^2\le12D(f)/\beta.

Since B=URAUR−1B=U_RAU_R^{-1},

∥(I−B)f∥2=∥(I−A)UR−1f∥2≤a+∥(UR−1−I)f∥2.\lVert(I-B)f\rVert_2=\lVert(I-A)U_R^{-1}f\rVert_2\le a+\lVert(U_R^{-1}-I)f\rVert_2.

Its square is at most 26D(f)/β26D(f)/\beta. Averaging this with the bound for a2a^2 gives (12) (in fact 27/227/2 suffices).

From a cycle to the central transposition generator

For any transposition edge ee, let Fe=(I−Uτe)/2F_e=(I-U_{\tau_e})/2, an orthogonal projection. The cycle Hamiltonian is

H=∑e∈M∪M′Fe.\mathcal{H}=\sum_{e\in M\cup M'}F_e.

The terminology “Hamiltonian” here means only a sum of positive self-adjoint operators. Define the central random-transposition generator

LRT=1(n2)∑1≤i<j≤n(I−U(ij)).(13)L_{\mathrm{RT}}=\frac{1}{\binom{n}{2}}\sum_{1\le i<j\le n}(I-U_{(ij)}). \tag*{(13)}

It generates a continuous-time walk making one uniformly chosen transposition per unit time on average. The continuous clock avoids the parity periodicity of a discrete walk that always transposes.

Lemma 7.2 (Path comparison). As quadratic forms,

LRT⪯8nH.(14)L_{\mathrm{RT}} \preceq8n\mathcal{H}. \tag*{(14)}

Proof. Delete one cycle edge to obtain a path. A transposition of vertices at path distance ℓ\ell is a word of length 2ℓ−12\ell-1 in adjacent transpositions, each path edge used at most twice. Telescoping and Cauchy–Schwarz give

∥(I−U(ij))f∥22≤4n∑e∈path⁡(i,j)∥(I−Uτe)f∥22.\left\lVert(I-U_{(ij)})f\right\rVert_{2}^{2}\le4n\sum_{e\in\operatorname{path}(i,j)}\left\lVert(I-U_{\tau_e})f\right\rVert_{2}^{2}.

Each fixed edge lies in at most n2/4n^{2}/4 such paths. Average over the (n2)\binom{n}{2} pairs, using ⟨f,LRTf⟩=(2(n2))−1∑i<j∥(I−U(ij))f∥22\langle f,L_{\mathrm{RT}}f\rangle=(2\binom{n}{2})^{-1}\sum_{i<j}\left\lVert(I-U_{(ij)})f\right\rVert_{2}^{2} and ⟨f,Fef⟩=∥(I−Uτe)f∥22/4\langle f,F_ef\rangle=\left\lVert(I-U_{\tau_e})f\right\rVert_{2}^{2}/4. The resulting coefficient is at most 8n8n. This is an elementary instance of the path comparison method [10].

The next input prevents losing a further factor of nn when replacing the individual edge projections by simultaneous matching updates.

Lemma 7.3 (Projection-product input). Suppose orthogonal projections FeF_e each fail to commute with at most two others. Let DD be the product of their complements, each applied once in any order; this includes any grouping into commuting layers. On a common invariant subspace VV where ∑eFe⪰γI\sum_e F_e\succeq\gamma I, one has

∥D∣V∥22≤(1+γ/4)−1.\left\lVert D|_V\right\rVert_{2}^{2}\le(1+\gamma/4)^{-1}.

This is the detectability-lemma estimate of Anshu–Arad–Vidick [4 Lemma 2], applied with noncommutation degree two. More precisely, their energy form of the lemma applies on the invariant subspace even if the restricted sum has no zero eigenvalue. No tensor-product assumption on VV is needed. In our cycle, disjoint transpositions commute and each edge has just two neighboring edges, so the hypothesis holds.

Lemma 7.4 (Central spectral comparison). For every f∈ℓ2(πn)f\in\ell^{2}(\pi_n),

∥f∥22−∥Qf∥22≥β16384n⟨f,LRTf⟩.(15)\left\lVert f\right\rVert_{2}^{2}-\left\lVert Qf\right\rVert_{2}^{2}\ge\frac{\beta}{16384n}\langle f,L_{\mathrm{RT}}f\rangle. \tag*{(15)}

Moreover the same inequality holds on every eigenspace of LRTL_{\mathrm{RT}}, and these eigenspaces are invariant under QQ.

Proof. The sum of all transpositions is central in the group algebra. Thus every UgU_g, and hence every operator under consideration, preserves each eigenspace VλV_\lambda of LRTL_{\mathrm{RT}}, whose eigenvalues lie in [0,2][0,2]. By Lemma 7.2, H∣Vλ⪰λ/(8n)I\mathcal{H}|_{V_\lambda}\succeq\lambda/(8n)I. Lemma 7.3 implies

∥BAf∥22≤∥f∥221+λ/(32n),f∈Vλ.\left\lVert BAf\right\rVert_{2}^{2}\le\frac{\left\lVert f\right\rVert_{2}^{2}}{1+\lambda/(32n)},\qquad f\in V_\lambda.

In particular, ∥f∥22−∥BAf∥22≥λ∥f∥22/(64n)\left\lVert f\right\rVert_{2}^{2}-\left\lVert BAf\right\rVert_{2}^{2}\ge\lambda\left\lVert f\right\rVert_{2}^{2}/(64n). On the other hand, writing a=∥(I−A)f∥2a=\left\lVert(I-A)f\right\rVert_{2} and b0=∥(I−B)f∥2b_0=\left\lVert(I-B)f\right\rVert_{2},

∥f∥22−∥BAf∥22=a2+∥(I−B)Af∥22≤3a2+2b02≤6⟨f,(I−S)f⟩.\left\lVert f\right\rVert_{2}^{2}-\left\lVert BAf\right\rVert_{2}^{2} =a^{2}+\left\lVert(I-B)Af\right\rVert_{2}^{2} \le3a^{2}+2b_{0}^{2}\le6\langle f,(I-S)f\rangle.

Therefore ⟨f,(I−S)f⟩≥λ∥f∥22/(384n)\langle f,(I-S)f\rangle\ge\lambda\left\lVert f\right\rVert_{2}^{2}/(384n). Combining with Lemma 7.1 gives D(f)≥βλ∥f∥22/(6144n)D(f)\ge\beta\lambda\left\lVert f\right\rVert_{2}^{2}/(6144n); the stated constant is weaker. Orthogonal decomposition into the VλV_\lambda gives the result for arbitrary ff.

Why the full spectrum gives the improved bound

Using only a spectral gap and the smallest stationary mass would lose an unnecessary factor comparable to nn. Instead we retain all central spectral subspaces.

Lemma 7.5 (Random-transposition input). For the continuous-time chain generated by (13), let χRT2(s)\chi_{\mathrm{RT}}^{2}(s) be the squared L2(πn)L^{2}(\pi_n) distance of its density from 11, starting at the identity. There is a universal constant C0C_0 such that

χRT2(s)≤4ε2ifs≥C0n(log⁡n+log⁡(1/ε)),0<ε≤1/2.\chi_{\mathrm{RT}}^{2}(s) \le4\varepsilon^{2}\quad\text{if}\quad s \ge C_0 n(\log n+\log(1/\varepsilon)),\qquad0<\varepsilon\le1/2.

Proof. We give a nonsharp spectral-sum bound to make the required estimate explicit. The classical representation-theoretic formulas for random transpositions [11] index the spectrum by partitions ρ\rho of nn. If dρd_\rho is the irreducible dimension and ρ′\rho' the conjugate partition, the eigenvalue of the transposition averaging operator is

rρ=∑i(ρi2)−∑i(ρi′2)(n2),r_\rho=\frac{\sum_i\binom{\rho_i}{2}-\sum_i\binom{\rho'_i}{2}}{\binom{n}{2}},

with multiplicity dρ2d_\rho^2. Consequently

χRT2(s)=∑ρ≠(n)dρ2e−2s(1−rρ).\chi_{\mathrm{RT}}^{2}(s)=\sum_{\rho\ne(n)}d_\rho^2e^{-2s(1-r_\rho)}.

Put j=n−ρ1j=n-\rho_1. Since all row lengths are at most n−jn-j,

∑i(ρi2)≤n(n−j−1)2,1−rρ≥jn−1.\sum_i\binom{\rho_i}{2}\le\frac{n(n-j-1)}{2},\qquad1-r_\rho\ge\frac{j}{n-1}.

Deleting the first row leaves a partition μ\mu of jj. A standard tableau of shape ρ\rho is determined by the jj entries below its first row and a standard tableau of shape μ\mu; column constraints can only reduce the count. Thus dρ≤(nj)dμd_\rho\le\binom{n}{j}d_\mu and, using ∑μ⊢jdμ2=j!\sum_{\mu\vdash j}d_\mu^2=j!,

∑ρ:n−ρ1=jdρ2≤(nj)2j!≤n2jj!.\sum_{\rho:n-\rho_1=j}d_\rho^2\le\binom{n}{j}^{2}j!\le\frac{n^{2j}}{j!}.

It follows that

χRT2(s)≤exp⁡(n2e−2s/(n−1))−1.(16)\chi_{\mathrm{RT}}^{2}(s)\le\exp\left(n^2e^{-2s/(n-1)}\right)-1. \tag*{(16)}

For s≥(n−1)(log⁡n+log⁡(1/ε))s\ge(n-1)(\log n+\log(1/\varepsilon)), the right side is at most eε2−1≤4ε2e^{\varepsilon^2}-1\le4\varepsilon^2 when 0<ε≤1/20<\varepsilon\le1/2. In particular C0=1C_0=1 suffices. □

The preceding estimate uses the full spectral sum, not merely its smallest positive eigenvalue. It is weaker than the sharp classical random-transposition analysis, but suffices for our comparison.

Proof of Theorem 3.5. Set α=β/(16384n)\alpha=\beta/(16384n). By Lemma 7.4,

∥Q∣Vλ∥22≤1−αλ.\lVert Q|_{V_\lambda}\rVert_2^2\le1-\alpha\lambda.

Let f0=n!1{id}f_0 = n!1_{\{\mathrm{id}\}} be the density of the initial point mass. The squared norm of its projection onto VλV_\lambda is dim⁡(Vλ)\dim(V_\lambda). Indeed, the spectral projector commutes with all translations, so its diagonal is constant and its trace is its rank. The density after tt steps is Qtf0Q^t f_0. Consequently,

∥Qtf0−1∥22≤∑λ>0dim⁡(Vλ)(1−αλ)t≤∑λ>0dim⁡(Vλ)e−αλt=χRT2(αt/2).\left\|Q^t f_0-1\right\|_2^2 \leq\sum_{\lambda>0}\dim(V_\lambda)(1-\alpha_\lambda)^t \leq\sum_{\lambda>0}\dim(V_\lambda)e^{-\alpha_\lambda t}=\chi^2_{\mathrm{RT}}(\alpha t/2).

Use dn(t)≤12∥Qtf0−1∥2d_n(t)\leq\frac{1}{2}\left\|Q^t f_0-1\right\|_2 and Lemma 7.5. More explicitly, the estimates give

tmix(ε)≤⌈32768n(n−1)β(log⁡n+log⁡(1/ε))⌉(17)t_{\mathrm{mix}}(\varepsilon)\leq\left\lceil\frac{32768n(n-1)}{\beta}\left(\log n+\log(1/\varepsilon)\right)\right\rceil \tag*{(17)}

which proves (7). This argument establishes convergence even without separately imposing aperiodicity on the two-cut law.

Remark 7.6 (What is and is not compared). The proof does not assert that interspersing arbitrary moves can only accelerate Thorp shuffling, nor does it thin the trajectory to balanced cuts. Both would require additional justification. It compares the actual one-step contraction of the full chain, including all intervening moves, to a central operator. The use of Q=P∗Q=P^*, rather than an unjustified reversible replacement for PP, is essential.

Lower bounds for the adhesive families

A universal information floor

Each cut-first increment is an ordinary order-preserving two-packet interleaving, irrespective of its probability. There are at most 2n2^n such increments, counted by their binary output words. The same support bound holds for their inverses, including MpM_p. Consequently,

dn(t)≥1−2ntn!,tmix(ε)≥log⁡2(n!)+log⁡2(1−ε)n.(18)d_n(t)\geq1-\frac{2^{nt}}{n!},\qquad t_{\mathrm{mix}}(\varepsilon)\geq\frac{\log_2(n!)+\log_2(1-\varepsilon)}{n}. \tag*{(18)}

This gives Ω(log⁡n)\Omega(\log n) without identifying seed entropy with the entropy of the output permutation.

Circular adjacency is the correct observable

Let J(σ)J(\sigma) count original directed circular neighbors (1,2),(2,3),…,(n,1)(1,2),(2,3),\ldots,(n,1) that remain neighbors in σ\sigma, including the bottom-to-top edge. Then J(id)=nJ(\mathrm{id})=n and

EπnJ=nn−1.(19)\mathbb{E}_{\pi_n}J=\frac{n}{n-1}. \tag*{(19)}

Circular rather than linear adjacency matters: a rotation leaves JJ unchanged.

Proposition 8.1 (Finite adhesion lower bounds). Put rn=1−21−nr_n=1-2^{1-n}. For any cut-first family and n≥4n\geq4,

dn(t)≥1−1n−1−3trn(n−2)qn.(20)d_n(t)\geq1-\frac{1}{n-1}-\frac{3tr_n(n-2)q}{n}. \tag*{(20)}

For MpM_p one has

dn(t)≥1−1n−1−3t(n−1)(n−2)q28n.(21)d_n(t)\geq1-\frac{1}{n-1}-\frac{3t(n-1)(n-2)q^2}{8n}. \tag*{(21)}

In addition, for all four families, every integer ℓ≥1\ell\ge1 satisfies

dn(t)≥P{Bin⁡(n,pt)≥2t+ℓ}−n(n−1)ℓ.(22)d_n(t) \ge\mathbb{P}\{\operatorname{Bin}(n,p^t) \ge2t+\ell\} - \frac{n}{(n-1)\ell}. \tag*{(22)}

Proof. For a nonempty cut, let RR be the number of broken internal bonds. It has law Bin⁡(n−2,q)\operatorname{Bin}(n-2,q). If R=0R=0, the shuffle is a rotation. Otherwise at most R+2≤3RR+2 \le3R circular edges can be destroyed: all block interiors survive, and only block boundaries are candidates. This bounds the loss of original edges as well, even if some are later recreated. Summing expected losses gives EJ(Xt)≥n−3trn(n−2)q\mathbb{E}J(X_t) \ge n-3t r_n(n-2)q. Apply the variational definition of total variation to the function J/n∈[0,1]J/n \in[0,1] and use (19).

For MpM_p, use the number RR of switches of the Markov label word, not the number of hidden adhesive blocks. Here R∼Bin⁡(n−1,q/2)R \sim\operatorname{Bin}(n-1,q/2). With zero or one switch the increment is a rotation or the identity. Otherwise at most R+1R+1 edges change, and (R+1)1{R≥2}≤32R(R−1)(R+1)\mathbf{1}_{\{R\ge2\}} \le\frac{3}{2}R(R-1). This proves (21). The coarser estimate E[J(Xt)]≥n−3tnq\mathbb{E}[J(X_t)] \ge n-3tnq is also valid for all four families, by counting broken adhesive bonds.

For the last assertion, preassign independent Bernoulli(p)(p) coins to each original directed edge in each round, even after that edge is lost. Whenever the edge is currently an internal packet contact, use its assigned coin for that bond. This preserves the model’s independent bond law. There are at most two exempt circular boundaries per round in a cut-first model and at most one in the inverse model. An original edge whose tt coins all survive cannot disappear unless it encounters an exempt boundary. At most 2t2t distinct original edges can encounter such a boundary before being lost. Therefore, on this enlarged space,

J(Xt)≥Zt−2t,Zt∼Bin⁡(n,pt).J(X_t) \ge Z_t-2t,\qquad Z_t \sim\operatorname{Bin}(n,p^t).

No independence between ZtZ_t and the chosen boundaries is needed. Under uniform measure, Markov’s inequality and (19) give πn(J≥ℓ)≤n/((n−1)ℓ)\pi_n(J\ge\ell) \le n/((n-1)\ell), proving the claim.

Corollary 8.2 (Uniform order lower bounds). As n→∞n \to\infty, uniformly over 0≤p<10 \le p < 1, all four families satisfy tmix(1/4)=Ω(L(n,p))t_{\mathrm{mix}}(1/4)=\Omega(L(n,p)). The inverse Markov family also satisfies tmix(1/4)=Ω((nq2)−1)t_{\mathrm{mix}}(1/4)=\Omega((nq^2)^{-1}).

Proof. When p≤1/2p \le1/2, L(n,p)=O(log⁡n)L(n,p)=O(\log n), so use (18). Suppose p>1/2p>1/2 and write x=nqx=nq. If xx is bounded, the coarse expected-loss bound in the preceding proof gives Ω(q−1)\Omega(q^{-1}), as needed. For x≥2x\ge2, take t=⌊log⁡x/(32q)⌋t=\lfloor\log x/(32q)\rfloor. Since −log⁡p≤2q-\log p \le2q, μ=EZt≥nx−1/16\mu=\mathbb{E}Z_t \ge nx^{-1/16}, and uniformly for x≥2x\ge2,

2tμ≤log⁡x16x15/16<14.\frac{2t}{\mu} \le\frac{\log x}{16x^{15/16}} < \frac{1}{4}.

Also μ≥n15/16→∞\mu\ge n^{15/16} \to\infty. Binomial concentration, with ℓ=⌊μ/2⌋\ell=\lfloor\mu/2\rfloor, makes the right side of (22) tend to one. Values of xx in a fixed bounded interval are already covered by the expected-loss bound. Combining the bounds proves the uniform order assertion. The additional Markov bound follows directly from (21).

Interpolation retains a stronger small-adhesion obstruction

Let Tn,pT_{n,p} be the number of block-key ties in one IpI_p round, and define sn=rn(n−2)s_n=r_n(n-2). A complete effective seed consists of the cut, the bond coins actually used, and the fair block-tie coins. Its entropy is

hn,p=H(K)+snH2(p)+ETn,p.h_{n,p}=\mathrm{H}(K)+s_n\mathrm{H}_2(p)+\mathbb{E}T_{n,p}.

Here and below 0log⁡0=00\log0=0. A useful explicit upper bound is

hˉn,p=H(K)+snH2(p)+min⁡{ETn(K)+snp, rn+snq2}.(23)\bar{h}_{n,p}=\mathrm{H}(K)+s_n\mathrm{H}_2(p)+\min\left\{\mathbb{E}T_n(K)+s_np,\ r_n+\frac{s_nq}{2}\right\}. \tag*{(23)}

The quantities Tn(k)T_n(k) and H(K)\mathrm{H}(K) are the finite binomial sums already given for the unglued model.

Proposition 8.3 (Parameter-dependent information bound). One has hn,p≤hˉn,ph_{n,p}\leq\bar{h}_{n,p}. For 0<ε≤1/20<\varepsilon\leq1/2,

tmixp(ε)≥(1−ε)log⁡2(n!)−H2(ε)hˉn,p.(24)t_{\mathrm{mix}}^{p}(\varepsilon)\geq\frac{(1-\varepsilon)\log_2(n!)-\mathrm{H}_2(\varepsilon)}{\bar{h}_{n,p}}. \tag*{(24)}

For every sequence p=pn∈[0,1]p=p_n\in[0,1] and fixed δ∈(0,1)\delta\in(0,1),

dn(⌊(1−δ)log⁡2(n!)hˉn,pn⌋)⟶1.(25)d_n\left(\left\lfloor(1-\delta)\frac{\log_2(n!)}{\bar{h}_{n,p_n}}\right\rfloor\right)\longrightarrow1. \tag*{(25)}

For even nn, if pn=o((nlog⁡n)−1)p_n=o((\sqrt{n}\log n)^{-1}), the original leading lower scale 2πnlog⁡2n\sqrt{2\pi n}\log_2 n is therefore unchanged.

Proof. A tie involving two singleton blocks was already an unglued tie. Every other tie uses a nonsingleton block, and there are at most as many such blocks as surviving bonds. Also Tn,p≤B/2T_{n,p}\leq B/2. Taking expectations proves (23). The entropy argument of Proposition 5.2 then proves (24).

For completeness, the information-concentration argument remains uniform in pp, even when pp tends to an endpoint. Write the one-round surprisal as Z=ZK+Zbonds+Tn,pZ=Z_K+Z_{\mathrm{bonds}}+T_{n,p}. The cut term has variance O(n)O(n) by Lemma 5.1. A single Bernoulli surprisal has variance pqlog⁡22(p/q)pq\log_2^2(p/q), uniformly bounded for 0≤p≤10\leq p\leq1. Conditional on a nonempty cut there are exactly n−2n-2 such variables. Empty cuts add at most O(n22−n)O(n^2 2^{-n}) to the variance. Finally Var⁡(Tn,p)≤(n/2)ETn,p\operatorname{Var}(T_{n,p})\leq(n/2)\mathbb{E}T_{n,p}. The inequality for the variance of a sum yields

Var⁡(Z)≤Cn(1+ETn,p)≤Cnhn,p.\operatorname{Var}(Z)\leq Cn(1+\mathbb{E}T_{n,p})\leq Cn h_{n,p}.

For tt as in (25), the total seed surprisal has mean at most (1−δ)log⁡2(n!)(1-\delta)\log_2(n!) and variance at most Cnlog⁡2(n!)Cn\log_2(n!). Chebyshev’s inequality makes its upper deviation by δlog⁡2(n!)/2\delta\log_2(n!)/2 have probability O(1/log⁡n)O(1/\log n). Histories below this threshold have at most (n!)1−δ/2(n!)^{1-\delta/2} outputs, whose uniform mass tends to zero. This proves (25). At the stated small-pp scale, sn(H2(p)+p)=o(n)s_n(\mathrm{H}_2(p)+p)=o(\sqrt{n}), so hˉn,p∼hn∼n/(2π)\bar{h}_{n,p}\sim h_n\sim\sqrt{n/(2\pi)} for even $n.

Local collision bounds: polynomial dependence on deck size

The proof method is deliberately common to the four families. A local alternative that exchanges two input cards supplies a random-swap projection. Three layers of such alternatives connect the deck along a path. Keeping the full central transposition spectrum then avoids a factor of order nn in the final mixing bound.

Extracting fair swaps without requiring a rare global event

Lemma 9.1 (Random-subset projection extraction). Let NN be a matching. Suppose an increment law can be sampled by first choosing auxiliary data, including S⊆NS\subseteq N, *and then independent fair

swaps on the edges of SS, acting on the input of a fixed remaining permutation. If every e∈Ne \in N has P(e∈S)≥ρ\mathbb{P}(e \in S) \ge\rho, then its adjoint norm deficit satisfies

D(f)≥ρ⟨f,(I−CN)f⟩.(26)\mathcal{D}(f) \ge\rho\langle f,(I-C_N)f\rangle. \tag*{(26)}

It suffices that the two local alternatives for an edge have masses a,ba,b: their common part supplies a fair swap with total mass 2min⁡(a,b)2\min(a,b); unmatched mass is retained as a separate outcome.

Proof. Conditionally the adjoint is Ud−1CSU_{d-1}C_S, so the conditional deficit is ⟨f,(I−CS)f⟩\langle f,(I-C_S)f\rangle. Mixture variance can only increase it. The commuting involutions associated to NN are simultaneously diagonalizable. On a nonconstant matching character with nonempty support E⊆NE \subseteq N, I−CSI-C_S equals one precisely when S∩E≠∅S \cap E \ne\varnothing. This event has probability at least ρ\rho, by considering any one e∈Ee \in E. This proves the quadratic-form inequality. Splitting two atoms into an equal common mass and residual masses proves the last assertion. Independence of the activation events is not required.

In applications with several disjoint local windows, fix the exterior data and group outcomes into orbits of the window flips. Each flip leaves the input counts at the beginning and end of its window unchanged. For card-weighted release the likelihood therefore factors into local window likelihoods and an unchanged exterior likelihood. For uniform block interleaving it is constant on each orbit. For Markov labels, separated windows are conditionally independent given the exterior labels. These facts justify independent common-part extractions within a layer. We never demand that all the windows be active simultaneously.

Lemma 9.2 (Three path layers). Suppose N1,N2,N3N_1,N_2,N_3 are matchings partitioning the edges of a Hamiltonian path, and D(f)≥κ⟨f,(I−CNj)f⟩\mathcal{D}(f) \ge\kappa\langle f,(I-C_{N_j})f\rangle for each jj. Then

tmix(ε)≤⌈2304n(n−1)κΛn,ε⌉.(27)t_{\mathrm{mix}}(\varepsilon) \le\left\lceil\frac{2304n(n-1)}{\kappa}\Lambda_{n,\varepsilon}\right\rceil. \tag*{(27)}

Proof. Let Aj=CNjA_j=C_{N_j} and S=(A1+A2+A3)/3S=(A_1+A_2+A_3)/3. The path comparison of Lemma 7.2 still gives LRT⪯8n∑eFeL_{\mathrm{RT}} \preceq8n\sum_e F_e, where Fe=(I−Uτe)/2F_e=(I-U_{\tau_e})/2. On a central eigenspace VλV_\lambda, Lemma 7.3 bounds the product A3A2A1A_3A_2A_1 and gives loss at least λ∥f∥22/(64n)\lambda\lVert f\rVert_2^2/(64n). If aj=∥(I−Aj)f∥2a_j=\lVert(I-A_j)f\rVert_2, its loss is at most

∑j=13(a1+⋯+aj)2≤6∑j=13aj2=18⟨f,(I−S)f⟩.\sum_{j=1}^{3}(a_1+\cdots+a_j)^2 \le6\sum_{j=1}^{3}a_j^2=18\langle f,(I-S)f\rangle.

Thus D(f)≥κλ∥f∥22/(1152n)\mathcal{D}(f)\ge\kappa\lambda\lVert f\rVert_2^2/(1152n) on VλV_\lambda. All relevant operators preserve these spaces. The spectral sum (16), at time κt/(2304n)\kappa t/(2304n), proves (27).

The polynomial estimates

Theorem 9.3 (Explicit local upper bounds). For even n=2m≥4n=2m\ge4 let ωn=2−n(nm)\omega_n=2^{-n}\binom{n}{m}. Define

ρI=q4min⁡{p2,q2/2},(28)\rho_I=q^4\min\{p^2,q^2/2\}, \tag*{(28)}
ρC=q61024(m+1),(29)\rho_C=\frac{q^6}{1024(m+1)}, \tag*{(29)}
ρB=q632768(1+mpq)m+1.(30)\rho_B=\frac{q^6}{32768(1+mpq)\sqrt{m+1}}. \tag*{(30)}

For F∈{I,C,B}F \in\{\mathrm{I},\mathrm{C},\mathrm{B}\} with ρF>0\rho_F > 0,

tmin⁡F(ε)≤⌈2304n(n−1)ωnρFΛn,ε⌉.(31)t_{\min}^{F}(\varepsilon) \le\left\lceil\frac{2304n(n-1)}{\omega_n\rho_F}\Lambda_{n,\varepsilon} \right\rceil. \tag*{(31)}

For all n≥4n \ge4 and p<1p < 1,

tmin⁡Mp(ε)≤⌈9216n(n−1)q−2Λn,ε⌉.(32)t_{\min}^{M_p}(\varepsilon) \le\left\lceil9216n(n-1)q^{-2}\Lambda_{n,\varepsilon} \right\rceil. \tag*{(32)}

Common cut-first geometry. Condition on K=mK=m and denote input cards in the two packets by a1,…,ama_1,\ldots,a_m and b1,…,bmb_1,\ldots,b_m. Use the matching M={{ai,bi}}M=\{\{a_i,b_i\}\} and split N={{bi,ai+1}:1≤i<m}N=\{\{b_i,a_{i+1}\}:1\le i<m\} into odd and even ii. Together these form the path a1,b1,a2,b2,…,am,bma_1,b_1,a_2,b_2,\ldots,a_m,b_m. The gadgets for a fixed parity use disjoint two-position windows. It suffices to prove activation probability at least ρF\rho_F for each edge; multiplying by the cut probability ωn\omega_n and applying Lemma 9.2 then gives (31). □

Interpolation activations. If ai,bia_i,b_i are singleton blocks, their tied midpoint keys give a fair swap of {ai,bi}\{a_i,b_i\}. At most four bonds must break, so the activation probability is at least q4q^4.

For an edge {bi,ai+1}\{b_i,a_{i+1}\} isolate positions i,i+1i,i+1 in both packets by breaking their external bonds, an event of probability at least q4q^4. Write a=aia=a_i, b=bib=b_i, c=ai+1c=a_{i+1}, d=bi+1d=b_{i+1}. If the two internal bonds break and both ties put left first, the local output is a,b,c,da,b,c,d, with conditional mass q2/4q^2/4. If both internal bonds survive and the tied two-card blocks put left first, it is a,c,b,da,c,b,d, with mass p2/2p^2/2. These outputs differ by exactly the input swap {b,c}\{b,c\}. Blocks outside the isolated window have keys outside its key interval and hence do not interfere. Common-part extraction activates the swap with probability at least 2q4min⁡(q2/4,p2/2)=ρI2q^4\min(q^2/4,p^2/2)=\rho_I. Disjoint windows have independent internal choices after the external bonds are fixed. Lemma 9.1 applies to each layer. □

Card-weighted activations. Conditional on the bond partitions, realize the interleaver by two independent continuous-time packet processes. A packet with aa cards remaining waits an exponential time of rate aa, then emits its next whole block. Competing exponential clocks give exactly the probability A/(A+B)A/(A+B); the construction is a proof device, not a new model parameter.

Isolate a two-position window i,i+1i,i+1 as four singleton cards, requiring at most six broken bonds. Let a=m−i+1≥2a=m-i+1\ge2. In one packet let SS be the time at which its prefix of i−1i-1 cards has been emitted. The rates visited before this time are a subset of a+1,…,ma+1,\ldots,m, whence

ES≤∑r=a+1m1r≤log⁡(m/a).\mathbb{E}S\le\sum_{r=a+1}^{m}\frac{1}{r}\le\log(m/a).

The two prefix times are independent and identically distributed under the imposed bonds. Divide [0,2log⁡(m/a)][0,2\log(m/a)] into bins of width 1/a1/a, including an endpoint bin. There are at most 2(m+1)2(m+1) bins since alog⁡(m/a)≤m/ea\log(m/a)\le m/e. At least half of the probability lies in this interval; if its length is zero, both prefix times are zero. Cauchy–Schwarz gives probability at least 1/[8(m+1)]1/[8(m+1)] that both times lie in one bin. The earlier ready packet waits for the later one with conditional probability at least e−1e^{-1}, since its current rate is aa. Thus with probability at least 1/[8e(m+1)]1/[8e(m+1)], both window heads are exposed before either is emitted.

At that moment both packets contain aa cards. Each of the local orders ai,bi,ai+1,bi+1a_i,b_i,a_{i+1},b_{i+1} and ai,ai+1,bi,bi+1a_i,a_{i+1},b_i,b_{i+1} has conditional probability at least 1/641/64. This follows directly by multiplying the four card-count ratios; the remaining counts differ by at most two, and the cases a=2a=2 only force some of the choices. After these four singleton releases both orders leave the same state. Their common part therefore activates {bi,ai+1}\{b_i,a_{i+1}\} with probability at least q6/[256e(m+1)]≥ρCq^6/[256e(m+1)]\ge\rho_C.

For {ai,bi}\{a_i,b_i\} use a one-position singleton window, at most four broken bonds, and the two orders ai,bia_i,b_i and bi,aib_i,a_i. The same prefix argument applies with a≥1a\ge1, and each order has at least least 1/4. Its activation probability is larger than ρC\rho_C. For a layer, local flips preserve its good windows and all their entry and exit counts; the likelihood factorization preceding Lemma 9.2 justifies simultaneous fair extraction.

Block-weighted activations. Again isolate a two-position window as four singleton cards, at cost at most q6q^6. Require that the two packets have the same number of prefix blocks, and also the same number of suffix blocks. Prefix and suffix partitions are independent. For a binomial variable YY of variance vv and an independent copy Y′Y', concentration in an interval of at most 5v+15\sqrt{v}+1 integers gives

P(Y=Y′)=∑jP(Y=j)2≥110v+1.\mathbb{P}(Y=Y')=\sum_j \mathbb{P}(Y=j)^2 \geq\frac{1}{10\sqrt{v+1}}.

Indeed, Chebyshev at radius 2v+12\sqrt{v+1} leaves probability at least 3/43/4, and Cauchy–Schwarz gives the displayed bound. Prefix and suffix block counts are shifted binomials or deterministic zeros. Their two agreements therefore have joint probability at least 1/[100(1+mpq)]1/[100(1+mpq)].

On agreement, let each packet have uu prefix blocks and vv suffix blocks, and put b=u+2+v≤mb=u+2+v\leq m. Under uniform block interleaving the chance of reaching the two window heads together is

(2uu)(2b−2ub−u)(2bb)≥14b+1≥14m+1.\frac{\binom{2u}{u}\binom{2b-2u}{b-u}}{\binom{2b}{b}} \geq\frac{1}{4\sqrt{b+1}} \geq\frac{1}{4\sqrt{m+1}}.

For example, this inequality follows from 4j/(2j+1)≤(2jj)≤4j/j+14^j/(2\sqrt{j}+1)\leq\binom{2j}{j}\leq4^j/\sqrt{j+1}, including j=0j=0. Each of the two four-card patterns used above has conditional probability at least 1/641/64, now with block counts replacing card counts. Their probabilities are equal, so their union is already a fair swap. Multiplying the estimates gives activation probability at least q6/[12800(1+mpq)m+1]≥ρBq^6/[12800(1+mpq)\sqrt{m+1}]\geq\rho_B. One-position windows similarly give the matching MM with at least this probability. Within a layer, condition on the partitions and the exterior interleaving. All allowed orientations then have equal weight, which verifies Lemma 9.1.

Markov-label activations. Put b=q/2b=q/2 and a=1−ba=1-b. Partition the neighboring input edges {i,i+1}\{i,i+1\} into three layers according to ii modulo three. Pairs in one layer have at least one intervening fixed label, and are conditionally independent given the exterior labels. For an interior pair, require its two exterior labels to agree and its two interior labels to differ. Exchanging the interior labels 01↔1001\leftrightarrow10 has equal conditional weight and swaps exactly the two adjacent input cards in the inverse shuffle. The total activation probability is 2ab2≥q2/42ab^2\geq q^2/4: the four relevant length-four patterns each have probability ab2/2ab^2/2.

For a pair touching an endpoint, common-part extraction conditional on its single exterior neighbor has activation probability 2b22b^2, also at least q2/4q^2/4. Apply Lemma 9.1 and then Lemma 9.2 with κ=q2/4\kappa=q^2/4. This proves (32). The adjacent-mark collision mechanism is related to that used in the stronger fixed-parameter analysis of [13]; the present argument is a direct parameter-explicit spectral comparison, not an improvement on their nn dependence.

A sharper high-adhesion bound for the cut-first models

The local bounds lose unnecessary powers of qq when almost every contact survives. A different argument uses the frequent rotations and the rare one-break moves. Unlike the balanced-cut proof, it works for odd decks too.

Theorem 10.1 (Rotation and one-break comparison). For n≥4n \ge4 let ωk=2−n(nk)\omega_k = 2^{-n}\binom{n}{k} and define

ck=min⁡{1/3,k/(2n)},ηn=∑k=2n−2min⁡{ωkck,ωk+1ck+1}.c_k = \min\{1/3, k/(2n)\}, \qquad\eta_n = \sum_{k=2}^{n-2} \min\{\omega_k c_k, \omega_{k+1}c_{k+1}\}.

Then ηn>0\eta_n > 0 and ηn→1/4\eta_n \to1/4. For each of CpC_p, BpB_p, IpI_p, with 0<p<10 < p < 1, put

an,p=pn−24n,bn,p=ηnqpn−3.a_{n,p} = \frac{p^{n-2}}{4n}, \qquad b_{n,p} = \eta_n q p^{n-3}.

An explicit common upper bound is

tmix(ε)≤⌈72n2(n−1)min⁡{an,p,bn,p}Λn,ε⌉.(33)t_{\mathrm{mix}}(\varepsilon) \le\left\lceil\frac{72n^2(n-1)}{\min\{a_{n,p},b_{n,p}\}}\Lambda_{n,\varepsilon}\right\rceil. \tag*{(33)}

In particular (4) holds with an absolute constant.

Proof. Write r=(1,2,…,n)r=(1,2,\ldots,n) for a cyclic rotation and A=n−1∑j=0n−1UrjA=n^{-1}\sum_{j=0}^{n-1}U_{r^j} for its invariant-space projection. The all-surviving-bonds event shows that the increment law at pp contains pn−2p^{n-2} times its law at p=1p=1. Empty cuts can be split with this same weight, so the assertion is unconditional.

For B1B_1 and I1I_1 the rotation operator is (I+EUKr)/2(I+EU^r_K)/2, with K∼Bin⁡(n,1/2)K\sim\operatorname{Bin}(n,1/2). For C1C_1 it is the same expression with K∼Bin⁡(n−1,1/2)K\sim\operatorname{Bin}(n-1,1/2): indeed ωk(n−k)/n=12P(Bin⁡(n−1,1/2)=k)\omega_k(n-k)/n=\frac{1}{2}\mathbb{P}(\operatorname{Bin}(n-1,1/2)=k). At any nontrivial nnth root of unity the binomial multiplier has modulus at most ∣cos⁡(π/n)∣n−1\lvert\cos(\pi/n)\rvert^{n-1}. The inequalities

cos⁡(π/n)≤1−2/n2,1−e−2(n−1)/n2≥12n\cos(\pi/n) \le1-2/n^2, \qquad1-e^{-2(n-1)/n^2} \ge\frac{1}{2n}

imply a squared-norm deficit at least 1/(4n)1/(4n) away from AA. Mixture variance therefore gives

D(f)≥an,p∥(I−A)f∥22.(34)\mathcal{D}(f) \ge a_{n,p}\lVert(I-A)f\rVert_2^2. \tag*{(34)}

Now let Tk=(k,k+1,…,n)T_k=(k,k+1,\ldots,n), the output-list permutation that moves card kk to the bottom. At cut kk, use left blocks [1,…,k−1][1,\ldots,k-1], [k][k] and one whole right block. This requires one broken bond and n−3n-3 surviving bonds, of probability qpn−3q p^{n-3}. The order left-large, right, left-singleton produces TkT_k. Its conditional probability is one for interpolation, 1/31/3 for block-weighted release, and knn−kn−k+1≥k/(2n)\frac{k}{n}\frac{n-k}{n-k+1}\ge k/(2n) for card-weighted release. Thus every family gives TkT_k mass at least wk=ωkckqpn−3w_k=\omega_kc_kq p^{n-3}, for 2≤k≤n−12\le k\le n-1.

Allocate half of each such atom to each neighboring pair of indices, discarding unused endpoint allocations. For the pair Tk,Tk+1T_k,T_{k+1}, the conditional variance contributes at least

min⁡{wk,wk+1}4∥(I−U(k,k+1))f∥22=min⁡{wk,wk+1}⟨f,F(k,k+1)f⟩,\frac{\min\{w_k,w_{k+1}\}}{4}\lVert(I-U_{(k,k+1)})f\rVert_2^2=\min\{w_k,w_{k+1}\}\langle f,F_{(k,k+1)}f\rangle,

because TkTk+1−1=(k,k+1)T_kT_{k+1}^{-1}=(k,k+1). Summing disjoint allocations gives

D(f)≥bn,p∑kvk∥F(k,k+1)f∥22,vk=min⁡{ωkck,ωk+1ck+1}ηn.(35)\mathcal{D}(f)\ge b_{n,p}\sum_k v_k\lVert F_{(k,k+1)}f\rVert_2^2,\qquad v_k=\frac{\min\{\omega_kc_k,\omega_{k+1}c_{k+1}\}}{\eta_n}. \tag*{(35)}

Here vk≥0v_k\ge0 and ∑kvk=1\sum_kv_k=1.

On a central eigenspace VλV_\lambda, put g=Afg=Af and x=∥f−g∥2x=\lVert f-g\rVert_2, y=∑kvk∥F(k,k+1)f∥22y=\sum_kv_k\lVert F_{(k,k+1)}f\rVert_2^2. Cyclic invariance makes all cyclic neighboring-edge energies of gg equal. The path comparison consequently yields

λ∥g∥22≤8n2∑kvk∥F(k,k+1)g∥22.\lambda\lVert g\rVert_2^2\le8n^2\sum_kv_k\lVert F_{(k,k+1)}g\rVert_2^2.

Since each FF is a contraction and λ≤2\lambda\le2, it follows that λ∥f∥22≤18n2(x+y)\lambda\lVert f\rVert_2^2 \le18n^2(x+y). Equations (34) and (35) give D(f)≥min⁡(an,p,bn,p)(x+y)/2D(f) \ge\min(a_{n,p},b_{n,p})(x+y)/2. The central spectral sum proves (33).

Finally, on ∣k−n/2∣≤n2/3\lvert k-n/2\rvert\le n^{2/3}, the adjacent binomial-mass ratios tend uniformly to one and ck→1/4c_k \to1/4. This interval has binomial probability tending to one. Outside it the total mass tends to zero. Thus ηn→1/4\eta_n \to1/4; its finite values for n≥4n \ge4 are positive. This proves the absolute-constant order bound.

Proof of Theorem 2.5. For fixed nn, (33) is On,ε(q−1)O_{n,\varepsilon}(q^{-1}) as p↑1p \uparrow1, while (20) gives the matching Ωn,ε(q−1)\Omega_{n,\varepsilon}(q^{-1}) lower bound. For MpM_p, combine (32) with (21). The numerator 1−ε−1/(n−1)1-\varepsilon-1/(n-1) is positive in the stated range.

Remark 10.2 (Why one parameter has two different singular exponents). In a cut-first model, the imposed cut already creates two packets. One additional broken contact can produce a move outside the rotation subgroup. In the inverse-label model, zero or one label switch still gives only a rotation. At least two switches are necessary. This is a structural distinction in the models, not evidence for a universal physical exponent. For n=2n=2 the rotation subgroup is all of Sn\mathcal{S}_n, so the quadratic-exponent statement is deliberately not made.

Small adhesion, regeneration, and a cutoff regime

Proposition 11.1 (A comparison that is valid without commutation). For even nn, let βn=min⁡{ωn/2,ωn/2+1}\beta_n=\min\{\omega_{n/2},\omega_{n/2+1}\}. For p<1p<1,

tmixp(ε)≤⌈32768n(n−1)βnqn−2Λn,ε⌉.t_{\mathrm{mix}}^p(\varepsilon) \le\left\lceil\frac{32768n(n-1)}{\beta_n q^{n-2}}\Lambda_{n,\varepsilon}\right\rceil.

Proof. With probability qn−2q^{n-2} all internal bonds at a nonempty cut break. Splitting empty-cut identity mass by the same factor yields Qp=qn−2Q0+(1−qn−2)RQ_p=q^{n-2}Q_0+(1-q^{n-2})R for a contraction RR. Mixture variance gives Dp(f)≥qn−2D0(f)D_p(f)\ge q^{n-2}D_0(f). Apply the central comparison of Lemma 7.4 and its full spectral proof. No claim that arbitrary intervening shuffles commute or can only accelerate mixing is used.

Proposition 11.2 (A GSR regeneration-window bound). Let F∈{C,B,M}F\in\{C,B,M\}, and put νC=νB=n−2\nu_C=\nu_B=n-2, νM=n−1\nu_M=n-1, and r=⌈log⁡2(n(n−1))⌉r=\lceil\log_2(n(n-1))\rceil. For n≥4n\ge4 and p<1p<1,

tmixFp(ε)≤r⌈2q−νFrlog⁡(1/ε)⌉.(36)t_{\mathrm{mix}}^{F_p}(\varepsilon) \le r\left\lceil2q^{-\nu_F r}\log(1/\varepsilon)\right\rceil. \tag*{(36)}

Proof. One round contains qνFq^{\nu_F} times its p=0p=0 kernel, which is GSR or inverse GSR. A run of rr such components therefore has weight qνFrq^{\nu_F r} in the rr-step kernel. After rr inverse GSR shuffles, independent uniform rr-bit labels have all distinct values with probability b=(2r)n/2rn≥1−n(n−1)/2r+1≥1/2b=(2^r)_n/2^{rn}\ge1-n(n-1)/2^{r+1}\ge1/2. Conditional on this event their order is uniform, so the rr-step GSR kernel minorizes bπnb\pi_n. This standard strong-stationary construction is described in [2, 5]. Consequently each rr-step window has a uniform component of mass at least qνFr/2q^{\nu_F r}/2. All residual kernels preserve uniform measure. Iterating the minorization gives (36). This argument uses whole windows, not invalid thinning of isolated successful rounds.

In particular, for any fixed c>0c>0, if p≤c/(nlog⁡n)p\le c/(n\log n) then q−νFrq^{-\nu_F r} stays bounded as n→∞n\to\infty. The regeneration bound and the information floor give tmixFp(1/4)=Θc(log⁡n)t_{\mathrm{mix}}^{F_p}(1/4)=\Theta_c(\log n) for all three GSR-derived families. The next result strengthens this order statement to the classical cutoff location under a little-oo assumption.

Theorem 11.3 (Classical cutoff survives sufficiently weak adhesion). For F∈{C,B,M}F \in\{\mathrm{C},\mathrm{B},\mathrm{M}\} and all integers t≥0t \ge0,

∣dn,pF(t)−dn,0F(t)∣≤t(n−1)p.(37)\left|d_{n,p}^{F}(t)-d_{n,0}^{F}(t)\right| \le t(n-1)p. \tag*{(37)}

In particular, if pn=o((nlog⁡n)−1)p_n=o((n\log n)^{-1}), these families have the GSR cutoff at 32log⁡2n\frac{3}{2}\log_2 n, with an O(1)O(1) window. On time sequences where the classical profile converges, their profiles have the same limit.

Proof. Couple each round with its p=0p=0 version until the first surviving bond. At most n−1n-1 contacts are tested in a round, and, conditional on no surviving bond, the interleaving or labeling is precisely the original GSR rule. A union bound over the tested contacts and rounds gives (37). The error is o(1)o(1) throughout any O(log⁡n)O(\log n) time range under the hypothesis. Transfer the classical total-variation cutoff and profile from [5]; inversion does not change the Markov family’s distance. This does not prove cutoff for fixed p>0p>0.

RegimeWhat is provedWhat is not proved
p=0p=0GSR cutoff; slow interpolation lower boundInterpolation’s sharp order or cutoff
p=O((nlog⁡n)−1)p=O((n\log n)^{-1})Logarithmic order for C, B, M; GSR cutoff under little-ooA fixed-positive-pp cutoff theorem
Fixed 0<p<10<p<1Polynomial cut-first bounds; Op(log⁡4n)O_p(\log^4 n) for MMatching orders for the cut-first families
n(1−p)=O(1)n(1-p)=O(1)Improved cut-first upper bound; inverse-model quadratic obstructionSharp powers of nn
Fixed nn, p↑1p \uparrow1Exact linear versus quadratic parameter exponentsA large-deck cutoff conclusion

Table 3. Different limits answer different questions. A fixed-nn adhesion exponent is not a substitute for a uniform-in-nn mixing theorem.

Finite calculations and reproducibility

Table 4 evaluates the exact binomial sums in the entropy formula. The entropy time ana_n is not an estimate proved to equal the mixing time, especially for small nn.

nnH(K)H(K)ETn(K)\mathbb{E}T_n(K)hnh_nana_nlower bound at 1/41/4
523.89733.64627.543429.904323
644.04714.89108.938133.116125
2565.04718.587213.6343123.511793
10246.047115.473021.5201407.4797306
163848.047154.773762.82083275.14582457

Table 4. Entropy quantities in bits and rounds. The last column is the ceiling of Proposition 5.2 with ε=1/4\varepsilon=1/4, not an observed mixing time.

The baseline script verify_shuffle.py performs the following diagnostics, recorded in verification_results.json:

  • Exact rational midpoint enumeration checks the tie formula for 8,382 deck-size/cut pairs with 2≤n≤1282 \le n \le128.

  • For each of the 63 even sizes from 4 through 128, it checks the Hamiltonian-cycle identity, the containment of the nearby-cut tie in MM, and the noncentral-divisor bound.

  • It enumerates the full transition matrices on S4\mathfrak{S}_4 and S6\mathfrak{S}_6, checks double stochasticity, and checks the two quadratic-form inequalities numerically. The minimum eigenvalues are nonnegative up to floating-point errors below 10−1410^{-14}.

  • Direct matrix iteration gives tmix(1/4)=3t_{\mathrm{mix}}(1/4) = 3 for n=4n = 4 and tmix(1/4)=4t_{\mathrm{mix}}(1/4) = 4 for n=6n = 6.

These small cases can detect convention or implementation errors. They provide no empirical evidence for an asymptotic cutoff and are not used as premises in the proofs.

The combinatorial and entropy checks require only the Python standard library. The optional full-matrix checks require NumPy. They can be run as

python3 verify_shuffle.py --max-n 128 --matrix \
    --output verification_results.json

No Monte Carlo estimate, training procedure, or fitted asymptotic exponent is used in this manuscript.

For the four families, the extension script verify_adhesive_shuffles.py additionally checks:

  • 140 exact rational increment laws: all four families, 2≤n≤82 \le n \le8, and p∈{0,1/4,1/2,3/4,1}p \in\{0, 1/4, 1/2, 3/4, 1\}. These checks include normalization, the block versus updated-count descriptions of CpC_p, the two descriptions of MpM_p, the original interpolation law at p=0p = 0, and endpoint supports.

  • The conditional binomial block-count law and the interpolation entropy bound on the same grid; the insertion identity and cyclic Fourier inequality through n=128n = 128.

  • All three local-layer quadratic-form inequalities for every family at (n,p)=(4,1/4)(n,p) = (4, 1/4), (4,1/2)(4, 1/2), (4,9/10)(4, 9/10), and (6,1/2)(6, 1/2); and both rotation/insertion inequalities for the three cut-first families at these points and at (5,1/2)(5, 1/2) and (5,9/10)(5, 9/10).

  • Direct full-state iteration for Table 5, including the distances immediately before and at each reported threshold. Every displayed comparison includes all four completed arms; no partial or timed-out arm is silently omitted.

nnppCpC_pBpB_pIpI_pMpM_p
403333
41/21/24427
49/109/1019186143
603343
61/21/26638
69/109/10252410132

Table 5. Numerically computed tmix(1/4)t_{\mathrm{mix}}(1/4) in full-shuffle units, starting from the identity. These are small-deck diagnostics, not asymptotic evidence. In particular, interpolation need not slow monotonically as adhesion increases: breaking the perfectly regular schedule can initially help. This observation is not a physical calibration.

Results are recorded in adhesive_verification_results.json. The transition probabilities are enumerated exactly before conversion to floating point for matrix operations. Numerical positive-semidefiniteness checks use tolerance 10−1010^{-10} and do not certify the symbolic inequalities. Run the extended checks with:

python3 verify_adhesive_shuffles.py --max-n 8 --matrix \
    --output adhesive_verification_results.json

Cutoff, limitations, and directions for improvement

What remains unresolved

A family has total-variation cutoff at times sns_n if, for each fixed δ∈(0,1)\delta\in(0,1), the distances at (1−δ)sn(1-\delta)s_n and (1+δ)sn(1+\delta)s_n tend respectively to one and zero. Theorem 11.3 proves cutoff for the GSR-derived families under a vanishing-adhesion hypothesis. It does not extend to a fixed positive adhesion parameter, nor to the interpolation family.

For unglued interpolation, Theorem 3.4 proves the first limit with sn=ans_n=a_n, but not the second. For every fixed ε∈(0,1)\varepsilon\in(0,1), they imply

lim inf⁡n→∞n eventmix(n)(ε)an≥1,tmix(n)(1/4)=O(n5/2log⁡n).\liminf_{\substack{n\to\infty\\ n\ \mathrm{even}}}\frac{t_{\mathrm{mix}}^{(n)}(\varepsilon)}{a_n}\ge1,\qquad t_{\mathrm{mix}}^{(n)}(1/4)=O(n^{5/2}\log n).

Thus the current lower and upper scales differ by a factor of order n2n^2. We do not know from these arguments whether the true scale is nlog⁡n\sqrt{n}\log n, a larger polynomial scale, or something between them. Likewise, the fixed-positive-pp cut-first bounds do not match in nn. The sharp parameter exponents in Theorem 2.5 hold with nn fixed, and cannot settle these large-deck questions.

Sufficient input entropy is not sufficient mixing. GSR shuffling is a useful warning: its input-entropy lower scale is log⁡2n\log_2 n, while its actual total-variation cutoff is 32log⁡2n\frac{3}{2}\log_2 n [5]. The word “entropic” in this manuscript labels a lower-bound clock, not a proved location of cutoff.

Where the upper argument loses information

The unglued proof deliberately uses only two cuts. Their probabilities are Θ(n−1/2)\Theta(n^{-1/2}), and the induced comparison graph is only a cycle. All other cuts are discarded through a contraction inequality. This robust simplification is responsible for much of the potential loss. It also replaces nonreversible deterministic transport by a norm comparison, which may conceal accelerated spreading over several rounds.

Three concrete improvements suggest themselves. First, use a window of Θ(n)\Theta(\sqrt{n}) typical cuts rather than two individual cuts, and analyze the resulting collection of conjugated matchings. Second, study a multistep operator in a frame following the deterministic merges; expansion of these matchings might give stronger contraction than a one-step comparison. Third, adapt the collision-based entropy approach of Morris [19] directly to the cut-dependent matchings. None of these steps is supplied by the present proof.

For the adhesive cut-first models, the local argument uses just the balanced cut and very conservative probabilities of meeting in selected singleton windows. The high-adhesion argument instead retains rotations and one-break insertions. Taking the better estimate reduces parameter losses, but neither comparison is expected to capture all of the transport created by typical shuffles. For MpM_p, the literature’s Op(log⁡4n)O_p(\log^4 n) result already improves our elementary nn dependence when p<1p<1 is fixed; our contribution there is explicit endpoint control.

Other deck sizes and other noise scales

For odd nn, unglued interpolation has no midpoint ties. The rule then has only the cut randomness, and elementary support counting already gives an order-nn lower bound at fixed error. The sharper even-deck analysis is driven by an event, the exactly balanced cut, that does not exist for odd decks. No upper theorem for odd-deck I0I_0 is claimed here. In contrast, Theorem 10.1 covers all three cut-first models on odd decks when 0<p<10 < p < 1, and the Markov-label bound works on either parity.

Continuous perturbations smaller than n−2n^{-2} all define the same chain. Perturbations large enough to reverse strict cross-packet comparisons can inject additional randomness. One must then specify the noise law, its scaling, and whether within-packet order is enforced. A single common phase per packet is different again: at an equal cut, its choices are globally correlated rather than independent for each pair. These variants should not be conflated in a cutoff claim.

Conclusion

One independently resampled contact-survival probability yields several distinct, mathematically transparent shuffles. Card-weighted selection must update remaining card counts after every drop; block-weighted selection, midpoint scheduling, and correlated-label inversion are different rules, not equivalent implementations.

The paper establishes explicit parameter-dependent upper and lower bounds, an interpolation information obstruction, and exact fixed-deck adhesion exponents: linear for cut-first release and quadratic for correlated labels. Classical cutoff transfers in a sufficiently weak perturbation regime. Sharp large-deck mixing orders and cutoff for the new fixed-parameter cut-first families remain open within this analysis. The contact model is physically motivated, but is neither a force law nor an experimentally validated model of hand shuffling.

References

  1. [1]D. Aharonov, I. Arad, Z. Landau, and U. Vazirani. The Detectability Lemma and Quantum Gap Amplification. Preprint, 2008. https://arxiv.org/abs/0811.3412.
  2. [2]D. Aldous and P. Diaconis. Shuffling cards and stopping times. American Mathematical Monthly 93 (1986), 333–348.DOI
  3. [3]H. Alarcón, T. Salez, C. Poulard, J.-F. Bloch, É. Raphaël, K. Dalnoki-Veress, and F. Restagno. Self-amplification of solid friction in interleaved assemblies. Physical Review Letters 116 (2016), 015502. https://doi.org/10.1103/PhysRevLett.116.015502.
  4. [4]A. Anshu, I. Arad, and T. Vidick. Simple proof of the detectability lemma and spectral gap amplification. Physical Review B 93 (2016), 205142. https://doi.org/10.1103/PhysRevB.93.205142.
  5. [5]D. Bayer and P. Diaconis. Trailing the dovetail shuffle to its lair. Annals of Applied Probability 2 (1992), 294–313. https://doi.org/10.1214/aoap/1177005705.
  6. [6]T. A. L. Burgo, C. A. Silva, L. B. S. Balestrin, and F. Galembeck. Friction coefficient dependence on electrostatic tribocharging. Scientific Reports 3 (2013), 2384. https://doi.org/10.1038/srep02384.
  7. [7]P. Diaconis and J. Fulman. The Mathematics of Shuffling Cards. American Mathematical Society, 2023. https://www.ams.org/books/mbk/146/.DOI
  8. [8]P. Diaconis. The cutoff phenomenon in finite Markov chains. Proceedings of the National Academy of Sciences USA 93 (1996), 1659–1664. https://doi.org/10.1073/pnas.93.4.1659.
  9. [9]P. Diaconis, R. L. Graham, and W. M. Kantor. The mathematics of perfect shuffles. Advances in Applied Mathematics 4 (1983), 175–196. https://darkwing.uoregon.edu/~kantor/PAPERS/PerfectShuffles.pdf.DOI
  10. [10]P. Diaconis and L. Saloff-Coste. Comparison techniques for random walk on finite groups. Annals of Probability 21 (1993), 2131–2156. https://pi.math.cornell.edu/~lsc/papers/comp-fig.pdf.DOI
  11. [11]P. Diaconis and M. Shahshahani. Generating a random permutation with random transpositions. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 57 (1981), 159–179. https://doi.org/10.1007/BF00535487.
  12. [12]Y. Jiang. A subquadratic upper bound for the mixing time of the Thorp shuffle. Preprint, submitted October 3, 2026. https://arxiv.org/abs/2610.18884.
  13. [13]J. Jonasson and B. Morris. Rapid mixing of dealer shuffles and clumpy shuffles. Electronic Communications in Probability 20 (2015), no. 20, 1–11. https://doi.org/10.1214/ECP.v20-3862.
  14. [14]J. Jonasson. The overhand shuffle mixes in Θ(n² log n) steps. Annals of Applied Probability 16 (2006), 231–243. https://doi.org/10.1214/1050516050000000692.
  15. [15]H. Lacoin. Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion. Annals of Probability 44 (2016), 1426–1487. https://arxiv.org/abs/1309.3873.
  16. [16]S. P. Lalley. Riffle shuffles and their associated dynamical systems. Journal of Theoretical Probability 12 (1999), 903–932. https://doi.org/10.1023/A:1021636902356.
  17. [17]D. A. Levin and Y. Peres, with contributions by E. L. Wilmer. Markov Chains and Mixing Times, second edition. American Mathematical Society, 2017. https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf.
  18. [18]B. Morris. The mixing time of the Thorp shuffle. SIAM Journal on Computing 38 (2008), 484–504. https://doi.org/10.1137/050636231.
  19. [19]B. Morris. Improved mixing time bounds for the Thorp shuffle and L-reversal chain. Annals of Probability 37 (2009), 453–477. https://doi.org/10.1214/08-AOP409.
  20. [20]B. Morris. Improved mixing time bounds for the Thorp shuffle. Combinatorics, Probability and Computing 22 (2013), 118–132. https://doi.org/10.1017/S0963548312000478.
  21. [21]M. Palomares. Comparing the Mixing Rates of Neat Riffle Shuffles. University of Michigan REU report, August 2025; mentor M. Conger. https://lsa.umich.edu/content/dam/math-assets/reu-su22/2025/REU_Report_Final_Mateo_Palomares.pdf.
  22. [22]R. Pemantle. Randomization time for the overhand shuffle. Journal of Theoretical Probability 2 (1989), 37–49. https://doi.org/10.1007/BF01048267.
  23. [23]B. N. J. Persson, M. Scaraggi, and A. I. Volokitin. Contact electrification and the work of adhesion. Preprint, 2013. https://arxiv.org/abs/1305.2709.
  24. [24]M. Sellke, J. Shi, and J. Wang. Universality of Cutoff for Riffle Shuffling. Preprint, 2025. https://arxiv.org/abs/2510.22783.
  25. [25]E. O. Thorp. Nonrandom shuffling with applications to the game of faro. Journal of the American Statistical Association 68 (1973), 842–847. https://doi.org/10.1080/01621459.1973.10481434.
  26. [26]D. B. Wilson. Mixing times of lozenge tiling and card shuffling Markov chains. Annals of Applied Probability 14 (2004), 274–325.DOI

Paper details

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

views · 3

downloads · 0

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

  • Mathematics

AI

View statement
Looking for related papers…
Contents