ON THE MIXING TIME OF KAC'S WALK AND OTHER HIGH-DIMENSIONAL GIBBS SAMPLERS WITH CONSTRAINTS

• 成果类型: Article
• 署名作者: Pillai, Natesh S.; Smith, Aaron
• 署名单位: Harvard University; University of Ottawa
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/17-AOP1230
• 发表日期: 2018
• 页码: 2345-2399
• 关键词: master equation; spectral gap; cutoff phenomenon; orthogonal group; markov-chains; monte-carlo; chaos; mixes; matrices; MODEL

摘要

Determining the total variation mixing time of Kac's random walk on the special orthogonal group SO(n) has been a long-standing open problem. In this paper, we construct a novel non-Markovian coupling for bounding this mixing time. The analysis of our coupling entails controlling the smallest singular value of a certain random matrix with highly dependent entries. The dependence of the entries in our matrix makes it not amenable to existing techniques in random matrix theory. To circumvent this difficulty, we extend some recent bounds on the smallest singular values of matrices with independent entries to our setting. These bounds imply that the mixing time of Kac's walk on the group SO(n) is between C(1)n(2) and C(2)n(4) log(n) for some explicit constants 0 < C-1, C-2 < infinity, substantially improving on the bound of O(n(5) log(n)(2)) in the preprint of Jiang [Jiang (2012)]. Our methods may also be applied to other high dimensional Gibbs samplers with constraints, and thus are of independent interest. In addition to giving analytical bounds on the mixing time, our approach allows us to compute rigorous estimates of the mixing time by simulating the eigenvalues of a random matrix.