| >>> Level Select <<< |
|
We prove that the Thorp shuffle on $2^d$ cards mixes in $\Theta(d)$ complete shuffles. The full permutation law after $1600d$ shuffles converges to uniform in total variation as $d\to\infty$, uniformly over the initial deck, while a support count gives a lower bound of $2d-O(1)$.
|
|
For the Thorp shuffle on $2^d$ cards, we prove that the worst-start total-variation distance after $32800d$ physical shuffles tends to zero as $d\to\infty$. Combining our fixed-list estimate with the companion Fourier transfer improves this bound to $512d$ shuffles. These results follow from bounds on partially observed permutation laws in random coordinate frames.
|
|
We show how information about partial permutations controls full permutation laws. Let n tend to infinity through multiples of eight. If the images of a uniformly chosen $7n/8$ labels approach the uniform injection law in average total variation, and the sign mean tends to zero, then the product of two independent permutations with the given law converges to uniform on Sn.
|
|
We bound the information remaining after paths of specified cards in the Thorp shuffle on $n=2^d$ cards have been observed. After a fixed number of deterministic coordinate sweeps, the joint endpoint law of further cards is close to uniform on the available positions, on average over the observed paths, provided a fixed positive fraction of labels lies outside both lists. Combined with a Fourier transfer, these bounds give full-deck mixing after $2048d$ physical shuffles.
|
|
Fix half the labels in a Thorp shuffle on $2^d$ positions and reveal their complete trajectories. We prove that, after an explicit absolute number of coordinate sweeps, the conditional permutation of the remaining labels approaches uniform in expected total variation as $d\to\infty$, uniformly in the initial layout. The resulting constructions give full-deck mixing in a constant multiple of d physical shuffles.
|
|
For $N=2^d$ cards, we prove that an absolute number of coordinate sweeps of the Thorp shuffle brings the full permutation law to total-variation distance tending to zero from uniform. The mixing time therefore has optimal order $\Theta(\log N)$ in physical shuffles.
|
|
We prove that the Thorp shuffle on $N=2^d$ labeled cards has full-permutation total-variation mixing time $\Theta(\log N)$ in physical shuffles. An absolute number of coordinate sweeps suffices for the upper bound.
|
|
We prove that an absolute number of coordinate sweeps of the Thorp shuffle on $n=2^d$ positions brings the full permutation to total-variation distance at most $\frac12n^{-5}$ from uniform, uniformly over the initial deck. Thus $O(d)$ physical shuffles suffice, which is optimal in order.
|
|
We prove that the Thorp shuffle on $n=2^d$ cards mixes in $\Theta(d)$ physical shuffles. After a sufficiently large fixed number of coordinate sweeps, the total-variation distance of the full permutation from uniform tends to zero as $d\to\infty$.
|
|
We prove that a fixed number of coordinate sweeps of the Thorp shuffle on $2^d$ cards makes the squared L2 distance of the full permutation density from uniform tend to zero as $d\to\infty$. In particular, the total-variation mixing time is $\Theta(d)$ physical shuffles.
|
|
For coordinate sweeps with near-uniform line laws and line sizes among powers of two in a suitable fixed interval, we prove a Schatten-moment bound after conditioning on any feasible collection of prescribed card trajectories. An analytic transfer to binary sweeps then shows that a fixed number of sweeps mixes the Thorp shuffle on $2^d$ cards in $O(d)$ physical steps, matching the order of the support lower bound.
|
|
We prove a permanent inequality with exponent strictly below two for laws on S4 sufficiently close to uniform and with exactly uniform coordinate marginals. Applied to a four-row recursion, it shows that an absolute number of coordinate sweeps brings the full permutation of the Thorp shuffle on $N=2^d$ cards to total-variation distance tending to zero from uniform as $N\to\infty$. Thus the mixing time has the optimal order $O(\log N)$ in physical shuffles.
|