THE THORP SHUFFLE ON 2^d CARDS MIXES IN THETA(d) SHUFFLES
A signed-tensor proof, presented from scratch

ABSTRACT

A fair coin decides whether each consecutive pair of cards is swapped.  Do
this d times in a row, at each step rotating which coordinate is being
paired, and you have run one "coordinate sweep".  How many times must we
repeat the sweep before the deck is truly random?

This note answers that question with a Theta(d) estimate: a constant
number of sweeps suffices, and the answer does not depend on the exact
constant.  The whole argument is written out, from the counting lower
bound up through the deepest representation-theoretic estimate.

The proof has three parts.  First, a support lower bound: t physical
shuffles have support of size at most 2^{tn/2}, while a uniform
permutation on n cards has support n!.  This forces t >= 2d - O(1).
Second, a Fourier and moment framework that turns "uniform in squared
L^2" into "uniform in total variation".  Third, the main technical
estimate -- a bound on D_lambda Tr(B_n^* B_n)^r for one fixed moment r,
uniform in the irreducible V_lambda.  The name "signed-tensor" refers to
the device that makes the moment induction work; we explain it slowly.

Throughout n = 2^d.  Positions are binary strings of length d.  One
"physical shuffle" is one pass of the local pairing rule (d steps of the
sweep all together).  One "sweep" is exactly d physical shuffles, one in
each coordinate direction.  The main theorem says that 200d physical
shuffles suffice for large d, while at least 2d - O(1) are necessary;
the mixing time is Theta(d) = Theta(log n).

The conclusion is stated precisely as THEOREM A below and proved in
Sections 1 through 9.  Section 10 collects the pieces and produces the
final inequality.


1.  THE SHUFFLE AND THE QUESTION

Label positions by vectors x = (x_1, ..., x_d) in F_2^d.  Let R be the
cyclic rotation

    R(x_1, ..., x_d) = (x_2, ..., x_d, x_1).

Let S be the operation that independently fixes or swaps each pair
{x, x + e_1}, where e_1 = (1, 0, ..., 0) and "x + e_1" is bitwise
addition mod 2.  One physical Thorp shuffle on the labels is R S.
Equivalently, undo the rotation after each step; then the pair-switch
happens in coordinate i_t = 1 + ((t-1) mod d).  After d physical
shuffles every coordinate has been refreshed exactly once.  That is
one sweep.

For a single card, each sweep refreshes each of its d bits with one
fresh fair coin.  So after exactly one sweep that card is uniform on
F_2^d.  The hard problem is the JOINT law of all n cards, because
different cards share switch bits.

Let q_d be the law of one physical Thorp shuffle as a permutation
of positions.  Let q_d^{*t} be the t-fold convolution (composition of
independent copies).  Let U_n be uniform measure on the symmetric
group S_n.

For two probability measures mu, nu on S_n, define

    TV(mu, nu) = (1/2) sum_g |mu(g) - nu(g)|.

This number bounds the discrepancy of the measures on any event.  Let

    t_mix(d) = least t >= 0 with TV(q_d^{*t}, U_n) <= 1/4.

THEOREM A (Thorp shuffle mixing).  For large d,

    TV(q_d^{*(200d)}, U_n) -> 0,

so t_mix(d) <= 200d.  Moreover, for every integer t >= 0,

    TV(q_d^{*t}, U_n) >= 1 - 2^{tn/2} / n!,

so t_mix(d) >= 2d - O(1).  In particular t_mix(d) = Theta(d).

The constant 200 is not claimed to be optimal.  What matters is that it
does not grow with d.  The lower and upper bounds are proved separately:
lower in Section 2, upper in Sections 3-9 after the technical moment
estimate is established.


2.  THE LOWER BOUND: COUNT THE COINS

One physical shuffle uses n/2 = 2^{d-1} independent fair coins.  After
t physical shuffles there are at most 2^{tn/2} possible coin strings,
hence at most 2^{tn/2} possible permutations in the support of q_d^{*t}.

Let A be that support.  Then q_d^{*t}(A) = 1, while

    U_n(A) <= |A| / n! <= 2^{tn/2} / n!.

The total variation distance between a distribution supported on A and
the uniform law is at least 1 - U_n(A).  Hence

    TV(q_d^{*t}, U_n) >= 1 - 2^{tn/2} / n!.

