Publication: Kac’s walk on n-sphere mixes in n log n steps
Open/View Files
Date
2017
Authors
Published Version
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Pillai, 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.
Research Data
Abstract
Determining 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.
Description
Other Available Sources
Keywords
Terms of Use
This article is made available under the terms and conditions applicable to Open Access Policy Articles (OAP), as set forth at Terms of Service