KAC'S WALK ON n-SPHERE MIXES IN n log n STEPS

• 成果类型: Article
• 署名作者: Pillai, Natesh S.; Smith, Aaron
• 署名单位: Harvard University; University of Ottawa
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/16-AAP1214
• 发表日期: 2017
• 页码: 631-650
• 关键词: spectral gap; master equation

摘要

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 1/2n 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 Jiang [Ann. AppL Probab. 22 (2012) 1712-1727]. Our main tool is a non-Markovian coupling recently introduced by the second author in [Ann. Appl. Probab. 24 (2014) 114-130] for obtaining the convergence rates of certain high dimensional Gibbs samplers in continuous state spaces.