2016/05/25 by Natesh S. Pillai, Aaron Smith, Pillai, Natesh S. +1 · 2 citations
Mathematics · #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1605.08122
openalex publication_date 2016/05/25 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Determining the total variation mixing time of Kac's random walk on the\nspecial orthogonal group \SO(n) has been a long-standing open\nproblem. In this paper, we construct a novel non-Markovian coupling for\nbounding this mixing time. The analysis of our coupling entails controlling the\nsmallest singular value of a certain random matrix with highly dependent\nentries. The dependence of the entries in our matrix makes it not-amenable to\nexisting techniques in random matrix theory. To circumvent this difficulty, we\nextend some recent bounds on the smallest singular values of matrices with\nindependent entries to our setting. These bounds imply that the mixing time of\nKac's walk on the group \SO(n) is between C1 n2 and C2\nn4 \log(n) for some explicit constants 0 < C1, C2 < \∞,\nsubstantially improving on the bound of O(n5 \log(n)2) by Jiang. Our\nmethods may also be applied to other high dimensional Gibbs samplers with\nconstraints and thus are of independent interest. In addition to giving\nanalytical bounds on the mixing time, our approach allows us to compute\nrigorous estimates of the mixing time by simulating the eigenvalues of a random\nmatrix.\n