Kac’s walk on n-sphere mixes in n log n steps
MetadataShow full item record
CitationPillai, Natesh S., and Aaron Smith. "Kac’s walk on n-sphere mixes in n log n steps." The Annals of Applied Probability 27, no. 1 (2017): 631-650.
AbstractDetermining the mixing time of Kac's random walk on the sphere Sn−1 is a long-standing open problem. We show that the total variation mixing time of Kac's walk on Sn−1 is between 12nlog(n) and 200nlog(n). Our bound is thus optimal up to a constant factor, improving on the best-known upper bound of O(n5log(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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:34390103
- FAS Scholarly Articles