If this is at most 1/4, then 2^{tn/2} / n! >= 3/4.  Stirling gives

    (tn/2) log 2 >= log n! + log(3/4)
                  >= n log n - n - O(log n).

Divide by (n/2) log 2:  t >= 2 log_2 n - O(1) = 2d - O(1).

That is the whole lower bound.  No probability estimate or Fourier
analysis is involved; it is pure counting.


3.  A DICTIONARY OF S_n REPRESENTATIONS

The upper bound uses the Fourier analysis of finite groups.  This
section reviews the pieces of symmetric-group representation theory that
we shall use, at a level sufficient for the proof.  A reader who has
seen matrices and factorials can follow.

A representation of a finite group G is a homomorphism

    rho : G -> U(V)

from G to the group of unitary endomorphisms of a finite-dimensional
complex inner-product space V.  It is irreducible if V contains no
G-invariant subspace other than {0} and V.  Its degree D is the
dimension of V.

The irreducible complex representations of the symmetric group S_s are
indexed by partitions lambda of s.  A partition is a nonincreasing
sequence of positive integers

    lambda = (lambda_1, lambda_2, ..., lambda_k),  lambda_1 >= ... >= 0.

We write lambda |- s.  Draw lambda as a left-justified array of boxes,
with lambda_i boxes in row i.  The conjugate partition lambda^t has
lambda^t_j equal to the number of rows of lambda with at least j boxes;
equivalently it is lambda reflected across the main diagonal.

A standard Young tableau of shape lambda is a filling of the boxes of
lambda with 1, ..., s, increasing in both rows and columns.  The degree
f^lambda of the irreducible V_lambda is the number of these tableaux.
The hook-length formula computes it directly:

    f^lambda = s! / prod_{cell z in lambda} h(z),

where the hook length h(z) is the size of the "hook" attached to the cell
z: the cell itself, the cells to its right in the same row, and the cells
below it in the same column.

Two extremes.  The partition (s) has one row and one tableau (1, 2, ...,
s), giving degree 1: the trivial representation.  The partition (1^s) has
one column and one tableau going down, giving degree 1: the sign
representation.

The following estimates about degrees are used without proof below,
because they are classical in representation theory.  A proof of the
parts we need is in every book on the symmetric group; the friendly
source is B. Sagan, "The Symmetric Group" (2001), and the elementary
argument used in the companion paper also works.

FACT 3.1 (Dimension lower bounds).
   (a)  f^lambda >= 1, with equality only for lambda = (s) or (1^s).
   (b)  If lambda has exactly s - k boxes below its first row (so
        lambda_1 = s - k), then for k <= s/4,
            log f^lambda >= c_1 k log(s/k) - O(k).
   (c)  If lambda has at most s/2 rows and at most s - n^{0.9}
        boxes below the first row, then log f^lambda >= n^{0.8}.
   (d)  For any two small constant slacks, if lambda has first row
        s - k with k >= n^{0.99}, then log f^lambda >= s^{0.99}.

These are not sharp; they are simply what the mixing proof uses.

FACT 3.2 (Branching and Littlewood-Richardson).
   (a)  Young branching.  The restriction of V_lambda from S_s to the
        subgroup S_{s-1} fixing one point decomposes as a direct sum
        of V_mu over the mu in lambda minus one outer corner.
   (b)  Pieri and Littlewood-Richardson.  For partitions alpha, beta
        of sizes a, b, the tensor product V_alpha tensor V_beta
        induces (via the Young subgroup S_a x S_b <= S_{a+b}) a
        representation of S_{a+b} that contains V_lambda with a
        combinatorial multiplicity (a Littlewood-Richardson
        coefficient).  In particular, if beta = (b) is a single row
        and lambda / alpha is a horizontal strip of size b, the
        multiplicity is one; if beta = (1^b), replace "horizontal"
        by "vertical".

These facts are the standard engine of the symmetric-group theory.  We
use them to "attach" and "detach" boxes from Young diagrams.

FACT 3.3 (Dual pairs and Schur-Weyl duality, in one sentence).
On (C^s)^{tensor p} there is a commuting action of S_p (permuting
tensor factors) and of the unitary group U(s) (acting diagonally).  The
space decomposes as a direct sum, over partitions alpha of p with at most
s rows, of

    V_alpha  tensor  U_alpha,

where V_alpha is the S_p irreducible of shape alpha and U_alpha is the
U(s) irreducible with highest weight alpha, of complex dimension D_alpha
given by the Weyl dimension formula

    D_alpha = prod_{1 <= i < j <= s}
                  (alpha_i - alpha_j + j - i) / (j - i).

