% Coordinate sweeps and the Thorp shuffle: a clear and complete proof
% that Theta(log N) physical shuffles mix N = 2^d cards.
%
% This document is self-contained. It proves one theorem:
% the Thorp shuffle on 2^d labeled cards mixes to the uniform
% permutation in O(d) physical shuffles, and Omega(d) are necessary.
%
% Structure:
% Part 1 What is the problem
% Part 2 Notation and the standard tools we use
% Part 3 A dimension lower bound
% Part 4 The overlap theorem (the technical heart)
% Part 5 From overlap to a row-column Fourier estimate
% Part 6 Schatten interpolation
% Part 7 The sparse shapes
% Part 8 The induction that proves the main moment bound
% Part 9 From the moment bound to mixing
% Part 10 The matching lower bound
%
% Everything below is written so that a reader who is willing to accept
% the "toolkit" of Part 2 can follow every step. The toolkit is standard
% representation theory of the symmetric group; each item is stated as a
% precise, usable fact, with a reference.
allowdisplaybreaks[1]
# Row--column symmetry and contraction of coordinate sweeps
large a clear and complete account
maketitle
Abstract:
The Thorp shuffle on N=2^d labeled cards mixes the full permutation to
uniform in Θ(log N) physical shuffles. The upper bound uses an
absolute number of coordinate sweeps (each sweep = d physical
shuffles). This document gives the complete proof, following the
weighted-contraction route. Everything the proof uses from representation
theory is collected in Part~part:toolkit as a precise, quotable list.
tableofcontents
%=========================================================================
part{What is the problem}
%=========================================================================
# The shuffle, in plain words
Take a deck of N=2^d cards. Label the d positions of a card by bits
x=(x_1,...,x_d)inF_2^d. One physical Thorp shuffle
does the following.
Deal the deck into the N/2 unordered pairs of positions that differ
only in the first bit, and in each pair independently swap the two
cards with probability 1/2. (This is a "riffle" along the first
coordinate: it is the classical Thorp move.)
Rotate the d coordinates cyclically, so that the next shuffle
riffles along what was the second coordinate.
In coordinates a physical shuffle sends (x_1,u)|->(u,x_1+xi_u),
where u=(x_2,...,x_d) and the bits xi_u are independent and fair.
After d physical shuffles the
rotation has come back to the identity, so d physical shuffles are the
same as the same matching applied independently along each of the
d coordinate directions, once. We call that object a
coordinate sweep.
A single card is already uniform after one sweep (it has been swapped
according to d independent fair coins). The subtlety is that the
joint law of all the cards is not uniform: the cards have used the
same switches, so they are correlated. The theorem says that an
absolute constant number of sweeps (i.e. O(d) physical shuffles)
destroys every trace of this correlation, measured in total variation
distance from the uniform permutation.
# Statement of the theorem
Let S_N be the symmetric group. A permutation gin S_N acts on
positions, and the product gh means "apply h first, then g".
Let q_d be the law of one physical shuffle; it is a probability measure
on S_N. Then K_d=q_d^{*d}, the law of one coordinate sweep, is the
d-fold convolution. We write K_d(lambda) for the expectation of the
representing matrix rho_lambda(g) of the irreducible unitary
representation labelled by the partition lambda⊢ N:
K_d(lambda)=sum_{gin S_N} K_d(g),rho_lambda(g).
Write D_lambda=dimrho_lambda. Because one matching layer averages
the (self-adjoint unitary) action of a product of disjoint transpositions,
its Fourier matrix is an orthogonal projection; therefore every
K_d(lambda) is a contraction.
[Main; weighted sweep moments]
There exist positive weights W_lambda (one per partition
lambda⊢ 2^d) and an absolute constant p_*<∞ such that, for
every dge1 and every lambda⊢ 2^d,
D_lambda^{3/4} le W_lambda le D_lambda,
W_lambda,|K_d(lambda)|_{p_d}^{p_d}le 1
quadfor some 2le p_dle p_*.
Consequently |K_d(lambda)|_{op}le D_lambda^{-3/(4p_*)}, and there
is an absolute q=4p_*/3<∞ with the unweighted bound
D_lambda|K_d(lambda)|_q^qle1.
[Optimal order of mixing]
Let t_{rm mix}(d) be the least number of physical shuffles after which
the distance from uniform is at most 1/4, uniformly over the starting
deck, and put N=2^d. There is an absolute constant C with
[
Biglceil(2)/(N)log_2(3N!)/(4)Bigrceil
le t_{rm mix}(d) le C,d .
]
In particular t_{rm mix}(d)=Θ(log N).
The upper bound is the hard direction and occupies Parts
part:dim--part:moment, part:mixing. The lower bound is
Part~part:lower.
# The plan, in plain words
Split the d coordinate directions into two blocks of approx d/2 each.
The positions become a rectangular board of m rows by n columns
(mn=N). The first block of directions shuffles within rows; the
second shuffles within columns. Each block is itself a collection of
smaller, independent coordinate sweeps (one independent copy inside each
row, and one inside each column).
Induction on d. Suppose we already understand the two smaller
sweeps on the row group and the column group. The full sweep is the
product of the row part and the column part. In any irreducible
representation V_lambda, the operator norm of a product is not simply
the product of the norms; the overlap between the row decomposition and
the column decomposition gets in the way. Part~part:overlap is
exactly the estimate of this overlap: how much of a vector that lives in
a single row-type can survive projection onto a single column-type inside
V_lambda.
The key engineering idea is the weight W_lambda. It is a number
between D_lambda^{3/4} and D_lambda, built so that the ratio
W_lambda/(W_mu W_nu) exactly pays for the overlap cost of going from
a row-type mu and a column-type nu up to lambda. This is what
makes the induction close with a bounded Schatten exponent
p_dle p_*, independent of d.
Three independent ways to prove the overlap estimate are known. This
document gives one of them completely: the weighted contraction
route, whose overlap estimate (Theorem~thm:occupied) is an inequality
about a board with deleted cells. It is the most self-contained. The other
two routes ("deletion frames" and "coherent states") prove the same kind
of bound by other techniques; we mention them in
Remarks~rem:frames--rem:coherent but do not develop them,
in order to keep this account short enough to actually read.
%=========================================================================
part{Notation and the standard tools we use}
%=========================================================================
# Conventions
All vector spaces are over C and all representations are unitary.
For a partition lambda of N (a Young diagram with N boxes) let
V_lambda be the irreducible S_N-representation and
D_lambda=dim V_lambda. On a product of groups, mu,nu,...
denote tuples of partitions and V_mu,D_mu are the tensor products and
products of dimensions. Traces on a single matrix space are
unnormalised; Schatten norms are
|A|_p^p=Tr(|A|^p) for 2le p<∞ and |A|_∞ is the
operator norm. All logarithms in estimates are natural; we write
flesssim g or f=O(g) when fle Cg for an absolute constant C,
and constants are relabelled freely.
We use the symmetric group S_L of degree L and allow L=0 (the
trivial group) and the empty partition (dimension 1). Box coordinates
are (i,j) with i the row and j the column; the width of
lambda is lambda_1 and k:=N-lambda_1 counts the boxes below the
first row.
# The toolkit
These are the classical facts used in the proof. Each is precise and ready
to quote.
[(T1)] Regard irreducibles on subgroups. Restricting V_lambda
to a Young subgroup S_{L_1}times...times S_{L_r} decomposes into
tensor products V_{lambda^{(1)}} ⊗ ... ⊗ V_{lambda^{(r)}},
with the lambda^{(i)} running over all tuples with
|lambda^{(1)}|+...+|lambda^{(r)}|=N and a nonnegative integer
multiplicity (the Littlewood--Richardson coefficient). In particular
restriction to S_{N-1 is "delete one box"}: V_lambda
restricted to S_{N-1} is the direct sum of V_{lambda^-} over all
ways to remove a corner box. (Branching; see Sagan 2001, Thm 2.8.3,
or James 1978.)
[(T2)] Two subgroups at once. If V_sigma is an irreducible of
S_{m} and V_tau of S_{n}, then
Ind_{S_mtimes S_n}^{S_{m+n}}(V_sigma ⊗ V_tau) contains
V_chi with multiplicity given by the Littlewood--Richardson
coefficient for the skew shape chi/sigma filled by the content of
tau. (Littlewood--Richardson; James 1978, Thm 16.4.)
[(T3)] Pieri's rule. Induction of a single row (or single
column) adds boxes to the first (or first column) subject to the diagram
staying a partition. (Stanley EC2, Thm 7.15.7.)
[(T4)] Hook-length formula, with the correction we keep. For
lambda⊢ L,
D_lambda=L!/prod_{boxes}hook(b). If lambda is the
diagram alpha decorated by a single extra long top row of length
L-|alpha|, the ratio of the top-row factorial to the hooks it creates
is at least binom{L}{|alpha|}exp(-|alpha|/(L-|alpha|+1)), obtained
by comparing the top-row part with binom{L}{|alpha|} and bounding the
hook perturbation in the first row. We use this repeatedly. (Sagan
2001, Thm 3.10.2.)
[(T5)] Ordinary Schur--Weyl duality. On the tensor power
(C^h)^{ ⊗ L} the groups U(h) and S_L act and commute,
and
(C^h)^{ ⊗ L}~=⊕_{gamma⊢ L, ell(gamma)le h}
W_gamma ⊗ V_gamma with W_gamma the polynomial
U(h)-representation of highest weight gamma. A positive matrix P
acting identically on all L factors has, on the U(h)-type gamma,
largest eigenvalue given by the highest-weight monomial
prod_i x_i^{gamma_i} in the eigenvalues of P sorted decreasingly;
this is also a lower bound for Tr(P^gamma). (Etingof et al.,
Thm 4.57 and Cor 4.59; Schur characters in Stanley EC2 Thm 7.10.3.)
[(T6)] Signed tensor space (C^h ⊕ C^h)^{ ⊗ s}
(the "even" block and the "odd" block). The group S_s acts by
permuting factors and inserting a sign equal to the sign of the
reordering of the odd factors. This S_s-action commutes with a diagonal
U(h)times U(h) action, one U(h) per block. Fixing the number s_e of
even slots and s_o of odd, a U(h)times U(h)-sector with top weights
(gamma,xi) has multiplicity space, as an S_s-representation,
Ind_{S_{s_e}times S_{s_o}}^{S_s}(V_gamma ⊗ V_{xi^{rm tr}}),
where xi^{rm tr} means the transpose because the odd block contributes
a sign. This is the standard "sign twist and induction" combination.
(Etingof et al., with James 1978 Thm 6.7 for the sign and Thm 16.4
for the induction.)
[(T7)] Group-algebra matrix actions. Given a matrix M on an
irreducible V_mu of a subgroup R⊆ S_N, form the element of
CR with matrices M on the V_mu-block and 0 elsewhere.
Viewed in any larger representation, its restriction to R acts as
"the chosen matrix on one copy of the carrier, and identity on every
multiplicity copy". Its coefficient at gin R is
(D_mu)/(|R|)Tr(Mrho_mu(g^{-1})). (Orthogonality and
Plancherel; Etingof et al.) We call this a matrix action
supported on mu. When M is the rank-one projector onto a unit
vector e, it is an orthogonal projection on the R-part and is written
P_{mu,e}; it uses one direction of the carrier and is the identity on
multiplicity copies.
[(T8)] Cauchy--Schwarz for sums of projections. When a positive
operator is a sum of orthogonal projections onto orthogonal subspaces,
comparison between two such decompositions is controlled by
Cauchy--Schwarz, and nonnegativity of each irreducible's contribution
lets one take traces representation by representation. We use this
without further comment.
[(T9)] Entropy of an occupation law. For a probability vector
(omega_{ij}) supported on the cells of a board and marginals
(p_i),(q_j), the relative entropy of omega from the product
(p_iq_j) is at most log(mn/s) when omega is uniform on s
occupied cells of an mtimes n board. (Standard; the argument is
the entropy/subadditivity duality of Carlen--Cordero-Erausquin 2009,
Thm 2.1.)
[(T10)] Interpolation of a bilinear Schatten map. If a bilinear
map has norm le e^{E/2} at the 2-Schatten endpoint and le1 at the
operator-norm endpoint, then it has norm le e^{E/p} at the
p-Schatten norm for 2le p<∞, with E independent of p.
(Complex interpolation of Schatten classes / three-lines; see the
computation in Part~part:interp. We spell it out.)
%=========================================================================
part{A dimension lower bound}
%=========================================================================
# Every nontrivial type that survives is large
One matching layer kills every partition of length >N/2: averaging a
swap along one coordinate projects onto the invariants of a Young subgroup
S_2^{N/2}, and only partitions of length le N/2 survive. So we only
need to bound types lambda with at most N/2 rows. Below, k=N-lambda_1
is the number of boxes below the first row.
[Dimension away from the first row]
There is an absolute c>0 such that, for every Nge2 and every
nontrivial partition lambda⊢ N with at most N/2 rows,
[
log D_lambda ge c,k, k=N-lambda_1.
]
Proof.
If both width and height are <N/10, every hook length is le N/5, so
the hook formula gives log D_lambdage cNge ck.
Otherwise pass to lambda or its transpose so the first row has length
uge N/10; let v=N-u be the remaining boxes. Keep that whole first
row and a subdiagram of size ell=min(v,floor( u/2)) below it.
By branching (T1) D_lambda is at least the dimension of that
subdiagram. For a diagram with first row u and any fixed lower part of
size ell, the hook formula plus (T4) bounds
[
D_lambda ge binom{u+ell}{ell},exp!Big(-(ell)/(u-ell+1)Big).
]
The lower part has width leell, so it adds at most ell to each top-row
hook; the correction is the displayed exponential. In the original case
ellge c_1 k (large N); in the transpose case the height hypothesis
gives vge N/2ge k, so again ellge c_1 k. With ellle u/2 the
logarithm is ge(log3-1)ellge c_2 k. Finite small N are covered by
decreasing c; the only one-dimensional irreducibles are trivial and
sign, both excluded here.
In particular, if k>N^{1-eps} for a small fixed eps>0 then
log D_lambda ge c_0,N^{1-eps}.
%=========================================================================
part{The overlap theorem}
%=========================================================================
# A board with deleted cells
This is the technical heart. Picture an mtimes n board, mn=N. Colour
some cells occupied (there are s of them) and the rest
deleted (there are t=N-s). Put the symmetric group G_s on the
occupied cells. Restricting a representation V_a of G_s to the
within-row group S_{n}^m, and also to the within-column group S_m^n,
gives two decompositions that do not commute. The theorem bounds how a
row-type direction and a column-type direction can overlap.
[Overlap on an arbitrary occupied board]
Let a⊢ s be a partition lying in the (h,h)-hook, i.e. no box of
a has both row index and column index greater than h; here 1le hle N.
Decompose V_a under the row group and, separately, under the column
group. For row-types sigma (a tuple of partitions) and column-types
theta, let I_{sigma,u}colon V_sigmato V_a and
I_{theta,v}colon V_thetato V_a be isometries onto orthogonal copies,
over all copies u and v, chosen so that their images span the
corresponding isotypic parts. Then
sum_{u,v}|I_{sigma,u}^* I_{theta,v}|_{op}^2
le exp!big{C[(m+n+1)h^2log(N+2)+t]big},
minBig{1, (D_sigma D_theta)/(D_a)Big}.
Here C is absolute. When s=0 the empty representation has dimension 1.
In plain words. The overlaps between the two decompositions are
tiny: the total squared overlap is bounded by an explicit factor (the
exponential) times the "quantum" ratio D_sigma D_theta/D_a, never
more than 1. The exponential depends on the hook width h and on the
number t of deleted cells, which is exactly the cost of having a
non-rectangular occupied region.
Proof. [Proof of Theorem~thm:occupied]
For s=0 there is nothing to prove. Throughout we use the signed tensor
space L=( C^hbbC^h ⊕ C^h)^{ ⊗ s} and the
signed S_s-action (T6).
smallskipnoindentRealisation.
By (T5)--(T7) the standard signed realization carries V_a inside
L; concretely, at fixed parity counts s_e,s_o and sector top
weights (gamma,xi) (both of length le h, degrees s_e,s_o), the
sector's multiplicity space is Ind_{S_{s_e}times S_{s_o}}^{S_s}(V_gamma ⊗
V_{xi^{rm tr}}). There is a sector containing V_a: take gamma as the
first h rows of a and xi^{rm tr} as the rest (a diagram of width
le h), so that the relevant Littlewood--Richardson coefficient is
positive. This sector is the arena for the rest of the proof.
smallskipnoindentSize and entropy of sectors.
The dimensions of the U(h)times U(h) carriers, and the number of
sectors, are at most exp(O(h^2log(N+2))) (count symbol occupations row
by row in a semistandard tableau). The multiplicity of any S_s-type
chi in the signed action is also leexp(O(h^2log(N+2))): given
(gamma,xi) contributing to chi, the skew shape chi/xi^{rm tr}
has content gamma and its part in the first h columns has at most
h^2 boxes, beyond which columns are determined. Hence (with
u=|gamma|+|xi|)
D_chi le exp(H(gamma,xi)) le D_chiexp(O(h^2log(N+2))),
H(gamma,xi)=sum_igamma_ilog(u/gamma_i)+sum_jxi_jlog(u/xi_j).
The first inequality is D_chilebinom{u}{|gamma|}D_gamma D_xi (from
T2 and transposition-invariance of dimension) with multinomial bounds; the
second is (T4) applied to the hooks in the first h rows and columns
together with |gammacapxi^{rm tr}|le h^2.
smallskipnoindentTurning overlap into a trace.
Let P_sigma,P_theta be the row- and column-isotypic projections inside
V_a, and expand the embeddings: the sum of squared Hilbert--Schmidt norms
sum_{u,v}|I_{sigma,u}^*I_{theta,v}|_2^2=Tr_{V_a}(P_sigma P_theta),
which dominates the required sum of squared operator norms. Lift to a
sector projector P of L and subgroup isotypic projectors
Q_sigma,Q_theta. Since P commutes with the signed permutations and
each irreducible contributes nonnegatively,
[
Tr_{V_a}(P_sigma P_theta) le Tr_{L} P Q_theta P).
]
smallskipnoindentMajorising by product states.
We bound Q_sigma in the positive semidefinite order by a probability
mixture of tensor products S=⊗_{cells} S_i, with the same
even state S_i in every cell of row i. The prefactor is
D_sigmaexp(Cm,h^2log(N+2)). On one row of length l, bound the
projection for a partition chi by the sum over compatible sector top
weights (gamma_0,xi_0); in each sector, average by
U(h)times U(h) the identical-cell product of the diagonal state with
entries (gamma_{0,i}/l,xi_{0,j}/l). After averaging this product acts
as a scalar geexp(-H(gamma_0,xi_0))/dim(carrier) on that
sector (highest-weight eigenvalue via T5), and the dimensions are folded
into the prefactor. Do the same for Q_theta with column states T_j and
prefactor D_thetaexp(Cn,h^2log(N+2)). Positivity then reduces us to
bounding Tr_{L} P T P).
smallskipnoindentThe quarter-root filter.
Two normalisations are needed at once: the global sector must pay
exp(-H(gamma,xi)) in the squared norm, and the per-cell overlaps must
average to le1 under the row- and column-marginals. Let barbar S,S,barbar TT
be the average cell-states over the s occupied cells, put
X=barbar S^S^{1/2}, Y=barbar T^T^{1/2}, and set
S_i'=X^{-1/2}S_iX^{-1/2}, T_j'=Y^{-1/2}T_jY^{-1/2} (inverses on
supports). With L=(X^{1/2})^{ ⊗ s}P(Y^{1/2})^{ ⊗ s} we have
Tr_{L}|(S')^{1/2}L(T')^{1/2}|_2^2. The matrix L acts
on the sector with operator norm leexp(-H(gamma,xi)/2): indeed
(X^{1/2})^{ ⊗ s}=(barbar S^S^{1/4})^{ ⊗ s} has norm
leexp(-H(gamma,xi)/4) on that sector by the largest-weight monomial
in the eigenvalues of barbar SS (whose sum is 1); the same for barbar T.T.
By matrix-coefficient orthogonality for the block-unitary group, L is an
integral of U^{ ⊗ s} over block unitaries with total coefficient
le exp(-H(gamma,xi)/2)·(squared carrier dimension).
smallskipnoindentThe cell product and an entropy bound.
For a block unitary U let z_{ij}=Tr(S_i'UT_j'U^*)ge0. The weighted
squared Hilbert--Schmidt norm of U^{ ⊗ s} on the occupied cells is
prod_{cells}z_{ij}. Under the product of row-marginals p_i and
column-marginals q_j (uniform occupation of the s cells), the mean is
Tr(barbar S^S^{1/2}Ubarbar T^T^{1/2}U^*)le1 by Cauchy--Schwarz. So the
omega-average of log z_{ij} is at most the relative entropy of the
occupation law omega from p_iq_j, which is lelog(mn/s)lelog(N/s)
(T9). Hence prod z_{ij}leexp(slog(N/s))leexp(t). Inserting the
integral for L and the triangle inequality,
[
Tr_{L} le exp{C h^2log(N+2)+t},exp(-H(gamma,xi)),
]
and D_aleexp(H(gamma,xi)) by (eq:sector-entropy). Multiplying by
the mixture prefactors D_sigma D_theta and dividing by D_a gives
(eq:occupied), with min{1,D_sigma D_theta/D_a} recording that
the overlap can never exceed 1.
A second, independent proof of an overlap bound uses deletion frames:
resolve a row-type vector by remembering only t marked positions per row,
control the resulting marked kernels with a Schatten-8 estimate, and use
a signed-tensor Schatten-2 estimate for the complementary shapes. It gives
a uniform Schatten exponent without weights.
A third proof, on coherent states, keeps the deleted positions as an
ordered list and compares row and column projections by averaging
highest-weight coherent vectors and matching their one-cell densities by a
minimum-norm (Kempf--Ness type) argument. It yields an explicit restoration
factor e^{3t}binom{N}{t}. These routes are not needed below.
%=========================================================================
part{From overlap to the row-column Fourier estimate}
%=========================================================================
# The weighted overlap
Now fix the split of the sweep. Write N=2^d as mn with m,n both of
order sqrt N (they are the sizes of a column and a row for a balanced
split of the d bits). The row part acts within rows, the column part
within columns; both are products of smaller independent sweeps.
We assume for the estimate that the current lambda is not sparse, in the
sense
k=N-lambda_1>N^{1-eps}, lambda^{rm tr}_1le N/2,
with the small eps of (eq:dim-large); the sparse range is handled
in Part~part:sparse. The weights W_lambda are built in
(eq:Jdef) below; for the moment only their two properties matter,
D_lambda^{3/4}le W_lambdale D_lambda, and the exact minimisation
formula (eq:Jdef).
[Weighted overlap]
Under (eq:not-sparse), for irreducibles mu of the row group and
nu of the column group and unit carrier vectors e,f,
W_lambda,Tr_{V_lambda}(P_{mu,e}P_{nu,f})
le W_mu W_nu,exp!big{O((log D_lambda)/d)big},
with an absolute implied constant independent of the types and of d.
The proof needs the weight formula, so we state it now.
# The weights
The weight is a small ``tax'' on each diagram designed so that the tax of
a parent equals the tax of its children plus exactly enough to pay
for restoring deleted cells. Fix absolute constants
[
b_0=tfrac14, delta=tfrac1{16}, b_1=(b_0delta)/(4),
A=10, eta=(b_1)/(2A), eps=(eta)/(8),
]
and the penalty function
[
F_L(r)=rmin{log(L/r), etalog L}(1le rle L), F_L(0)=0.
]
For a diagram lambda⊢ L and a subdiagram a⊆lambda
(itself a Young diagram) let r=L-|a| and define
J(lambda)=min_{a⊆lambda}big{b_0log D_a+b_1 rlog L-AF_L(r)big},
W_lambda=D_lambda,e^{-J(lambda)}.
Empty diagrams have J=0, W=1. Since AF_L(r)le(b_1)/(2)rlog L,
the minimised expression is nonnegative, and a=lambda shows
0le J(lambda)letfrac14log D_lambda; hence
D_lambda^{3/4} le W_lambda le D_lambda.
On tuples (product groups) J is summed and W multiplied.
The point of J is this trimming lemma: the minimising a can be
taken inside the (h,h)-hook, h=floor( N^delta), at additive
cost O(h^2) in the minimum of (eq:Jdef). Indeed, trimming the boxes
with both indices >h from any minimiser a_1 to get a changes
log D_{a_1}-log D_a by at least x(log h-C)-Ch^2 where x is the
number trimmed, while the penalty changes by at most (b_1log N+A)x; as
b_1<b_0delta the trim is favorable. Consequently, taking a in the
hook with t=N-|a|,
b_0log D_a+b_1tlog N-AF_N(t)=J(lambda)+O(h^2),
tlog Nle C(log D_lambda+h^2).
# Proof of the weighted overlap
Proof. [Proof of Proposition~prop:weighted-overlap]
Take the hook subdiagram a from (eq:trim), and choose a diagram
b⊢ t so that V_lambda occurs in
I={G_{N-t}times G_t}^{G_N}(V_a ⊗ V_b) (possible by
branching and decomposing the restriction). The trace on I of
XY, for X=P_{mu,e} and Y=P_{nu,f}, bounds the wanted trace on
V_lambda, since each G_N-type contributes nonnegatively.
smallskipnoindentFibers at deleted sets.
I is a direct sum over the t-sets Z of the board; at Z, the
stabiliser acts as V_a on the complement of Z and V_b on Z. Let
v_i count Z in row i and u_j in column j, and set
[
L_R=prod_ibinom{n}{v_i},
L_C=prod_jbinom{m}{u_j},
L_0=binom{N}{t},
E_0=H_R+H_C-H_0,
]
H_R=sum_i v_ilog(n/v_i), H_C=sum_j u_jlog(m/u_j),
H_0=tlog(N/t) (zero terms are 0). For a nonempty profile E_0ge0 (it
is t times a relative entropy). The layout count is controlled by
logfrac{L_{RC}^2L_0}{L_RL_C} le E_0+O(t),
where L_{RC} is the number of t-sets with the given row- and
column-profiles: log L_Rge H_R, log L_Cge H_C,
log L_0le H_0+t by binomial bounds, and subadditivity of entropy gives
log L_{RC}le E_0+2t (take a uniformly random occupied cell with
independent row index I and column index J, and use
H(Vmid I,J)le H(Vmid I)+H(Vmid J)-H(V)).
smallskipnoindentDiagonal blocks.
The block trace of XY pairs Z,Z' with equal profiles; off-diagonal
blocks are bounded by the geometric mean of diagonal overlaps (Cauchy--
Schwarz for X^{1/2}UX'^{1/2}). For a diagonal block at Z, the row
stabiliser R_Z acts separately off and on Z; if alpha=(sigma,tau)
denotes the two parts, then (T7, orthogonality, |R|=L_R|R_Z|)
[
X_{ZZ}=(D_mu)/(L_R)sum_alpha(1)/(D_alpha)P_{alpha,M_alpha},
]
the M_alphasucceq0 with sum_alphaTr M_alpha=1 obtained by tracing
out the multiplicity space. Similarly Y_{ZZ} with D_nu/L_C and column
stabiliser types zeta=(theta,pi). The only subtlety is that M_alpha
need not be a product of a surviving-cell state and a deleted-cell state;
the next lemma (which needs no independence) removes this worry.
[Arbitrary carrier vectors]
Let A_l: E'to E and B_r: F'to F be finite families with
sum_r|< x,B_r y>|^2le C|x|^2|y|^2. Then for unit
win E ⊗ F and w'in E' ⊗ F',
sum_{l,r}|< w,(A_l ⊗ B_r)w'>|^2le Csum_l|A_l|_op^2.
Proof.
For fixed l, B|->< w,(A_l ⊗ B)w'> has operator
norm le|A_l|_op; by trace-norm duality it is
sum_s c_s< x_s,By_s> with unit x_s,y_s, c_sge0,
sum_s c_sle|A_l|_op. The triangle inequality in ell^2(r), then
squaring and summing in l, finishes.
The fiber overlap for arbitrary pure carrier vectors w,w' therefore has
the form sum_{l,r}|< w,(A_l ⊗ B_r)w'>|^2 with A_l the
row-decomposition overlaps and B_r the column ones. On Z itself the
row and column subgroups intersect trivially, so the pairwise products of
their group elements use unique factorisations; Plancherel in G_t gives
for unit x,y
sum_r|< x,B_ry>|^2 le (D_tau D_pi)/(D_b)
(t!)/(prod_i v_i!prod_j u_j!) le (D_tau D_pi)/(D_b)e^{E_0+O(t)}
(using E_0=tlog t-sum v_ilog v_i-sum u_jlog u_j and factorial
bounds). Lemma~lem:entangled upgrades this to arbitrary carrier
vectors, and Theorem~thm:occupied bounds sum_l|A_l|_op^2.
smallskipnoindentPutting the pieces together.
Write S=max{0,log(D_sigma D_theta/D_a)}. Combining
(eq:occupied), the fiber bound via Lemma~lem:entangled, and
(eq:on-Z), and dividing by D_alpha D_zeta from the diagonal-block
formulas, the pure-state bound becomes
[
(1)/(D_aD_b)exp{E_0-S+O(t+(m+n+1)h^2log(N+2))}.
]
The positive mixtures have total weight 1, so no extra count appears.
Multiply by D_mu D_nu L_{RC}^2/(L_RL_C) and use
D_lambdale L_0D_aD_b and (eq:layout):
(D_mu D_nu)/(D_lambda)
exp{2E_0-S+O(t+(m+n+1)h^2log(N+2))}.
smallskipnoindentThe weight budget pays 2E_0-S.
Restrict mu_i to its complement row of size n-v_i: the surviving type
sigma_i is a subpartition of mu_i of that size; likewise theta_j
is a subpartition of nu_j of size m-u_j. So
[
J(mu)+J(nu)le b_0log(D_sigma D_theta)+b_1tlog N
-ABig(sum_i F_n(v_i)+sum_j F_m(u_j)Big).
]
Together with (eq:trim), this gives
J(lambda)-J(mu)-J(nu) ge -b_0 S+AE_0
-Obig(h^2+(mn^{1-eta}+nm^{1-eta})log(N+2)big).
Therefore, with E the error in (eq:budget),
[
2E_0-S-[J(lambda)-J(mu)-J(nu)]
le (2-A)E_0-(1-b_0)S+E,
]
since Age2, b_0le1, E_0,Sge0. This is exactly the statement that
replacing D_mu D_nu/D_lambda by W_mu W_nu/W_lambda (i.e.
dividing (eq:pref-final) by D_lambda e^{-J} and multiplying by the
child weights) leaves only the error E. All error terms and the
count of profiles are O((log D_lambda)/d) by (eq:dim-large), and
hle N^{1/16}, m,nasympsqrt N, eps<eta/2. This is
(eq:weighted-overlap).
%=========================================================================
part{Schatten interpolation}
%=========================================================================
# A p-moment bilinear estimate
The row part and the column part of the sweep multiply (in the scan order)
to give K_d. Each part, inside a row or a column, is an independent
smaller sweep. Let B(M,M')calB(M,M') on V_lambda be the product of the
two subgroup matrix actions, using arbitrary matrices M_mu, M'_nu on
their irreducibles.
Under (eq:not-sparse), for 2le p<∞,
W_lambda|B(M,M')calB(M,M')|_p^p
le e^{O((log D_lambda)/d)}
Big(sum_mu W_mu|M_mu|_p^pBig)Big(sum_nu W_nu|M'_nu|_p^pBig),
with the constant in the exponent independent of p.
Proof.
For a single pair of types, the squared 2-norm is a trace of a product of
positive matrix actions; diagonalising and using (eq:weighted-overlap)
gives
W_lambda|B(M,M')calB(M,M')|_2^2le e^{E}(sum_mu W_mu|M_mu|_2^2)
(sum_nu W_nu|M'_nu|_2^2) with E=O((log D_lambda)/d). Summing over
type tuples with triangle and Cauchy--Schwarz absorbs the log counts
(which are O(N^{3/4}log N), covered by (eq:dim-large)) into E.
Also |B(M,M')calB(M,M')|_oplemax_mu|M_mu|_opmax_nu|M'_nu|_op
by unitary restriction.
Now interpolate. Let the bilinear map Phi carry (M,M') to
B(M,M')calB(M,M') with output weighted trace-norm. It has norm le e^{E/2}
at the 2-Schatten endpoint and le1 at the operator-norm endpoint.
Normalise inputs to p-norm 1; test the output against a dual-norm-one
matrix. On the strip with value at z=2/p, extend the inputs blockwise by
polar factors with exponent pz/2 on absolute values (zero singular values
kept zero) and the test matrix with exponent p'(1-z/2),
p'=p/(p-1). Boundary norms are le1; the three-lines inequality gives
factor e^{(E/2)theta}=e^{E/p} at theta=2/p. Raising to the p-th
power gives (eq:interp), and the exponent coefficient does not grow
with p.
%=========================================================================
part{The sparse shapes}
%=========================================================================
# Representations whose first row is almost the whole diagram
When k=N-lambda_1 is small, the general machinery is overkill; a direct
combinatorial estimate is better. This is the range that seeds the
induction.
For k=N-lambda_1ge1,
|K_d(lambda)|_op le (Cd)^k,(k/N)^{k/8}
for an absolute C.
Proof.
Work on ordered injective k-tuples of positions x|-> y. Let K be
the sweep transition kernel. On functions of k-tuples that sum to zero
over any one coordinate (all others fixed), K acts; this subspace contains
V_lambda because V_lambda occurs on k-tuples (invariants upon
restriction to G_{N-k}, branching T1) but not on (k-1)-tuples.
smallskipnoindentThe pair-factor formula.
A sweep sends each card along a path; the path of a card is fixed by its
start and end, since the successive end coordinates replace the start ones.
For two cards, let ell be the last coordinate where they differ at the
start and r the first coordinate where they differ at the end. Give the
pair weight w=0 if r>ell, w=2 if r=ell, w=1 otherwise. Then
K(x,y)=N^{-k}prod_{pairs}w. (Paths do not collide iff
rleell for all pairs; a switch used by two paths rather than one
contributes the factor 2 exactly when a pair has r=ell.) This works for
any subset of cards.
smallskipnoindentCancelled kernel.
Because the zero-sum subspace forces all proper-coordinate marginals to
vanish, we may replace K by the fully cancelled
[
D(x,y)=N^{-k}sum_{B⊆[k]}(-1)^{k-|B|}prod_{pairs in B}w .
]
This vanishes unless the contact graph (pairs with wne1) has no isolated
vertex, and its absolute column sums are le2^k (each subset term in
absolute value is the nonnegative doubly stochastic sweep kernel).
smallskipnoindentInclusion of occupied sets.
In K^*K we sample x from the row z of K^* (a reverse scan). The
occupied set S of x satisfies, for every fixed F,
Pr(S⊇ F)le(k/N)^{|F|}.
This is the upper product-of-marginals property: true at the reverse scan
start, and preserved by a random switch (test one switched site, average
the two bounds; test both, and the product of marginals can only grow under
averaging). The final marginals are k/N (one position is uniform after
all coordinates).
smallskipnoindentA spanning forest.
A no-isolated-vertex graph on S contains a spanning forest with cle k/2
rooted trees of size ge2. There are le C_0^k forest shapes, choose
roots in binom Nc ways and path types in 2^k ways. Conditioned on the
common routing, expose children after parents: a common-routing child has
at most two possible start positions per meeting switch, and an
independent-path child summed over fresh positions meets a given parent at
stage i with expectation le2^i2^{-(i-1)}. Each embedding uses k sites,
so multiply by (k/N)^k via (eq:inclusion). Summing gives, for the
signed kernel K^*D, absolute row sum le(C_1d)^k(k/N)^{k/2} using
binom Ncle(C_2N/k)^{k/2} for cle k/2. The ell^2-operator (Schur)
bound on this subspace bounds K^*K there, proving (eq:sparse).
%=========================================================================
part{The induction that proves the main moment bound}
%=========================================================================
# Closing the induction
Proof. [Proof of Theorem~thm:main]
All K_d(lambda) are contractions. Partitions of length >N/2 are killed
by one matching layer; the trivial one satisfies (eq:main-bound) at any
exponent.
smallskipnoindentSparse range. For 1le kle N^{1-eps},
(eq:sparse) with W_lambdale D_lambdale N^k gives, for all large
d and any sufficiently large absolute exponent p,
[
W_lambda|K_d(lambda)|_p^p
le N^k· N^{k},N^{-eps k p/8}·(log-factor)^kle1 .
]
smallskipnoindentThe recursive step. Suppose (eq:main-bound)
holds at the two smaller bit sizes d_1,d_2lelceil d/2rceil with their
exponents. Apply (eq:interp) at p=max(p_{d_1},p_{d_2})ge2, feeding
in the two subgroup sweep parts. Each input on a tuple is a tensor product of
smaller sweeps, so each weighted p-th power term of the inputs is le1
by the inductive hypothesis, and the sums over type tuples use only the
count bounds. Thus
[
W_lambda|K_d(lambda)|_p^pleexp{C(log D_lambda)/d}
]
with C absolute. Since W_lambdage D_lambda^{3/4},
[
|K_d(lambda)|_p^p le D_lambda^{-3/4}e^{C(log D_lambda)/d}
le D_lambda^{-1/2}
]
for large d (so C/dle1/4), which gives |K|_op^ple|K|_p^ple D_lambda^{-1/2}.
Push the exponent by a small factor 1+theta. Interpolation of Schatten norms
gives |K|_{p(1+theta)}^{p(1+theta)}le|K|_op^{theta p}|K|_p^p for
thetage0. Write E=C(log D_lambda)/d, so that W_lambda|K|_p^ple e^{E}
and |K|_op^{theta p}le(D_lambda^{-3/4}e^{E})^{theta} (using
W_lambdage D_lambda^{3/4}). Then
[
W_lambda|K|_{p(1+theta)}^{p(1+theta)}
le D_lambda^{-3theta/4},e^{E(1+theta)}le1
]
once thetage C'/d with an absolute C' (take C'=2C). Take
p_d=p(1+C'/d); then (eq:main-bound) holds at p_d.
smallskipnoindentBase case. For each fixed small d, a nontrivial
sweep matrix is a product of orthogonal projections that together generate
S_N, so its operator norm is strictly below 1 on every nontrivial
V_lambda (equality would need a common invariant vector for all matching
switches, whose generated group is all of S_N). Hence a finite absolute
base exponent p_0 exists covering the finitely many dle d_0, chosen also
large enough for the sparse range.
smallskipnoindentBounded exponent. The recurrence multiplies the
two child exponents by 1+C'/d and then takes a maximum. Along repeated
halvings d|->lceil d/2rceil the sum of 1/d is a convergent
geometric series, so p_dle p_*<∞ with p_* absolute. This proves
(eq:main-bound), hence Theorem~thm:main.
%=========================================================================
part{From the moment bound to mixing}
%=========================================================================
# Plancherel and Cauchy--Schwarz
Let pi be the uniform permutation distribution, and let Pr_j be the law
of j independent forward sweeps. Finite-group Plancherel and
Cauchy--Schwarz (Diaconis--Shahshahani 1981, Sections 2--3) give
4,|Pr_j-pi|_{TV}^2 le sum_{lambdane(N)} D_lambda|K_d(lambda)^j|_{HS}^2 .
We bound |K_d(lambda)^j|_{HS}^2le D_lambda|K_d(lambda)|_op^{2j}.
By Theorem~thm:main and W_lambdage D_lambda^{3/4},
|K_d(lambda)|_ople D_lambda^{-3/(4p_*)}. Hence
[
D_lambda|K_d(lambda)^j|_{HS}^2 le D_lambda^2,D_lambda^{-3j/(2p_*)}.
]
Taking j=8p_*/3 (an absolute number of sweeps) gives
D_lambda^2D_lambda^{-4}=D_lambda^{-2}. So
[
4|Pr_j-pi|_{TV}^2 le sum_{substack{lambdane(N) lambda^{rm tr}_1le N/2}} D_lambda^{-2}.
]
This sum tends to 0 as dto∞: for k>N^{1-eps} it is bounded by
(eq:dim-large) and the partition count; for 1le kle N^{1-eps},
D_lambdage e^{-1}(N/k)^k (top-row hook estimate as in Lemma~lem:dim)
and there are at most 2^k such diagrams. Since the product law determines
the deck from any fixed starting deck, this is a worst-case bound. Thus an
absolute number j of sweeps gives TV distance le1/4 uniformly in d
(large d; the finitely many small d converge by the strict Fourier gap
and only increase the absolute sweep count, and convolution cannot increase
TV). One sweep is d physical shuffles, so t_{rm mix}(d)le Cd. This is
the upper bound of Corollary~cor:mix.
%=========================================================================
part{The matching lower bound}
%=========================================================================
# Counting reachable permutations
[Support obstruction]
Let q_d be one physical shuffle. For every integer tge0,
[
|q_d^{*t}-U_{S_N}|_{TV} ge 1-frac{2^{tN/2}}{N!}.
]
Thus TV distance le1/4 needs at least
lceil(2/N)log_2(3N!/4)rceil=2d-O(1) physical shuffles.
Proof.
One physical shuffle uses N/2 independent fair bits (one per pair), so
t shuffles use tN/2 fair bits and can produce at most 2^{tN/2}
permutations. Testing against the uniform measure (which weighs every
permutation and every non-reachable point in the complement),
|q_d^{*t}-U_{S_N}|_{TV}ge1-2^{tN/2}/N!. The threshold
2^{tN/2}/N!le3/4 rearranges to the stated lower bound; Stirling gives the
2d-O(1) form.
This is the lower bound of Corollary~cor:mix. Combined with the upper
bound, t_{rm mix}(d)=Θ(d)=Θ(log N).
%=========================================================================
{99}
bibitem[Thorp(1973)]{Thorp} E.~O.~Thorp, Nonrandom shuffling with
applications to the game of Faro, J. Amer. Statist. Assoc. 68 (1973),
842--847.
bibitem[Morris(2008)]{Morris2008} B.~Morris, The mixing time of the Thorp
shuffle, SIAM J. Comput. 38 (2008), 484--504.
bibitem[Morris(2009)]{Morris2009} B.~Morris, Improved mixing time bounds for
the Thorp shuffle and the L-reversal chain, Ann. Probab. 37 (2009),
453--477.
bibitem[Morris(2013)]{Morris2013} B.~Morris, Improved mixing time bounds for
the Thorp shuffle, Combin. Probab. Comput. 22 (2013), 118--132.
bibitem[Montenegro--Tetali(2006)]{MT} R.~Montenegro, P.~Tetali,
Mathematical aspects of mixing times in Markov chains, Found. Trends
Theoret. Comput. Sci. 1 (2006), 237--354.
bibitem[Czumaj--Vocking(2014)]{CV} A.~Czumaj, B.~V"ocking, Thorp shuffling,
butterflies, and non-Markovian couplings, ICALP 2014, LNCS 8572, 344--355.
bibitem[Diaconis--Shahshahani(1981)]{DS} P.~Diaconis, M.~Shahshahani,
Generating a random permutation with random transpositions, Z. Wahrsch. 57
(1981), 159--179.
bibitem[Sagan(2001)]{Sagan} B.~E.~Sagan, The Symmetric Group, 2nd ed., GTM
203, Springer, 2001.
bibitem[Stanley(1999)]{Stanley} R.~P.~Stanley, Enumerative Combinatorics II,
Cambridge, 1999.
bibitem[James(1978)]{James} G.~D.~James, The Representation Theory of the
Symmetric Groups, LNM 682, Springer, 1978.
bibitem[Etingof et al.(2011)]{Etingof} P.~Etingof et al., Introduction to
representation theory, MIT lecture notes, 2011.
bibitem[Borcea--Br"anden--Liggett(2009)]{BBL} J.~Borcea, P.~Br"anden,
T.~M.~Liggett, Negative dependence and the geometry of polynomials, J. Amer.
Math. Soc. 22 (2009), 521--567.
bibitem[Carlen--Cordero-Erausquin(2009)]{CCE} E.~A.~Carlen,
D.~Cordero-Erausquin, Subadditivity of the entropy and Brascamp--Lieb type
inequalities, GAFA 19 (2009), 373--405.
bibitem[Vershik--Okounkov(2005)]{VO} A.~M.~Vershik, A.~Yu.~Okounkov, A new
approach to the representation theory of the symmetric groups II, J. Math.
Sci. 131 (2005), 5471--5494.
bibitem[Perelomov(1972)]{Perelomov} A.~M.~Perelomov, Coherent states for
arbitrary Lie group, Comm. Math. Phys. 26 (1972), 222--236.
bibitem[Franks--Walter(2022)]{FW} C.~Franks, M.~Walter, Minimal length in an
orbit closure as a semiclassical limit, arXiv:2004.14872.
bibitem[Kempf--Ness(1979)]{KN} G.~Kempf, L.~Ness, The length of vectors in
representation spaces, LNM 732, Springer, 1979, 233--243.