Introduction

A single card can become uniformly distributed long before a shuffled deck is close to uniform. The Thorp shuffle makes this distinction particularly clear. Split a deck into two equal halves, pair cards that occupy corresponding positions, and choose the order of each pair by an independent fair coin. Interleaving the pairs produces the new deck. For a deck of size \(n=2^d\), every individual card is uniform after \(d\) shuffles. The question is how much longer it takes to randomize the joint order of all \(n\) cards.

We prove that a constant multiple of \(d\) shuffles suffices. Let \(q_d\) denote the law of one complete shuffle as a permutation of the positions, and let \(U_n\) be uniform on the symmetric group \(S_n\). Convolution is the law of composition of independent permutations, and \[\|\mu-\nu\|_{\mathrm{TV}} =\frac12\sum_g|\mu(g)-\nu(g)|.\] Write \(t_{\mathrm{mix}}(d)\) for the least nonnegative integer \(t\) at which \(\|q_d^{*t}-U_n\|_{\mathrm{TV}}\le1/4\).

One step in this theorem is one complete physical shuffle. Changing the initial deck translates the permutation law, so its distance from uniform is unchanged. The upper bound is asymptotic in \(d\); the constant \(1600\) is an explicit choice in the proof, not a proposed sharp constant. Determining a leading constant or a cutoff remains a separate question.

The full-law conclusion controls every statistic of the final deck and, in particular, the joint positions of any deterministic selection of cards, by contraction of total variation under a map. It also shows that this shuffle produces an approximately uniform permutation using \(O(n\log n)\) independent fair bits: each of the \(O(\log n)\) steps uses \(n/2\) bits. The support bound identifies the same order of randomness as necessary for this construction.

The model and the support obstruction

Let \(d\ge1\) be an integer. Identify the positions with \(V=\mathbb F_2^d\), write \(e_1,\ldots,e_d\) for its standard basis, and label each card by its initial position. A permutation maps a label to its current position; composition means \((gh)(x)=g(h(x))\). With \[R(x_1,\ldots,x_d)=(x_2,\ldots,x_d,x_1),\] one physical shuffle is \(RS\), where \(S\) independently fixes or swaps each pair \(\{x,x+e_1\}\). Thus its action is \[(x_1,u)\longmapsto (u,x_1+\xi_u),\] with independent fair bits \(\xi_u\).

Let \(S_1,S_2,\ldots\) be independent copies of \(S\). If \(Y_t=RS_tY_{t-1}\) is the physical permutation, started from \(Y_0=\mathrm{id}\), and \(X_t=R^{-t}Y_t\), then \[X_{t+1}=Q_tX_t,\qquad Q_t=R^{-t}S_{t+1}R^t.\] The \(Q_t\) are independent matching switches in the directions \(i_t=1+(t\bmod d)\), since \(R^{-t}e_1=e_{i_t}\). A block whose length is a multiple of \(d\) ends in the physical frame. We analyze this cyclic-coordinate process, writing \(\Pi_t=X_t\).

During one full sweep each coordinate of a given card is refreshed exactly once by a coin fair conditional on the card’s earlier path. These refreshed bits form a uniform binary string. Restoring the deterministic rotation preserves uniformity, proving the one-card assertion in the introduction.

Uniform measure is invariant under every position permutation. Starting from any fixed deck translates the law started at the identity and leaves its total-variation distance from uniform unchanged. Moreover, \(t\) shuffles have at most \(2^{tn/2}\) possible coin strings. Their support \(A\) therefore gives \[\|q_d^{*t}-U_n\|_{\mathrm{TV}} \ge q_d^{*t}(A)-U_n(A) \ge1-\frac{2^{tn/2}}{n!}.\] Distance at most \(1/4\) forces \(2^{tn/2}\ge3n!/4\), proving the rounded lower bound. The inequalities \((n/e)^n\le n!\le n^n\) give its asymptotic form.

