Mixing on Generalized Associahedra

2024/08/10 by William S. C. Chang, Colin Defant, Chang, William +3
Computer Science · #Speech and Audio Processing

paper · pdf · doi:10.48550/arxiv.2408.05611

Abstract

Eppstein and Frishberg recently proved that the mixing time for the simple random walk on the 1-skeleton of the associahedron is O(n³log³ n). We obtain similar rapid mixing results for the simple random walks on the 1-skeleta of the type-B and type-D associahedra. We adapt Eppstein and Frishberg's technique to obtain the same bound of O(n³log³ n) in type B and a bound of O(n¹³ log² n) in type D; in the process, we establish an expansion bound that is tight up to logarithmic factors in type B.

Related

• Mixing time upper bound for the uniformized Rosenthal walk on the special orthogonal groups
• On the Mixing Time of Kac's Walk and Other High-Dimensional Gibbs\n Samplers with Constraints
• On mixing times for stratified walks on the d-cube
• The random walk on upper triangular matrices over ℤ/m ℤ
• Kac's Walk on n-sphere mixes in nlog n steps