Corollary 8.10 -- random transpositions mix in $(2+o(1))\,n\log n$

The random transpositions shuffle of a deck of $n$ 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 $1/n$ and each transposition with probability $2/n^2$. Its stationary distribution is uniform over all $n!$ orderings. The mixing time $t_{\mathrm{mix}}$ is the first time $t$ at which $\max_x\|P^t(x,\cdot)-\mathrm{unif}\|_{TV}\le\tfrac14$, where $P^t(x,\cdot)$ is the law of the deck after $t$ shuffles from ordering $x$ and $\|\mu-\nu\|_{TV}=\max_A|\mu(A)-\nu(A)|$ is the total variation distance.

The theorem (Corollary 8.10 of Levin–Peres–Wilmer, the capstone of Chapter 8) asserts: for every $\delta>0$ there is an $N$ such that for all $n\ge N$,

Random transpositions mix in at most $(2+o(1))\,n\log n$ steps. The book's proof constructs a strong stationary time by the marking scheme of Broder; the matching lower bound of order $\tfrac12 n\log n$ is the companion theorem of this mission.