For completeness, mixing exists in each fixed dimension. A full coordinate sweep has positive probability of being the identity, and of making any specified single cube-edge transposition. Edge transpositions on the connected cube generate \(S_n\). Every permutation can therefore be obtained in some number of sweeps; identity sweeps pad these representations to one common length. The kernel at that length assigns positive mass to every group element and hence dominates a positive multiple of \(U_n\). Iteration proves convergence. This finite-dimensional observation does not assert the numerical bound \(1600d\) for every \(d\).

A conditional flow with one sweep of memory

Choose an ordered list \((c_1,\ldots,c_k)\) of distinct labels independently of the shuffle. We will ultimately average over uniform lists, but first fix the list. For \(0\le\ell<k\le n\), expose the trajectories of its first \(\ell\) cards, and call the next card the tagged card. Let \(\mathcal F_s\) be the sigma-field generated by the list and the exposed paths through time \(s\). Let \(B_s\) be the positions not occupied by those \(\ell\) cards, so \(m=|B_s|=n-\ell\) is constant. Define \[p_s(x)=\mathbb P\{\Pi_s(c_{\ell+1})=x\mid\mathcal F_s\}, \qquad w_s(x)=p_s(x)-\frac1m\mathbf1_{B_s}(x).\] The vector \(w_s\) is supported on \(B_s\), has total sum zero, and has squared norm at most one. Averaging and transport also underlie Morris’s chameleon representation [10]. The next lemma identifies the unexposed coins directly for labeled trajectories.

Let \(A_i\) average a function across every coordinate-\(i\) pair, and write \(x^{(i)}=x+e_i\). Put \[E_s=\mathbb E\|w_s\|_2^2, \qquad L_s=\sum_x w_s(x)^2\mathbf1_{\{x^{(i_s)}\notin B_s\}}, \qquad b_s=\mathbb E L_s.\] Here the expectation includes the initial list when it is random. Before the next exposed positions are revealed, the transport choices on edges with one free position are independent fair coins. Hence \[ w_{s+1}=A_{i_s}w_s+\xi_s, \qquad \mathbb E(\xi_s\mid\mathcal F_s)=0. \tag{1}\] On a one-free-position edge whose free endpoint is \(x\), its noise is \[\pm\frac{w_s(x)}2(\delta_x-\delta_{x^{(i_s)}}),\] where \(\delta_x\) is unit mass at \(x\), and the signs are independent on distinct such edges. Other edges contribute no noise.

Why the recent noise contracts

We bound the recent-noise term \(b_s\) in terms of the energy \(E_s\), then use the resulting decay to control ordered card marginals.

Fix \(s\ge d-1\), put \(a=s-d+1\), and let \(H_0,H_1\) be the two halves defined by coordinate \(i_s\). The updates from \(a\) to \(s\) use every other coordinate once and do not cross these halves. Conditional on \(\mathcal F_a\), the initial free sets \(B_a\cap H_h\) and centered flows \(w_a|_{H_h}\) are fixed, and the future switch arrays in the two halves are independent. The pair \((B_s\cap H_h,w_s|_{H_h})\) is determined by this initial state and the switch array inside \(H_h\).

Every position at time \(a\) in a half is marginally uniform in that half after the intervening \(d-1\) updates: each of its remaining coordinates is refreshed by a conditionally fair coin. Summing this endpoint probability over the free positions at time \(a\) gives, for every \(y\in H_{1-h}\), \[\mathbb P\{y\in B_s\mid\mathcal F_a\} =\frac{|B_a\cap H_{1-h}|}{n/2}.\] For \(x\in H_h\), the random variables \(w_s(x)^2\) and \(\mathbf1_{\{x^{(i_s)}\in B_s\}}\) depend on opposite future arrays. Their conditional independence therefore yields \[ \mathbb E\left[\sum_{x\in H_h}w_s(x)^2 \mathbf1_{\{x^{(i_s)}\in B_s\}}\,\middle|\,\mathcal F_a\right] =\frac{|B_a\cap H_{1-h}|}{n/2} \mathbb E\left[\sum_{x\in H_h}w_s(x)^2 \,\middle|\,\mathcal F_a\right]. \tag{3}\] The values of the flow and the free set within one half need not be independent.

