2025/11/02 by Michael Howes, Howes, Michael · 1 citation
Mathematics · Computer Science · #Markov Chains and Monte Carlo Methods #Random Matrices and Applications #Bayesian Methods and Mixture Models
paper · pdf · doi:10.48550/arxiv.2511.01058
This article gives sharp estimates for the mixing time of the Burnside process for Sylow p-double cosets in the symmetric group Sn. This process is a Markov chain on Sn which can be used to uniformly sample Sylow p-double cosets. The analysis applies when n = pk with p prime and k < p. The main result describes the limit profile of the distance to the stationary distribution as p goes to infinity. From the limit profile, we get the following two corollaries. First, if k remains fixed as p → ∞, then order p steps are necessary and sufficient for mixing and cut-off does not occur. Second, if k → ∞ as p → ∞, then cut-off occurs at p log k with a window of size p. The limit profile is derived from explicit upper and lower bounds on the distance between the Burnside process and its stationary distribution. These non-asymptotic bounds give very accurate approximations even for p as small as 11.