Limit profiles and cutoff for the Burnside process on Sylow double cosets

This article gives sharp estimates for the mixing time of the Burnside process for Sylow $p$-double cosets in the symmetric group $S_n$. This process is a Markov chain on $S_n$ 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\to \mathrm{\infty }$, then order $p$ steps are necessary and sufficient for mixing and cut-off does not occur. Second, if $k\to \mathrm{\infty }$ as $p\to \mathrm{\infty }$, 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.