Section 16.1.3 -- adjacent transpositions lower bound

The lazy random adjacent transpositions shuffle of a deck of $n$ cards does nothing with probability $\tfrac12$ and otherwise swaps the cards in a uniformly chosen pair of neighbouring positions $(i,i+1)$: the identity carries probability $\tfrac12$ and each of the $n-1$ adjacent transpositions probability $1/\bigl(2(n-1)\bigr)$. Its stationary distribution is uniform. The mixing time $t_{\mathrm{mix}}$ is the first time $t$ at which $\max_x\|P^t(x,\cdot)-\mathrm{unif}\|_{TV}\le\tfrac14$, with $\|\mu-\nu\|_{TV}=\max_A|\mu(A)-\nu(A)|$ the total variation distance.

The theorem (§16.1.3 of Levin–Peres–Wilmer) asserts: for every $n\ge2$,

Order $n^3$ steps are necessary, matching the $n^3\log n$ upper bound up to the logarithm. The obstruction is transport: a single card performs a random walk on the $n$ positions that advances only when its own position is selected, so moving it across the deck takes order $n\cdot n^2$ steps.