Now take a uniform random initial list, independent of the shuffle, and suppose \(m\ge n/8\). For every fixed realization of the shuffle, the image of the uniformly chosen free set is uniform among the \(m\)-subsets of \(V\). Thus \(B_a\) is unconditionally a uniform \(m\)-subset. Its count in either half has mean \(m/2\), and \[ \mathbb P\{|B_a\cap H_h|<m/4\}\le e^{-m/32}. \tag{4}\] For completeness we give the bounded-difference exponential-moment argument of Hoeffding and Azuma [6, 1] in this setting. Expose the uniform subset in random order and use the Doob martingale for its final half-count. Changing the next draw can be coupled with the remaining completion by exchanging the two possible drawn points; the increment has absolute value at most one. A centered random variable in an interval of length two has exponential moment at most \(e^{\theta^2/2}\): for \(\psi(\theta)=\log\mathbb E e^{\theta Z}\), the second derivative is a tilted variance at most one, and integration from zero proves the bound. Conditional multiplication over the \(m\) martingale increments gives \(\mathbb E e^{\theta(M_m-M_0)}\le e^{m\theta^2/2}\). Markov’s inequality and minimization in \(\theta\) give the lower-tail bound \(e^{-u^2/(2m)}\); use \(u=m/4\) to obtain (4).

With \[\beta=\frac1{16},\qquad \eta=2e^{-n/256},\] both half densities in (3) are at least \(\beta\), except on an \(\mathcal F_a\)-measurable event of probability at most \(\eta\). The exceptional event may be correlated with the energy. Since the energy is at most one, (3), summed over the halves, nonetheless gives \[ b_s\le(1-\beta)E_s+\eta. \tag{5}\] This uses an unconditional exceptional probability and does not claim concentration conditional on the exposed paths.

Let \(\gamma=31/32=1-\beta/2\). Equations (2) and (5) imply \[ E_t\le\gamma^{t-2d}+\frac\eta\beta =\left(\frac{31}{32}\right)^{t-2d} +32e^{-n/256}. \tag{6}\] For \(t\le2d\) the bound follows from \(E_t\le1\). For \(t>2d\), use induction in (2); all indices \(t-j\) are at least \(d\). The geometric contribution is at most \(\gamma^{t-2d}\), because \[(1-\beta)\sum_{j=1}^{\infty}(2\gamma)^{-j} =\frac{1-\beta}{2\gamma-1}=1.\] The constant contribution is at most \((1-\beta)\eta/\beta+\eta=\eta/\beta\). This proves (6).

We next turn the energy estimate into a bound on the positions of an ordered list. We use the sequential comparison of Morris [11], also given by Morris, Rogaway and Stegers [14]. It applies to any law on distinct-position tuples; \(U_{\mathrm{inj}}\) denotes the uniform law on such tuples.

The bound averages over the input list. We will use that average to choose a single partition into eight blocks for which all eight complementary marginals have small total error.

The remaining question concerns the full permutation, including dependencies involving the omitted cards. We now pass to representations of \(S_n\). Restricting a representation to the subgroups that permute labels within the eight blocks separates it into tensor factors. At least one factor is small enough that the span generated by a single vector remains controlled, even when that factor occurs with multiplicity. This converts the marginal estimates into bounds on the Fourier matrices of a slightly trimmed law. First we prove the dimension estimate needed to sum those bounds; then we carry out the trimming and orbit-span argument.

The representation degrees needed for the lift

The transfer needs two properties of symmetric-group representation degrees. A uniform bound on their reciprocal sum will control orbit dimensions for the label-block subgroups in Proposition 7. Decay of the sum away from the trivial and sign representations will control the full-group Fourier error in Section 7. We prove both properties here.

