Mixing Time of the Random-Pair Monte Shuffle

Introduction

The random-transposition shuffle chooses two positions independently and uniformly at each step and exchanges the cards at those positions. Diaconis and Shahshahani [5] proved that its mixing time is $\frac{1}{2}n\log n+O(n)$. We ask how the mixing time changes when the chosen positions are revealed and the only hidden choice is whether to exchange the two cards.

We study the random-pair Monte shuffle, which exchanges the cards at a uniformly sampled pair of positions with probability $1/2$. The sequence of pairs, called the schedule, is public, and the exchange decisions are independent hidden bits. For each schedule we measure the total variation distance of the resulting distribution on permutations from uniform, and then average this distance over schedules.

In this paper we prove that the mixing time is $2n\log n + O(n)$. Revealing the schedule therefore doubles the leading term relative to the ordinary $1/2$-lazy random-transposition shuffle, whose mixing time is $n\log n + O_{\varepsilon}(n)$. Together with the factor of two due to laziness, this gives a factor of four relative to classical random transpositions.

Our shuffle is an instance of the Monte framework introduced by Morris [14]. Here we consider shuffles specified by a public schedule of fair switches, each of which either exchanges the cards at two specified positions or leaves them in place, with equal probabilities. The schedule may be fixed, as in the Thorp shuffle, or random, as in our model. Several Monte shuffles are known to mix in $\Theta(n\log n)$ individual switches, including the Thorp shuffle by a recent result [19].

Our bounds determine both the leading constant and an $O(n)$ cutoff window. Saloff-Coste and Zúñiga, in their refined analysis of classical random transpositions, observe that “It is quite rare to be able to capture the mixing time of a chain with such precision” [22]. To our knowledge, the random-pair Monte shuffle is the first public-schedule Monte shuffle whose full-permutation mixing time has been determined up to an additive $O(n)$ term.

The public schedule defines a switching network, with the hidden bits determining the switch settings. Such networks have cryptographic applications in constructions of Oblivious RAM [8] and format-preserving encryption [9]. For an oblivious shuffle based on pairwise exchanges, a switching network captures its threat model: the adversary learns the network from the memory access pattern, while the switch settings remain hidden. Each step reads two records, re-encrypts them in private memory, and writes back, concealing whether they were exchanged. Security of shuffling-based Oblivious RAM requires the final permutation to remain indistinguishable from uniform even given the observed access pattern. Format-preserving encryption can be constructed from a switching network as long as the trajectory of any card can be efficiently traced in both directions.

Disjoint switches commute and can be executed in parallel, provided that their dependencies are respected. Combining our mixing bound with the dependency graph depth estimate of Czumaj and Lingas [2] gives, for fixed error and failure probabilities, public switching networks with at most $2n \log n + O(n)$ switches and $O(\log n)$ depth. The probability is over the choice of the network; the mixing guarantee is conditional on that choice. Explicit bounds are given in § 3.

Notation

All logarithms are natural unless a base is indicated. We use the following notation:

$n$	Number of cards.
$[n]$	$\{1,\ldots,n\}$.
$S_n$	Symmetric group on $[n]$.
$\overset{\$}{\leftarrow}$ | Uniform sampling.
$U_n$	Uniform distribution on $S_n$.
$\mathrm{id}$	Identity permutation.
$\mathbf{1}$	All-ones vector in $\mathbb{R}^n$.
$\mathbf{e}_i$	$i$th standard basis vector of $\mathbb{R}^n$.
$I$	Identity matrix.
$R_\sigma$	Permutation matrix of $\sigma\in S_n$ defined as $R_\sigma\mathbf{e}_i = \mathbf{e}_{\sigma(i)}$.
$\mathcal{L}(X)$	Distribution of a random variable $X$.
$\oplus$	XOR, applied componentwise to bit vectors.
$\mu* \nu$	Convolution: $(\mu* \nu)(\sigma) = \sum_\gamma\mu(\gamma)\nu(\gamma^{-1}\sigma)$.
$\lVert\mu-\nu\rVert_{\mathrm{TV}}$	$\frac{1}{2}\sum_x \lvert\mu(x)-\nu(x)\rvert$.
$\chi^2(\mu\mathbin\Vert U_n)$	$n!\sum_{\sigma\in S_n}\mu(\sigma)^2-1$.
$d_\infty(\mu,U_n)$	Relative $L^\infty$ error: $\max_{\sigma\in S_n}\lvert n!\mu(\sigma)-1\rvert$.
$\operatorname{tr}(A)$	Matrix trace, $\sum_i A_{ii}$.
$\operatorname{Tr}_W(L)$	Operator trace of $L: W \to W$.
$\lVert A\rVert_F^2$	Squared Frobenius norm, $\operatorname{tr}(A^\mathsf{T}A)=\sum_{i,j} A_{ij}^2$.