Symmetric-group quantities come in pairs with Schur-Weyl duality.  This
is the single most-used item below; when we write a permutation operator
on a "signed tensor space", it is acting on the S-side of this
decomposition, and the compact group acts on the U-side.

FACT 3.4 (Marked-label coefficient restriction).
If G is a finite group, H <= G, and x = sum_g x_g g is a positive
element of the group algebra C G, then restricting to the sum over h in H
of the coefficients x_h gives a positive element of C H.  In the regular
representation, its matrix on l^2(H) is a principal submatrix of the
matrix of x, hence positive.  Its regular trace is

    Tr_{reg,H}(E_H x)  =  |H| x_e  =  |H| Tr_{reg,G}(x) / |G|.

And on a single irreducible V_rho of H, its trace is at most the regular
trace divided by dim(V_rho).  This is the standard consequence of the
identity Trace(V_rho) <= regular trace / dim(V_rho) applied in the
orthogonal decomposition of the regular representation.

These are the four representation-theoretic facts.  Nothing else is
required; what remains is the analysis of tensor powers.


4.  FOURIER ANALYSIS AND THE L^2 CRITERION

For a probability measure mu on S_n and an irreducible V_lambda, define
the Fourier transform

    hat mu(lambda) = sum_{g in S_n} mu(g) * rho_lambda(g).

This is a D_lambda x D_lambda matrix.  For convolution,

    hat{mu * nu}(lambda) = hat mu(lambda) hat nu(lambda).

Two norms on matrices are used:

   Spectral (operator) norm:  || A ||_op = largest singular value of A.

   Hilbert-Schmidt norm:  || A ||_HS = ( sum_{ij} |A_{ij}|^2 )^{1/2}.

Both are unitarily invariant, and ||A||_HS <= sqrt(D_lambda) ||A||_op
because the square root of the number of singular values is sqrt(D_lambda).

PLANCHEREL IDENTITY.  For a probability mu on S_n,
sum_{lambda |- n} D_lambda || hat mu(lambda) ||_HS^2
    = | S_n | * sum_g mu(g)^2
    = n! * sum_g mu(g)^2.

We shall use this in the "distance to uniform" form.  Write nu = mu - U_n,
which is a signed measure of total mass zero.  Then hat nu(lambda) =
hat mu(lambda) for every nontrivial lambda and hat nu(trivial) = 0.
Plancherel gives

    || mu - U_n ||_2^2
        =  sum_{lambda != (n)} D_lambda || hat mu(lambda) ||_HS^2.

Also TV(mu, U_n) <= (1/2) || mu - U_n ||_2, by Cauchy-Schwarz:

    2 TV(mu, U_n) = sum_g |nu(g)| = sum_g |nu(g) . 1|
                 <= (sum_g |nu(g)|^2)^{1/2} * (sum_g 1)^{1/2}
                 = (n!)^{1/2} (sum_g |nu(g)|^2)^{1/2}
                 = || nu ||_2.

Therefore: if mu = q_d^{*t} and || mu - U_n ||_2 -> 0, then
TV(mu, U_n) -> 0, and mu is mixing.

FOURIER OF A SWEEP.  The sweep operator of one physical Thorp shuffle is

    hat q_d(lambda) = rho_lambda(some permutation action).

Concretely, with the notation B_n = Pi_d Pi_{d-1} ... Pi_1 (the operator
in V_lambda given by averaging one coin-toss layer per coordinate), the
Fourier transform of q_d^{*L} is B_n^L, the L-th power of B_n.  The
initial operators Pi_i are orthogonal projections (each is the averaged
projection onto a pair-switching subgroup).  B_n is not normal, so
the spectral picture of B_n is not simply diagonal; but || B_n^L ||_op
= || B_n ||_op^L, and Schatten inequalities control || B_n^L ||_HS by
|| B_n ||_op^{L-2} Tr(B_n^* B_n).  We use precisely this below.

The single linear-algebraic observation we shall need from this is:

LEMMA 4.1 (Safe use of sweep powers).  For integers r >= s >= 1 and any
matrix T, let Q = T^* T.  Then

    || T^r ||_HS^2 <= || Q ||_op^{r - s} Tr(Q^s).

