Kac's Walk on $n$-sphere mixes in $n\log n$ steps

Abstract

Determining the mixing time of Kac's random walk on the sphere ${\mathrm{S}}^{n-1}$ is a long-standing open problem. We show that the total variation mixing time of Kac's walk on ${\mathrm{S}}^{n-1}$ is between $\frac{1}{2}n\log (n)$ and $200n\log (n)$. Our bound is thus optimal up to a constant factor, improving on the best-known upper bound of $O(n^5\log (n{)}^2)$ due to Jiang. Our main tool is a `non-Markovian' coupling recently introduced by the second author for obtaining the convergence rates of certain high dimensional Gibbs samplers in continuous state spaces.