Permutations map card labels to positions, and products act from right to left.

Random-pair Monte shuffle and main results

We define the random-pair Monte shuffle on $n$ cards as follows. At each step $t$, sample $x_t,y_t$ independently and uniformly with replacement from $[n]$, and set $\tau_t=(x_t\,y_t)$, with $\tau_t=\mathrm{id}$ when $x_t=y_t$. All endpoint samples are independent across steps. Each $\tau_t$ specifies a switch.

Independently, sample a private bit vector $B=(b_1,\ldots,b_m)$ uniformly from $\{0,1\}^m$, and set

For fixed $T$, the distribution $\Pi_T$ averages over the private bit vector $B$. The function $\pi_t(T,B)$ uses only the first $t$ entries of each argument; we abbreviate it to $\pi_t$ when the inputs are understood. We take $T_0$ to be the empty schedule and $\pi_0(T,B)=\mathrm{id}$. All $m$ sampled pairs, including equal-endpoint null steps, count toward mixing time. Define the conditional error and its schedule average by

Equivalently,

The target is therefore a uniform full permutation independent of its public schedule. For $0<\varepsilon<1$, let

We prove Theorem 1.1 in § 2. Doubling the leading term in the number of steps suffices for the stronger conditional pointwise guarantee of Proposition 2.3. For fixed $0<\varepsilon,\delta<1$, a schedule of length $4n\log n+O_{\varepsilon,\delta}(n)$ satisfies

with probability at least $1-\delta$ over the public schedule.

For the upper bound in Equation (6), we run two copies of the shuffle with the same schedule and independent private bits. After averaging over schedules, their relative permutation follows the ordinary $1/2$-lazy random-transposition walk. The collision probability of the two copies is therefore the return probability of this auxiliary walk. Its normalized excess over $1/n!$ equals the expected conditional chi-square error of our shuffle. We bound this error using the $L^2$ estimate of Saloff-Coste and Zúñiga [22], then apply the standard inequality relating total variation and chi-square distance. Ordinary TV mixing of the auxiliary walk is not sufficient: the argument needs control of its return probability. This accounts for the additional factor of two beyond laziness.

For the lower bound (Equation (5)), we construct a test function of the schedule and the observed permutation. Its value is the expected number of cardwise agreements with an independent run under the same schedule, centered by subtracting one. This function aggregates the small biases in the destinations of individual cards. To turn the difference in means into a distinguisher, we control the statistic’s variance under the shuffle and uniform distributions. A change of schedule expresses its second moment as the trace of a matrix-averaging operator. We decompose the matrix space into four subspaces preserved by relabeling and compute the eigenvalue on each. The resulting variance estimate, together with Chebyshev’s inequality, gives the matching lower bound.

Related work

Morris [14 Section 3.1] introduced the collision/Monte framework and developed entropy methods for shuffles built from fair identity/transposition choices. A fair switch on positions $x,y$ is

Each occurrence uses a fresh, independent private bit. A step applies one candidate switch; a round applies a complete layer of disjoint switches.

We review Monte shuffles and random-transposition shuffles below. Table 1 summarizes their definitions and mixing bounds.

