Kac’s walk on \(n\)-sphere mixes in \(n\log n\) steps. (English) Zbl 1364.60056

Pillai, Natesh S.; Smith, Aaron

Ann. Appl. Probab. 27, No. 1, 631-650 (2017).

Summary: 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 \(\frac12n\log(n)\) and \(200n\log(n)\) for all \(n\) sufficiently large. 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 Y. Jiang [ibid. 22, No. 4, 1712–1727 (2012; Zbl 1248.60004)]. Our main tool is a “non-Markovian” coupling recently introduced by the second author in [ibid. 24, No. 1, 114–130 (2014; Zbl 1293.60072)] for obtaining the convergence rates of certain high dimensional Gibbs samplers in continuous state spaces.

MSC:

60G50	Sums of independent random variables; random walks
60J10	Markov chains (discrete-time Markov processes on discrete state spaces)
60J20	Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)

Keywords:

Kac’s random walk; Markov chain; Gibbs sampler; coupling; mixing times

Citations:

Zbl 1248.60004; Zbl 1293.60072