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

Michael Howes · 2025

Read Limit profiles and cutoff for the Burnside process on Sylow double cosets by Michael Howes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01058.txt.

Introduction

Michael Howes studies how quickly a random sampling process settles into uniformity. The Burnside process is a Markov chain on the symmetric group used to sample Sylow p-double cosets evenly. Its mixing time tells users how many steps to run before trusting the output.

Howes derives sharp estimates in the regime where the group size is a prime times a smaller factor. The main result gives the limit profile of the distance to the stationary distribution as the prime grows. Two regimes emerge. With the smaller factor fixed, order p steps are necessary and sufficient, and no sharp cutoff occurs. If that factor also grows, a cutoff appears at a stated time, with a window of size p. The bounds stay accurate even for primes as small as eleven.

Catalog record

CREATORMichael Howes
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-01058

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Limit profiles and cutoff for the Burnside process on Sylow double cosets Michael Howes Abstract This article gives sharp estimates for the mixing time of the Burnside process for Sylow p p -double cosets in the symmetric group S n S_{n} . This process is a Markov chain on S n S_{n} which can be used to uniformly sample Sylow p p -double cosets. The analysis applies when n = p ​ k n=pk with p p prime and k < p k<p . The main result describes the limit profile of the distance to the stationary distribution as p p goes to infinity. From the limit profile, we get the following two corollaries. First, if k k remains fixed as p → ∞ p\to\infty , then order p p steps are necessary and sufficient for mixing and cutoff does not occur. Second, if k → ∞ k\to\infty as p → ∞ p\to\infty , then cutoff occurs at p ​ log ⁡ k p\log k with a window of size p 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 p as small as 11 11 . 1 Introduction and main results The Burnside process is a Markov chain Monte Carlo algorithm for uniformly sampling orbits from a group action [ 16 ] . Recent works have shown empirically that the Burnside process mixes quickly in a number of complex and interesting examples [ 3 , 8 , 14 ] . This paper is perhaps the first to provide a sharp analysis of the mixing time of an instance of the Burnside process for double cosets. To describe the Burnside process, let \mathscr{X} be a finite set and let G be a finite group acting on \mathscr{X} with x^{g} denoting the image of g acting on x . The set {\mathscr{X}} splits into disjoint orbits {\mathscr{X}}=\mathscr{O}_{x_{1}}\sqcup\mathscr{O}_{x_{2}}\sqcup\cdots\sqcup\mathscr{O}_{x_{Z}}, where \mathscr{O}_{x}=\{x^{g}:g\in G\} is the orbit containing x and Z is the number of orbits. The Burnside process is a Markov chain on {\mathscr{X}} with stationary distribution \pi(x)=\frac{1}{Z|\mathscr{O}_{x}|} . Thus, sampling X from \pi and reporting the orbit containing X gives a way of uniformly sampling an orbit. Furthermore, taking many steps of the Burnside produces random elements of {\mathscr{X}} that are approximately distributed according to \pi . The Burnside process transitions from x to y according to the following two-step procedure: 1. From x\in\mathscr{X} , choose g uniformly from the set G_{x}=\{g\in G:x^{g}=x\} . 2. Given g , choose y uniformly from the set {\mathscr{X}}^{g}=\{y\in{\mathscr{X}}:y^{g}=y\} . The probability of transitioning from x to y is thus given by the following transition kernel P(x,y)=\frac{1}{|G_{x}|}\sum_{g\in G_{x}\cap G_{y}}\frac{1}{|{\mathscr{X}}^{g}|}, (1) The kernel P is ergodic and reversible with respect to \pi and thus \pi is the unique stationary distribution of P [ 16 , Theorem 2.1] . For x\in{\mathscr{X}} and t\geq 1 we will write P^{t}_{x} for the distribution on {\mathscr{X}} that corresponds to starting at x and taking t steps of the Burnside process. That is for any y\in{\mathscr{X}} , P_{x}^{1}(y)=P_{x}(y)=P(x,y)\quad\text{and}\quad P_{x}^{t}(y)=\sum_{z\in{\mathscr{X}}}P^{t-1}_{x}(z)P_{z}(y). This paper focuses on a particular case of the Burnside process called the Sylow–Burnside process . In this example, {\mathscr{X}}=S_{n} is the symmetric group of degree n and G is the product group H\times H where H\subseteq S_{n} is a Sylow p -subgroup with p prime. The product H\times H acts on S_{n} by \sigma^{h,g}=h^{-1}\sigma g. Under this group action the orbits are Sylow p -double cosets and the Sylow–Burnside process can be used to uniformly sample double cosets. Background and motivation for studying this example is given in Section 2.2 . If P is an ergodic transition kernel, then the distribution P_{x}^{t} converges to \pi as t goes to infinity for any x\in{\mathscr{X}} . To understand how quickly P_{x}^{t} converges to \pi , total variation distance is typically used. The total variation distance between two probability measures \mu and \nu on a finite set {\mathscr{X}} is given by \|\mu-\nu\|_{\mathrm{TV}}=\sup_{A\subseteq{\mathscr{X}}}|\mu(A)-\nu(A)|=\frac{1}{2}\sum_{y\in{\mathscr{X}}}|\mu(x)-\nu(x)|=\sum_{y\in{\mathscr{X}}}(\mu(x)-\nu(x))_{+}. The field of Markov chain mixing is focused on proving upper bounds on \|P^{t}_{x}-\pi\|_{\mathrm{TV}} that depend on both t and parameters of the Markov chain P (such as the size of {\mathscr{X}} ). The worst-case value of \|P^{t}_{x}-\pi\|_{\mathrm{TV}} (as a function of x ) is denoted by d(t) . That is, for t\in\mathbb{N} , \displaystyle d(t) \displaystyle=\max_{x\in{\mathscr{X}}}\|P^{t}_{x}-\pi\|_{\mathrm{TV}}, (2) and d(t)=d(\lfloor t\rfloor) for noninteger t where \lfloor\cdot\rfloor is the floor function. The goal of this paper is to approximate d(t) when P is the transition kernel for the Sylow–Burnside process. The analysis in this paper applies when n=pk with p prime and k<p . The main result is the limit of d(t) as p,t\to\infty jointly. A result of this type is called a limit profile or a cutoff profile . Theorem 1.1 . Suppose p=p_{m} is a diverging sequence of prime numbers, and that k=k_{m} is a sequence of positive integers with k_{m}<p_{m} for all m . Let P be the transition kernel for the Sylow–Burnside process on S_{pk} and let d(t) be as in equation ( 2 ). 1. If k_{m}\equiv k is eventually constant, then for all c\geq 0 , d(cp)\rightarrow 1-(1-e^{-c})^{k}. (3) 2. If k_{m}\to\infty , then for all c\in\mathbb{R} , d(p\log k+cp)\to 1-\exp({-e^{-c}}). (4) Remark 1.2 . 1. Theorem 1.1 describes how fast t must grow as a function of p for d(t) to be small. If k is fixed, then taking t=cp with c large is necessary and sufficient for d(t) to be small. If k diverges with p , then taking t=p\log k+cp with c large is necessary and sufficient for d(t) to be small. 2. Equation ( 4 ) is an example of cutoff [ 9 ] . If t=(1+\varepsilon)p\log k , then d(t) approaches 0 and if t=(1-\varepsilon)p\log k , then d(t) approaches 1. Demonstrating that a Markov chain has cutoff often requires detailed understanding of the Markov chain and its asymptotics. 3. Theorem 1.1 gives the limiting value of \|P^{t}_{\sigma}-\pi\|_{\mathrm{TV}} for the worst-case choice of \sigma\in S_{n} . In the proof of Theorem 1.1 we will see that this worst-case corresponds to setting \sigma=\mathrm{Id} or any other \sigma with |H\sigma H|=|H| . For general \sigma , see the remarks after Theorem 1.3 . The asymptotic results in Theorem 1.1 are a consequence of the following bounds on d(t) . Unlike Theorem 1.1 , Theorem 1.3 contains an explicit error bound that decays super-exponentially as p\to\infty . Theorem 1.3 . Fix p\geq 11 , 1\leq k<p and \sigma\in S_{pk} . If |H\sigma H|=p^{a} , then for all t\geq 1 \left|\|P^{t}_{\sigma}-\pi\|_{\mathrm{TV}}-1+\left(1-\left(1-\frac{1}{p}\right)^{t}\right)^{2k-a}\right|\leq\frac{4p^{4}}{(p-1)!}+\frac{t}{(p-2)!}. (5) In particular, \|P^{t}_{\sigma}-\pi\|_{\mathrm{TV}}\leq 1-\left(1-\left(1-\frac{1}{p}\right)^{t}\right)^{2k-a}+\frac{4p^{4}}{(p-1)!}+\frac{t}{(p-2)!}. (6) Remark 1.4 . 1. Somewhat surprisingly, the right-hand-side of ( 6 ) diverges as t\to\infty for fixed p . However, the function d(t) is non-decreasing and satisfies d(\ell t)\leq(2d(t))^{\ell} [ 19 , Chapter 4] . Thus, if ( 6 ) is used to find t_{0} such that d(t_{0})\leq 1/4 , then for all t\geq t_{0} we will have d(t)\leq 2^{-\lfloor t/t_{0}\rfloor} . It follows that ( 6 ) can be adapted to give bounds on d(t) that go to zero even with fixed p . Note that Theorem 1.1 implies that the smallest such t_{0} is

Read the complete text