Name	Definition	Mixing time	References
Thorp shuffle	$T_i=\{\{x,y\}:x\oplus y=e_i\ \bmod\ell\}$<br>apply $\prod_{\{x,y\}\in T_i} C^{b}(x,y)$	$O_{\varepsilon}(\log^{3} n)$ rounds<br>$\Theta_{\varepsilon}(\log n)$ rounds	[15]<br>[19]
Swap-or-Not	$\boxed{K_i}\mathrel{\overset{\$}{\leftarrow}}\mathbb{F}_2^{\ell}$<br>$T_i=\{\{x,y\}:x\oplus y=K_i\}$<br>apply $\prod_{\{x,y\}\in T_i} C^{b}(x,y)$ | $O_{\varepsilon,\alpha}(\log n)^{\dagger}$ rounds | [9]
Sometimes-Recurse	For $i=\ell,\ldots,1$, run $r$ rounds of<br>Swap-or-Not on the first $2^i$ positions	$r=O_{\varepsilon}(\log n)$<br>$O_{\varepsilon}(n\log n)$ steps total	[17]
Random<br>perfect-matching<br>Monte	$T_i=\{\{x_j,y_j\}\}_{j=1}^{n/2}$ uniform<br>random partition of $[n]$<br>apply $\prod_{\{x,y\}\in T_i} C^{b}(x,y)$	$O_{\varepsilon,\alpha}(\log n)^{\dagger}$ rounds	[3]
Random-pair Monte	$\boxed{x,y}\mathrel{\overset{\$}{\leftarrow}}[n]$<br>apply $C^{b}(x,y)$ | $O_{\varepsilon}(n\log n)^{\ddagger}$ steps<br>$2n\log n+O_{\varepsilon}(n)$ steps | [Ana26]<br>This work
Semi-random<br>transpositions	$\boxed{x_i}\in[n]$ fixed in advance; $y_i\mathrel{\overset{\$}{\leftarrow}}[n]$<br>apply $(x_i\,y_i)$ | $O_{\varepsilon}(n\log n)$ steps | [16]
Random transposition	$x,y\mathrel{\overset{\$}{\leftarrow}}[n]$<br>apply $(x\,y)$ | $\frac{1}{2}n\log n+O_{\varepsilon}(n)$ steps | [5]

The Thorp shuffle. For $n=2^{\ell}$, identify positions with $\mathbb{F}_{2}^{\ell}$ and let $\mathbf{e}_{0},\ldots,\mathbf{e}_{\ell-1}$ be its standard basis. In round $i$, independently apply a fair switch to every unordered pair $\{x,x\oplus\mathbf{e}_{i\bmod\ell}\}$. This is the Thorp shuffle in a rotating coordinate frame. In the equivalent time-invariant description, the deck is cut in half and corresponding cards from the two halves are interleaved in independently chosen random orders [24]. The first polylogarithmic bound on the Thorp shuffle mixing time was Morris’s $O(\log^{44}n)$ estimate on the number of rounds [13], which was subsequently improved to the asymptotically optimal $\Theta(\log n)$ [18, 14, 15, 10, 19].

XOR Swap-Or-Not. Hoang, Morris, and Rogaway [9] introduced the Swap-Or-Not shuffle. In its XOR form, round $i$ samples a public key $K_i\in\mathbb{F}_{2}^{\ell}$ and applies independent fair switches to all pairs $\{x,x\oplus K_i\}$. Conditional on the round keys, their proof bounds convergence in $O(\log n)$ rounds for the joint positions of any prescribed fixed fraction of the cards, not a total variation bound for the full permutation. Dai, Hoang, and Tessaro [4] obtain tighter Swap-Or-Not bounds using the chi-squared method. Jho and Lee [11] generalize Swap-Or-Not by replacing the XOR pairings with keyed partitions, reducing the round count for the same fractional-deck guarantee.

Ristenpart and Yilek’s Mix-and-Cut shuffle [20] obtains full-permutation statistical security by recursively randomizing the partition of a deck into two halves. For $n=2^{\ell}$, their construction applies $r$ rounds of Swap-Or-Not to each block, cuts it in half, and independently shuffles the two halves by the same procedure. For fixed error, their analysis gives $O_{\varepsilon}(\log^{2}n)$ layers and a total of $O_{\varepsilon}(n\log^{2}n)$ switches.

Morris and Rogaway’s Sometimes-Recurse shuffle [17] recurses on only one half after each Swap-Or-Not stage. With independent randomness at each stage, it is a Monte shuffle whose public schedule consists of matching layers on successively smaller subdecks. Their recursive argument, combined with the Swap-Or-Not bound on the partial deck mixing, gives full-permutation conditional TV mixing in $O_{\varepsilon}(n\log n)$ switches and $O_{\varepsilon}(\log^{2}n)$ layers.

Random matching layers. One can construct a switching network by sampling a uniform perfect matching in each round. Czumaj [3] proves that perfect-matching networks mix any prescribed fixed fraction of the cards in $O(\log n)$ layers with probability $1-O(n^{-2})$ over the choice of the network. The same work gives a separate explicit full-permutation network with $O(n\log n)$ switches and $O(\log^2 n)$ depth.

