Mixing time upper bound for the uniformized Rosenthal walk on the special orthogonal groups

2011/10/25 by Yunjiang Jiang, Jiang, Yunjiang
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Representation Theory (math.RT) #math.CO #math.PR #math.RT

paper · pdf · doi:10.48550/arxiv.1110.5394

arxiv created 2011/10/25 · arxiv updated 2011/10/26

Abstract

We prove that a uniformized variant of both the Rosenthal walk \citeRosenthal and the Kac random walk \citeKac on SO(n) mixes in \cO(n³) steps in total variation distance. The proof also extends easily to Rosenthal walk with fixed angle θ≠ π. To the best of our knowledge, this is the first polynomial time bound for both walks. The techniques employed are mainly from representation theory of SO(n). But a crucial new ingredient is the interpretation of the Fourier coefficients of the character ratio as counting the number of particle cascade paths arising from the classical branching rules.

Related

• On the Mixing Time of Kac's Walk and Other High-Dimensional Gibbs\n Samplers with Constraints
• Kac's Walk on n-sphere mixes in nlog n steps
• Mixing on Generalized Associahedra
• Cutoff Phenomenon and Limiting Profile of a Random Walk on the Symmetric Group
• A Coupling Argument for the Random Transposition Walk