Proof.  Schatten interpolation ("Holder") gives || T^s ||_HS <=
|| T ||_{S^{2s}}^s = (Tr(Q^s))^{1/2}, and multiplying the remaining
r - s factors of T bounds the operator norm by || Q ||_op^{(r-s)/2}.
Squaring combines.  No normality of T is used.

This lemma says that a single moment estimate Tr(Q^s) <= small, at a
short moment s, upgrades to an L^2 estimate at every longer power, as
long as ||Q||_op <= 1 (which it is: each Pi_i is an orthogonal
projection, hence a contraction).

The framework is now in place.  The rest of the paper proves:

MOMENT THEOREM (Section 5, proved in Sections 6-9).
There are absolute constants c_0 > 0 and r >= 1, such that for every
dyadic n = 2^d and every partition lambda |- n with lambda_1 <= 3n/4,

    log( D_lambda * Tr_{V_lambda}(B_n^* B_n)^r )
        <=  -c_0 log D_lambda.

For the remaining shapes (lambda_1 > 3n/4), the sweep is annihilated
on V_lambda, so the moment is zero.

Once this theorem is granted, the full-deck mixing bound follows in
Section 10 with only bookkeeping: apply the Plancherel identity, use
Lemma 4.1 with s = r and r replaced by a bigger moment, and sum the
resulting 1/D_lambda using the reciprocal-degree lemma.


5.  THE MOMENT THEOREM: STATEMENT, AND WHY IT IS TRUE

Recall Pi_i is the orthogonal projection in V_lambda onto the average of
the i-th pair-switch.  The sweep operator is B_n = Pi_d Pi_{d-1} ...
Pi_1.  Its adjoint is B_n^* = Pi_1 Pi_2 ... Pi_d.  The product Q_n =
B_n^* B_n is positive.  We want a bound on Tr_{V_lambda}(Q_n^r) for one
fixed r, uniformly over lambda.

MOMENT THEOREM (restated).  There are absolute constants c_0 > 0 and
r_0 >= 1 such that for every dyadic n = 2^d, every r >= r_0, and every
partition lambda |- n with lambda_1 <= 3n/4,

    log( D_lambda * Tr_{V_lambda}(Q_n^r) )
        <=  -c_0 * log D_lambda.

If lambda_1 > 3n/4, the first pair-switch already annihilates V_lambda:
the only invariants of the pi_1 averaging are those shapes whose Young
diagram dominates (2, 2, ..., 2, 0, ..., 0) with n/2 boxes; such shapes
have at least n/2 rows, hence first row at most n/2, and in particular
at most 3n/4.  So in the exceptional range Tr(Q_n^r) = 0 and the
inequality holds trivially.

Why should such a bound be true?  Think of the "first-row defect"

    k  =  n - lambda_1,

the number of boxes below the first row of lambda.  There are two
regimes, handled by completely different arguments.

SMALL k (the "sparse" regime).  When k is small, V_lambda embeds in the
permutation module of order-k-tuples of distinct positions.  Intuitively
this is because the shape (n-k, lambda_2, ...) is contained inside the
first row of length n-k together with a small tail.  On this tuple
module, the sweep operator acts by a Markov kernel that is a sum of
path-collision events between the k labels.  With k labels and n
positions, collisions are rare: two independent labels share a switch
on a given coordinate with probability about 1/sqrt(n), and k is
small.  The alternating-sum trick (inclusion-exclusion over subsets of
the k labels) makes all path-configurations with an "isolated" label
cancel; the kernel only survives on configurations where every label
collides with at least one other.  Such configurations cost an
exponential penalty in k.  That is the sparse case, and Section 6
turns the intuition into the estimate

    || B_n ||_{V_lambda} <= exp(O(k)) * (2dk/n)^{k/4}.

For k << sqrt(n) this is astronomically small.

LARGE k (the "dense" regime).  When k is large, the sparse estimate
is not useful.  Instead we split the sweep into two halves.  Take the
first floor(d/2) coordinates as "rows" and the last ceil(d/2) as
"columns".  If s = 2^{floor(d/2)} and m = 2^{ceil(d/2)}, positions
form an s x m grid, and

    B_n = B_col B_row,

where B_row is a tensor product of independent size-s sweeps within
rows, and B_col is a tensor product of independent size-m sweeps within
columns.  By a trace inequality of Araki-Lieb-Thirring (Fact 8.1 below),

    Tr_{V_lambda}(Q_n^r)  <=  Tr_{V_lambda}(X Y)