The iid random-pair upper bound. In the work closest to ours, Anari [Ana26] proves multiplicative pointwise near-uniformity for a random-pair Monte shuffle, with high probability over the public schedule, in $O(n\log n)$ steps. We obtain the sharp leading constant for conditional TV mixing and a matching lower bound. Our multiplicative pointwise guarantee uses $4n\log n+O(n)$ steps, twice the leading count for conditional total variation.

Czumaj and Lingas [2] show by a counting argument that $m=\Omega(n\log n)$ independent uniform distinct-pair interactions have dependency depth $\Theta(m/n)$ in expectation and with high probability. We apply this result in § 3.

Random transpositions. The random transposition shuffle samples $x,y$ independently and uniformly from $[n]$ and applies $(xy)$. Diaconis and Shahshahani [5] proved the sharp total-variation upper bound of $\frac{1}{2}n\log n+O_{\varepsilon}(n)$ steps for each fixed error $0<\varepsilon<1$. Saloff-Coste and Zúñiga [22] refined the classical $L^2$ estimates with explicit constants in discrete and continuous time; we use their continuous-time bound in spectral form (Proposition 2.2).

A matching lower bound follows by tracking the number of untouched cards, known as the coupon-collector problem. In a series of works, this lower bound was shown to be optimal in several senses: by White for convergence in separation distance [25], by Teyssier through an exact total-variation cutoff profile [23], and by Jain and Sawhney [12], who proved that the walk is asymptotically uniform at the first time every card has been touched.

Semi-random transpositions. Fix a sequence of positions $x_1,x_2,\ldots$ before execution. At step $i$, sample $y_i$ uniformly from $[n]$ and apply $(x_i y_i)$. Mossel, Peres, and Sinclair [16] proved an $O_{\varepsilon}(n\log n)$ mixing bound uniformly over the fixed sequence. Saloff-Coste and Zúñiga [21] and, independently, Ganapathy [7] sharpened this to $n\log n+O_{\varepsilon}(n)$, with the leading constant optimal over all fixed endpoint sequences, as witnessed by the star-transposition shuffle.

Upper and matching lower bounds for conditional mixing

We first prove the upper bound by comparing two executions with a common schedule. We then construct a test function for the lower bound and estimate its first two moments.

The shared-schedule collision identity

Let $P$ be the classical random-transposition kernel: independently sample $x,y$ uniformly from $[n]$ and apply $(xy)$, including the identity when $x=y$. Our schedule-averaged kernel is its $1/2$-lazification,

Write $q_m=\mathcal{L}(\pi_m(T,\mathcal{B}))=\mathbb{E}_{T}\Pi_T$ for its $m$-step distribution from id. Define the expected conditional chi-square error and the pointwise relative error of the schedule-averaged distribution by

Note that $\eta_m$ concerns the averaged distribution $q_m$. The conditional relative error $d_\infty(\Pi_T,U_n)$ is a different quantity, which we bound in Proposition 2.3.

The collision identity explains the additional factor of two relative to the ordinary lazy random-transposition shuffle. Since $Q$ is symmetric, the ordinary chi-square error satisfies

whereas the expected conditional chi-square error is $X_n(m)=n!q_m(\operatorname{id})-1$ by (2.1). Thus a chi-square bound for the ordinary lazy walk gives the same bound on the expected conditional error at twice the time. This explains the additional factor of two in our upper bound, beyond the slowdown from laziness. The matching lower bound shows that this additional factor is also necessary for conditional TV mixing. The next subsection obtains the required return-probability bound from the $L^2$ estimate of Saloff-Coste and Zúñiga [22].

Conditional mixing upper bound

Let $p_0=1,p_1,\ldots,p_{n!-1}$ be the eigenvalues of $P$, counted with multiplicity, with $p_0$ corresponding to constant functions. Proposition 4.6 of Saloff-Coste and Zúñiga [22] gives the following estimate in our normalization:

We use their continuous-time $L^2$ bound only in this spectral form.

For $n\ge10$ and $0<\varepsilon\le1/2$, a sufficient number of sampled steps for joint error at most $\varepsilon$ is

We can also bound the probability of a bad schedule. Since $\Delta(\mathsf{T})^2\le\frac{1}{4}\chi^2(\Pi_{\mathsf{T}}\Vert U_n)$,