Let \(\lambda\vdash s\) be a partition of \(s\), represented by its Young diagram, whose row lengths are the parts of \(\lambda\). Write \(f^\lambda\) for the degree of the corresponding irreducible representation of \(S_s\). A standard Young tableau fills the diagram with \(1,\ldots,s\), increasing along each row and column. We use the classical facts that \(f^\lambda\) counts these tableaux, is unchanged by transposing the diagram, and satisfies the hook-length formula \[f^\lambda=\frac{s!}{\prod_{z\in\lambda}h(z)},\] where \(h(z)\) counts the box \(z\) together with the boxes to its right and below it. The row \((s)\) and column \((1^s)\) give the trivial and sign representations, respectively [18, 4].

Stronger asymptotics for every fixed positive inverse-degree exponent were proved by Liebeck and Shalev [8]. The elementary proof below gives all the summability used here.

From eight large marginals to the whole group

Assume \(d\ge3\), put \(G=S_n\), and let \(\mu=q_d^{*(200d)}\). Choose a uniform ordered partition \((M_1,\ldots,M_8)\) of the labels into blocks of size \(n/8\). Each complement is a uniform subset of size \(7n/8\). Giving it an independent uniform order yields exactly the list in (8), and changing that order does not change the total-variation distance. Therefore some deterministic partition has \[ \delta_n:=\sum_{a=1}^8 \|\mathcal L(\mu\text{ on }V\setminus M_a)-U_{\mathrm{inj}}\|_{\mathrm{TV}} \le8\varepsilon_n=o(1). \tag{10}\] Fix that partition. Let \(H_a\) be the subgroup of all permutations that fix every label outside \(M_a\). Two maps \(g,g'\) agree on the complement exactly when \(g'=gh\) for some \(h\in H_a\). Thus the complementary image tuple identifies the left coset \(gH_a\), and its uniform law is the coset pushforward of uniform measure on \(G\).

For each \(a\), remove every coset \(C\in G/H_a\) with \(\mu(C)>2|H_a|/|G|\), and let \(E\) be what remains after all eight removals. A bad coset satisfies \(\mu(C)\le2(\mu(C)-|H_a|/|G|)\). The sum of positive excesses is its marginal total-variation distance, so the union bound gives \[M:=\mu(E)\ge1-2\delta_n.\] For all sufficiently large \(n\), we have \(M\ge1/2\) and may define the conditional probability law \(\nu=\mu(\cdot\mid E)\). Then \[ \|\nu-\mu\|_{\mathrm{TV}}=1-M=o(1), \qquad \nu(gH_a)\le\frac2M\frac{|H_a|}{|G|} \le4\frac{|H_a|}{|G|}. \tag{11}\] A coset removed for that subgroup has no retained mass; every other coset had the required original cap. This proves the same cap for all eight systems under one common law. Consequently, for every nonnegative function that is constant on the cosets of any one \(H_a\), its expectation under \(\nu\) is at most four times its uniform expectation. The next proposition applies this comparison to projections onto orbit spans.

We use finite-dimensional complex Hilbert spaces. The operator norm is \(\|B\|_{\mathrm{op}}\), and the Hilbert–Schmidt norm is \(\|B\|_{\mathrm{HS}}^2=\operatorname{tr}(B^*B)\) with ordinary, unnormalized trace. Write \(\widehat H_a\) for the set of equivalence classes of irreducible representations of \(H_a\). For a probability measure \(\nu\) on \(G\) and a unitary representation \(\rho\), define \(\widehat\nu(\rho)=\sum_g\nu(g)\rho(g)\).

Eight convolution factors and the final comparison

The final comparison uses the finite-group Fourier method of Diaconis and Shahshahani [3]. The shuffle law is not constant on conjugacy classes, so we retain matrix norms throughout. By (11) and Proposition 7, the nearby law \(\nu\) has the required Fourier operator bound. We first show that \(\nu^{*8}\) is close to uniform, then compare it with the law of eight independent intervals of \(200d\) shuffles, \(\mu^{*8}=q_d^{*(1600d)}\).