where X = (B_row B_row^*)^r and Y = (B_col B_col^*)^r are positive
elements of the row and column subgroup algebras respectively.  Each
factors over its lines: X = tensor_{rows} X_i, Y = tensor_{cols} Y_j.

Now comes the signed tensor.  Fix an occurrence

    V_alpha  tensor  V_{beta^t}  tensor  V_gamma
        <=  Res^{S_n}_{S_u x S_v x S_l} V_lambda

for partitions alpha, beta, gamma with |alpha| = u, |beta| = v,
|gamma| = l, u + v + l = n.  Here l is a count of "marked positions"
that we explicitly do not track.  This occurrence exists by Young
branching and the Littlewood-Richardson rule whenever the decomposition
is combinatorially possible; the point of choosing it is to isolate
long rows (alpha), long columns (beta^t), and a small remainder
(gamma, with l boxes to hide in the "marks").

The signed tensor intuition is a color-coding trick.  Label each of the
n positions by one of q "even colors" e_1, ..., e_q or q "odd colors"
o_1, ..., o_q, and let S_n act on (C^{2q})^{tensor n} by permuting
positions, with a minus sign whenever two odd colors trade places (a
"graded" permutation).  The signed permutation action commutes with the
natural diagonal action of the compact group G_q = U(q) x U(q).  By
Schur-Weyl duality (Fact 3.3, applied twice, once to the even slots and
once to the odd slots), the space decomposes into pieces indexed by a
"compact type" (a, b), where a is a partition with at most q rows
counting even-slot content and b is the same for odd; and the piece
carries the S_n irreducible V_rho for every rho compatible with the type
via Littlewood-Richardson.

The KEY point.  For a properly chosen compact type (a, b), the piece
that carries V_lambda has a large S_n-irreducible dimension D_gamma of
gamma as its multiplicity.  Specifically, choosing a to be the first u
rows of the target, b to be the transposes of the next v rows, and gamma
to be the remainder, the multiplicity of V_lambda on the signed tensor
space is at least D_gamma (and typically much more, but that is not
needed).

Combine this with a positivity argument.  X and Y are positive
permutation-group-algebra elements; they commute with the signed action
of S_n on the signed tensor space, hence commute with the global
type-λ projection P.  Positive traces on irreducible components are
nonnegative.  This gives

    D_gamma * Tr_{V_lambda}(X Y)  <=  Tr_{signed tensor}(P X Y).

And the right-hand side factorizes into "local" pieces over rows and
columns.  For each row, the trace picks up the form Tr(X_z P_H) for a
local row-type projection P_H; for each column similarly Tr(Y_z P_K).
Combining, the trace of P X Y is bounded by

    || P_H P_K P ||^2  *  Tr(X_z P_H) *  Tr(Y_z P_K)   (per local type)

and each factor is estimated separately:

  * Angle factor || P_H P_K P ||^2: how much do the local row and
    column type projections overlap, after intersecting with the global
    type?  Bounded by the "static angle" lemma (Section 7), which uses
    a density-matrix argument.

  * Local trace factor Tr(X_z P_H): bounded by the induction hypothesis
    applied in each row (a smaller-sized problem), combined with a
    "pointwise-stabilizer" trace inequality (Fact 3.4) for the marked
    positions.

  * Local entropy cost: each trivially-linear-in-n or trivially-
    logarithmic quantity is accounted for, and the final "budget" closes
    thanks to a small gain per split, iterated over d/2 levels.

Section 8 makes this precise.  Section 9 chooses the occurrence with an
alpha, beta, gamma that is FAVORABLE for the final estimate (in
particular, one with l = 0 and F(alpha, beta) <= C_0 * log D_lambda).
Section 10 then applies the moment theorem.

For a first reading, the logical dependencies are:

    Section 6 (sparse)  <-- no dependencies, uses only the tuple model.
    Section 7 (static)  <-- uses Fact 3.4 and the density-matrix trick.
    Section 8 (dense)   <-- uses Section 7 and the induction hypothesis
                            (i.e., the moment theorem itself, applied at
                            smaller dyadic sizes).
    Section 9           <-- uses only hook-dimension bounds.
    Section 10          <-- uses Moment Theorem + Lemma 4.1.

The sparseness threshold is k_0 = n^{1 - delta}, delta > 0 a small
absolute constant (delta = 1/64 is convenient).