Consequently, for $n\ge10$, $0<\varepsilon\le1/2$, and $0<\delta<1$, a sufficient number of sampled steps for this probability to be at most $\delta$ is

We next obtain a pointwise bound conditional on the schedule. The argument uses two independent blocks of the shuffle. Write

This is a schedule-dependent bound, unlike in $\eta_m=d_\infty(q_m,U_n)$.

Proof. For any two probability distributions $\mu,\nu$ on $S_n$, centered convolution and Cauchy–Schwarz give

Split $\mathrm{T}$ into two independent length-$m$ schedules $\mathrm{T}^{(1)},\mathrm{T}^{(2)}$. Conditional on these schedules, $\Pi_{\mathrm{T}}=\Pi_{\mathrm{T}^{(2)}}*\Pi_{\mathrm{T}^{(1)}}$, so

Taking $c=4+\log(1/(\varepsilon\delta))$ and applying Markov’s inequality proves (16).

Thus $4n\log n+O_{\varepsilon,\delta}(n)$ steps suffice for fixed $\varepsilon,\delta$. This is the conditional pointwise guarantee studied by Anari [Ana26], with an explicit sufficient constant.

A schedule-dependent distinguisher

Counting possible outputs gives the lower bound $2^m\ge(1-\varepsilon)n!$, whose leading term is $(n\log n)/\log2$, which falls short of the goal of proving the tightness of the constant 2. We instead use a test function that combines the biases in the destinations of all cards, conditional on the schedule.

For a schedule prefix $\mathrm{T}_t$, let

The probability is over $b_1,\ldots,b_t$, with the schedule fixed. Thus column $i$ is the distribution of the position of card $i$. Write $M_{\mathrm{T}}=M_{\mathrm{T}_m}$ for the final matrix. To measure its deviation from uniform, subtract the matrix $J$ whose entries are all $1/n$:

The rows and columns of $C_{\mathrm{T}}$ sum to zero. The squared Frobenius norm $\lVert C_{\mathrm{T}}\rVert_{\mathrm{F}}^2=\sum_{i,j}C_{\mathrm{T}}(j,i)^2$ measures the total squared single-card destination bias.

Given the schedule and a candidate permutation $\sigma$, consider the test function

Equivalently, $F(\mathrm{T},\sigma)=\sum_i C_{\mathrm{T}}(\sigma(i),i)$. The quantity $F(\mathrm{T},\sigma)+1$ is the expected number of cardwise agreements between $\sigma$ and an independent execution of the same schedule.

We will distinguish the two distributions by thresholding $F$ in the proof of Theorem 2.8. Let $R$ denote the joint distribution of the schedule and realized permutation, $(\mathrm{T},\pi_m(\mathrm{T},B))$, and $I$ the distribution of $(\mathrm{T},\sigma)$ with $\sigma\sim U_n$ independent of $\mathrm{T}$. By (3), $d_n(m)=\lVert R-I\rVert_{\mathrm{TV}}$.

Throughout the lower-bound proof, assume $n\ge4$ and let

Proof. For $\tau=(u\ v)$ obtained from independent uniform endpoints $u,v\in[n]$, set

A fair switch averages the probabilities at its two positions. Thus, if $p$ is a card’s position-probability column vector before the switch, it becomes $P_\tau p$ afterward: the entries at $u$ and $v$ are both $(p_u+p_v)/2$, and the others are unchanged. When $u=v$, $J_\tau=0$ and $P_\tau=I$.

Since card $i$ starts at position $i$, its initial distribution is $\mathbf{e}_i$. Applying the updates to all columns gives

Coordinate averaging fixes $J$ on both sides. Thus the centered matrices satisfy

Here and below, $\mathbb{E}_\tau$ uses this endpoint-sampling distribution, including $\tau=\mathrm{id}$ with probability $1/n$. Averaging gives

Since $JC_{T_{t-1}}=0$, symmetry and idempotence of $P_{\tau_t}$ imply

Starting from $\left\|I-J\right\|_{\mathrm{F}}^2=n-1$, iteration yields

Under the actual shuffle, $\mathbb{P}\{\pi_m(i)=j\mid T\}=M_T(j,i)$, with probability over $B\mathrel{\overset{\$}{\leftarrow}}\{0,1\}^m$. Hence

