How many shuffles does a deck of cards need? The question created the modern theory of mixing times: Diaconis and Shahshahani's analysis of random transpositions (1981) and the Bayer–Diaconis "seven shuffles suffice" analysis of the riffle shuffle (1992) are its founding results. Chapters 8 and 16 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) treat the four standard shuffles: random transpositions (pick two cards, swap them), the riffle shuffle (cut and interleave, the Gilbert–Shannon–Reeds model), random adjacent transpositions, and the -reversal chain of segment reversals — the last motivated by genome rearrangement, where a chromosome evolves by reversing segments and the mixing time measures evolutionary distance ("from shuffling cards to shuffling genes").
All four chains are random walks on a symmetric group; decks are encoded as in Mission III, an arrangement being a permutation with position on top. Random transpositions have increment distribution , . The lazy adjacent-transposition walk puts mass on the identity and on each . One inverse riffle shuffle assigns each card an independent uniform bit and moves the cards labeled to the top, preserving relative order; the (forward) riffle shuffle is its time reversal, given by transposing the inverse-shuffle matrix (the stationary distribution being uniform). The -reversal chain on circular arrangements indexed by picks a position and a length uniformly and reverses the segment .
for random transpositions on cards (Corollary 8.10), formalized as: for every there is with for all .
Proposition 8.11 (random transpositions lower bound , via fixed points); Proposition 8.13 (riffle shuffle: ); Proposition 8.14 (riffle shuffle: for large , by the counting bound of Mission IV); the random adjacent transpositions upper bound for large (§16.1.2, display (16.4)) and lower bound (§16.1.3, by following a single card); and Proposition 16.2 (the -reversal chain with satisfies , via conserved adjacencies).
The results. Random transpositions at (the constant here is not sharp; the sharp constant is part of the celebrated Diaconis–Shahshahani cutoff) and riffle at are the emblematic mixing results outside of spin systems; the riffle bound is the mathematical content of "seven shuffles suffice" for . The adjacent-transposition walk at order is the basic example where geometry (diameter ) forces polynomial mixing. The -reversal lower bound is the quantitative starting point of the biological application.
Formalizing them. Random walks on symmetric groups and their mixing are entirely absent from Mathlib; so are the combinatorial devices these proofs run on — the Broder stopping time, rising sequences and the Eulerian-number analysis of riffle shuffles, single-card projections, conserved adjacencies. The riffle shuffle formalization via bit strings and the stable-sort permutation Tuple.sort gives a clean combinatorial model reusable for the cutoff analysis of Mission XI.
Corollary 8.10's route is the Broder strong stationary time: mark cards under a card-and-position scheme and prove that, conditioned on the marked set and its positions, the marked cards are uniformly ordered — an exchangeability induction on top of Mission III's stopping-rule framework; then the coupon-collector-style tail with an extra factor. Proposition 8.11 requires the fixed-point statistic: the expected number of untouched cards after transpositions and a second-moment bound, fed into Proposition 7.8. The riffle upper bound runs through inverse shuffles: after inverse shuffles the deck is a uniform stable sort of -bit labels, and mixing reduces to the birthday problem for labels; formalizing "distinct labels imply uniform order" is the crux. The -reversal lower bound needs a second-moment argument for the number of conserved adjacencies with the exact variance bookkeeping of the book. Throughout, the walk-on-group conventions (left vs right increments, forward vs inverse shuffle) are the classic source of silent errors; the formal statements pin them.
All chains are explicit matrices on Equiv.Perm (Fin n) (or Equiv.Perm (ZMod n) for the circular -reversal chain); increments act on the left, matching Mission I's group-walk convention. The riffle shuffle is defined as the transpose-reversal of the explicit inverse-riffle matrix — the two have equal distance to uniformity by Lemma 4.13 (Mission II), which a solver may use rather than re-derive. Asymptotic statements (, "for sufficiently large ") are spelled out with explicit quantifiers; upper bounds carry a where integer rounding requires it. The -reversal family takes the length function as a hypothesis-carrying parameter with , and its lower bound is a genuine limit statement (Tendsto, distance to stationarity tending to ).
Welcome contributions: exchangeability and projection lemmas for deck chains; Eulerian/rising-sequence counting; the single-card chain projection (reused for Mission XI's cutoff examples).
namespace MarkovMixing
/-- **Corollary 8.10** (LPW), the capstone of Chapter 8: the random
transpositions shuffle on `n` cards mixes in at most `(2 + o(1)) n log n`
steps. -/
theorem random_transpositions_mixing (δ : ℝ) (hδ : 0 < δ) :
∃ N : ℕ, ∀ n : ℕ, N ≤ n →
(tMix (randomTranspositions n) (uniformDist (Equiv.Perm (Fin n))) : ℝ) ≤
(2 + δ) * n * Real.log n := by
sorry
end MarkovMixing
The random transpositions shuffle of a deck of cards picks two cards independently and uniformly at random and swaps them (doing nothing when the same card is picked twice): the identity is applied with probability and each transposition with probability . Its stationary distribution is uniform over all orderings. The mixing time is the first time at which , where is the law of the deck after shuffles from ordering and is the total variation distance.
The theorem (Corollary 8.10 of Levin–Peres–Wilmer, the capstone of Chapter 8) asserts: for every there is an such that for all ,
Random transpositions mix in at most steps. The book's proof constructs a strong stationary time by the marking scheme of Broder; the matching lower bound of order is the companion theorem of this mission.
No open leaves. Every sub-goal is proved or awaiting decomposition.