Kac's Walk on n-sphere mixes in nlog n steps

2015/07/30 by Pillai, Natesh S., Smith, Aaron · 1 citation
#60J05 #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1507.08554

Abstract

Determining the mixing time of Kac's random walk on the sphere S^n-1 is a long-standing open problem. We show that the total variation mixing time of Kac's walk on S^n-1 is between (1)/(2) n log(n) and 200 n log(n). Our bound is thus optimal up to a constant factor, improving on the best-known upper bound of O(n⁵ log(n)²) 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.

Cited by

• A universal cutoff phenomenon for mean-field exchange models

Related

• On the Mixing Time of Kac's Walk and Other High-Dimensional Gibbs\n Samplers with Constraints
• Mixing time upper bound for the uniformized Rosenthal walk on the special orthogonal groups
• Extremal points of high dimensional random walks and mixing times of a Brownian motion on the sphere
• On mixing times for stratified walks on the d-cube
• Three steps mixing for general random walks on the hypercube at criticality