Since $\sum_{i,j}M_T(j,i)=n$, the last expression equals $\sum_{i,j}(M_T(j,i)-1/n)^2=\left\|C_T\right\|_{\mathrm{F}}^2$. Averaging over $T$ and applying (2.14) computes the realized mean.

For an independent uniform permutation, the conditional mean is zero because $C_T$ has zero column sums. Expanding the square under a uniform permutation gives

Indeed, the diagonal terms contribute $\left\|C_T\right\|_{\mathrm{F}}^2/n$. The remaining terms contribute $\left\|C_T\right\|_{\mathrm{F}}^2/[n(n-1)]$, using the zero row and column sums and the uniform distribution on distinct images. Averaging over $T$ and using (2.14) completes the proof.

The realized second moment

The mean gap alone is not enough: it could be due to rare large values of $F$. We now estimate the second moment $\mathbb{E}_R F^2=\mathbb{E}_{T,B}[F(T,\pi_m(T,B))^2]$. The next lemma absorbs the realized walk into a change of schedule, leaving an expectation over schedules alone.

Equip $\mathbb{R}^{n\times n}$ with the Frobenius inner product $\langle X,Y\rangle_F=\operatorname{tr}(X^{\mathsf{T}}Y)$. To evaluate the remaining second moment, consider the matrix space and averaging operator

Each update averages two rows and the corresponding columns, preserving $\mathcal{Z}$. By independence of the public pairs, for $X\in\mathcal{Z}$ we have

where the last equality uses $JX=XJ=0$. The operator $X\mapsto C_TXC_T^{\mathsf{T}}$ has trace $(\operatorname{tr}C_T)^2$: its diagonal coefficients in the matrix-unit basis are $C_T(i,i)C_T(j,j)$. Since $C_TJ=JC_T=0$, it vanishes on $\mathcal{Z}^{\perp}$, and its trace on $\mathcal{Z}$ is unchanged. Taking expectations and applying Lemma 2.5 gives

It remains to determine the spectrum of $\mathcal{A}$ on $\mathcal{Z}$.

Proof. Simultaneously relabeling rows and columns gives a representation $\rho$ of $S_n$ on $\mathcal{Z}$:

Let $H = I - J$. The following four subspaces of $\mathcal{Z}$ are preserved by every relabeling, in the order listed in the lemma:

Here $\operatorname{diag}(z)$ is the diagonal matrix with diagonal $z$. These subspaces have the dimensions in the lemma and form a direct sum: split into symmetric and skew-symmetric parts, then use the common and vertex components to match the diagonal, leaving the residual component. Indeed, $(H\operatorname{diag}(z)H)_{ii} = (1 - 2/n)z_i$ for zero-sum $z$.

To justify irreducibility, let $V = \mathbf{1}^{\perp}$ be the standard zero-sum-vector representation. The map $u \otimes v \mapsto uv^{\mathsf{T}}$ identifies its tensor square $V \otimes V$ with $\mathcal{Z}$ and respects relabeling, since $(R_\sigma u)(R_\sigma v)^{\mathsf{T}} = R_\sigma(uv^{\mathsf{T}})R_\sigma^{\mathsf{T}}$. For $n \ge4$, this tensor square has exactly four irreducible summands [6 Exercise 4.19]. Our four nonzero invariant subspaces must therefore each be irreducible: none contains a smaller nonzero subspace preserved by every relabeling.

Let the operator $\mathcal{K}$ be the average over transpositions of distinct labels:

This operator preserves each component and commutes with every relabeling. It is self-adjoint for the Frobenius inner product, so its eigenspaces are also preserved by every relabeling. By Schur’s lemma, $\mathcal{K}$ multiplies each irreducible component $W$ by a scalar. All transpositions have the same trace on $W$, giving that scalar as

Thus only the trace of one transposition on each component is needed.

To relate this relabeling average to our shuffle, observe that $P_\tau= (I + R_\tau)/2$. With independent uniform endpoints,

The identity term in the second formula accounts for equal endpoints. Since $JX = XJ = 0$ for $X \in\mathcal{Z}$, expansion gives

Hence its eigenvalue on $W$ is $(n-1)(3+r_W)/(4n)$.

It remains to compute the four traces and the dimensions of the respective eigenspaces. On the common component the trace is $1$. On the vertex component, relabeling simply permutes $z$, so the trace is $n-3$: a transposition fixes $n-2$ coordinate vectors, and the constant direction contributes $1$.

The symmetric matrices in $\mathcal{Z}$ have basis $J_{(ij)} = \frac{1}{2}(e_i-e_j)(e_i-e_j)^{\mathsf{T}}$, $i<j$, which is permuted by relabeling. The transposition $(1\ 2)$ fixes $\{1,2\}$ and the $\binom{n-2}{2}$ pairs avoiding those labels. Subtracting the common and vertex traces gives the residual trace

On all skew-symmetric matrices, the trace is $\binom{n-2}{2}-1$: the basis matrix on $\{1,2\}$ changes sign, disjoint pairs are fixed, and the other basis matrices are exchanged. This space splits into the skew component of $\mathcal{Z}$ and the matrices $z\mathbf{1}^{\mathsf{T}}-\mathbf{1}z^{\mathsf{T}}$ with $\sum_i z_i=0$. The latter transform as zero-sum vectors and have trace $n-3$. The skew component therefore has trace

Dividing these traces by the dimensions in Equation (23) yields, in order,

Substitution into (2.18) gives the four stated eigenvalues; their multiplicities are the component dimensions.

Proof. By (2.16), we sum the $m$th powers of the eigenvalues in Lemma 2.6, with their multiplicities:

where the last inequality follows from $0\leq\lambda_4=1-2/n\leq(1-1/n)^2=\lambda^2$. Recalling that $\mathbb{E}_{R}F=(n-1)\lambda^m$ (Lemma 2.4), we have

The variance of $F$ under $R$ can also be bounded without determining the full operator spectrum. One approach is to write $F$ as a sum of $n$ random variables using Equation (17) and compute their pairwise covariances. For $m=2n\log n+O(n)$, the total covariance contribution is lower order than the sum of the individual variances. We use the spectral argument because, although less elementary, it makes the structure of the second moment more transparent.

The lower bound and the cutoff window

The moment estimates now give the lower bound by Chebyshev’s inequality.

Proof. Write $s=(n-1)\lambda^m>0$ for the mean under the realized distribution. The ideal mean is zero, so we distinguish the two experiments using $\{F \ge s/2\}$. Chebyshev’s inequality, Lemma 2.4, and Proposition 2.7 give

Taking the positive part is valid because TV distance is nonnegative.

Proof of Theorem 1.1. Write $c=m/n-2\log n$. Suppose first that $c<0$, and put $\rho_m=((n-1)^2\lambda^m)^{-1}$. Convexity gives $\lambda_2\le\lambda^{3/2}$, so Theorem 2.8 yields

Using $-\log\lambda\le1/n+1/[2n(n-1)]$ and $\log(n/(n-1))\le1/(n-1)$, we obtain

Set $z=e^{c/2}$. If $z\ge1/8$, (1.5) is trivial. Otherwise,

proving the left-hand bound.

If $c\ge4$, Proposition 2.2 gives $d_n(m)\le(e^2/2)e^{-c/2}\le8e^{-c/2}$. For $0<c<4$, the same bound follows from $d_n(m)\le1<8e^{-c/2}$. This proves (1.6). Finally, monotonicity of $d_n$ and these two bounds place each fixed-error mixing time within $O_\varepsilon(n)$ of $2n\log n$, proving (1.4).

The test function can be computed from the schedule and the candidate permutation. Starting from the identity matrix, form $M_T$ by averaging the corresponding rows, and then evaluate (2.11), aggregating single-card biases across the entire deck.

A shallow public switching network

We now apply the mixing bound to parallel switching networks. Sample a schedule of a Monte shuffle. Form a directed dependency graph where two switches are connected if they share an endpoint; the arc goes in the direction of their order in the schedule. Switches that are not logically dependent can be executed in parallel.

Write $H_m$ for the number of parallel layers, equivalently the maximum number of switches on a directed dependency path. This is a random variable determined by the public schedule. Czumaj and Lingas [2] show that for $m = \Omega(n \log n)$ independent uniform distinct-pair interactions, the depth is $O(m/n)$ in expectation and with high probability. Their path-counting estimate supplies the constants below. It also applies to our with-replacement schedule: replacing every public null step by a fresh uniform distinct pair gives their model, and deleting those replacements cannot increase depth.

Proof. Equation (13) bounds the mixing failure probability by $\delta/2$. To complete the union bound, let $k$ be the ceiling in (29). The path-counting estimate of Czumaj and Lingas [2 Section 4], with $k! \ge(k/e)^k$, gives

References