Schur–Weyl duality for diagonalizing a Markov chain on the hypercube
Persi Diaconis Department of Statistics Department of Mathematics Stanford University Andrew Lin Department of Mathematics Stanford University Arun Ram Department of Mathematics University of Melbourne · 2025
Read Schur–Weyl duality for diagonalizing a Markov chain on the hypercube by Persi Diaconis Department of Statistics Department of Mathematics Stanford University Andrew Lin Department of Mathematics Stanford University Arun Ram Department of Mathematics University of Melbourne (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-2512-23285.txt.
Introduction
Persi Diaconis, Andrew Lin, and Arun Ram diagonalize a slow-mixing Markov chain on binary strings. The chain wanders over all strings of a fixed length and takes a long time to forget its starting point, so sharp convergence rates matter. The authors bring in the machinery of algebraic combinatorics: representation theory, Murphy elements, and above all Schur-Weyl duality. That duality relates the symmetries of permuting coordinates to those of rotating the space. From it they construct an orthonormal basis of eigenfunctions, which delivers sharp convergence rates.
Catalog record
| CREATOR | Persi Diaconis Department of Statistics Department of Mathematics Stanford University Andrew Lin Department of Mathematics Stanford University Arun Ram Department of Mathematics University of Melbourne |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 144 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-23285
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Schur–Weyl duality for diagonalizing a Markov chain on the hypercube Persi Diaconis Department of Statistics Department of Mathematics Stanford University Andrew Lin Department of Mathematics Stanford University Arun Ram Department of Mathematics University of Melbourne Abstract We show how the tools of modern algebraic combinatorics – representation theory, Murphy elements, and particularly Schur–Weyl duality – can be used to give an explicit orthonormal basis of eigenfunctions for a “curiously slowly mixing Markov chain” on the space of binary n n -tuples. The basis is used to give sharp rates of convergence to stationarity. 1 Introduction In [ DLR25 ] , we studied a “curiously slowly mixing Markov chain” on C_{2}^{n}=\{(x_{1},\ldots,x_{n}):x_{i}\in\{0,1\}\} . Started at the all-zeros state, this chain mixes in a bounded number of steps, no matter how large n is, in both the usual \ell^{1} and \ell^{2} distances. From more general starts, order \log n steps always suffice for \ell^{1} , while order \frac{n}{\log n} steps are required for \ell^{2} from most starts. Our initial analysis was hampered by not being able to orthogonally diagonalize the chain. Recently, we succeeded in using tools of algebraic combinatorics to find an orthonormal basis of eigenvectors. This lets us do more refined analysis. The Markov chain in question is the “Burnside process,” a broadly useful procedure for sampling a uniform orbit of a finite group acting on a finite set. This chain has resisted analysis, even in very special cases, and the present step forward seems like a breakthrough. Let \mathfrak{X} be a finite set and G a finite group acting on \mathfrak{X} . The action splits \mathfrak{X} into disjoint orbits \mathfrak{X}=\mathcal{O}_{1}\cup\mathcal{O}_{2}\cup\cdots\cup\mathcal{O}_{Z}. The Burnside process gives a way of choosing a uniformly distributed orbit (in contrast to a uniformly distributed element of \mathfrak{X} ), which is a basic task for Pólya’s problems of enumeration under symmetry. It consists of two steps: • From x\in\mathfrak{X} , choose s uniformly from the set G_{x}=\{s:x^{s}=x\} . • From s\in G , choose y uniformly from the set \mathfrak{X}_{s}=\{y:y^{s}=y\} . The chance of moving from x to y in one step of the chain is K(x,y)=\frac{1}{|G_{x}|}\sum_{s\in G_{x}\cap G_{y}}\frac{1}{|\mathfrak{X}_{s}|}. This is an ergodic, reversible Markov chain on \mathfrak{X} with stationary distribution \pi(x)=\frac{1}{Z|\mathcal{O}_{x}|}, where Z is the total number of orbits and \mathcal{O}_{x} is the orbit containing x . Thus, running the chain and simply recording the current orbit gives a Markov chain on orbits with a uniform stationary distribution. Examples on huge state spaces in various applications (see for instance [ BD24 ] , [ DH25 ] , [ DZ26 ] ) empirically indicate extremely rapid mixing, but it appears difficult to prove this in any of these instances. Instead, a “simplest example” previously studied in the sequence of papers [ Jer93 ] , [ Dia05 ] , [ DZ21 ] , [ DLR25 ] is instructive. Let the set \mathfrak{X}=C_{2}^{n} be the binary n -tuples, and let the symmetric group G=S_{n} act by permuting coordinates. Thus, the orbit decomposition is \mathfrak{X}=\mathcal{O}_{0}\cup\mathcal{O}_{1}\cup\cdots\cup\mathcal{O}_{n},\quad\text{where}\quad\mathcal{O}_{i}=\{x\in C_{2}^{n}:|x|=i\}, and where |x| denotes the number of ones in x . The two steps of the Burnside process can be explicitly described in this case: • From x\in C_{2}^{n} , choose s\in S_{n} with x^{s}=x uniformly. This is easy to do, since G_{x}=S_{i}\times S_{n-i} for i=|x| , where we permute the zeros and the ones each among themselves. • From s\in S_{n} , choose y\in C_{2}^{n} with y^{s}=y . This too is easy to do: simply break s into its disjoint cycles, color each one 0 or 1 with probability \frac{1}{2} , and install the values according to s . The resulting Markov transition matrix K(x,y) has a simple description, given in [ DLR25 , Lemma 3.1] , and its stationary distribution is \pi(x)=\frac{1}{(n+1)\binom{n}{|x|}} . Its eigenvalues can be described as follows ( [ DLR25 , Theorem 1.2] ): we have \displaystyle\beta_{0}=1, \displaystyle\beta_{k}=\frac{\binom{2k}{k}^{2}}{2^{4k}}\text{ with multiplicity }\binom{n}{2k}\text{ for }1\leq k\leq\left\lfloor\frac{n}{2}\right\rfloor, (1.1) \displaystyle 0\text{ with multiplicity }2^{n-1}. To describe convergence of the Markov chain, define the \ell^{1} or total variation distance ||K_{x}^{\ell}-\pi||_{\text{TV}}=\frac{1}{2}\sum_{y\in C_{2}^{n}}|K^{\ell}(x,y)-\pi(y)|, and the \ell^{2} or chi-square distance \chi_{x}^{2}(\ell)=\sum_{y}\frac{(K^{\ell}(x,y)-\pi(y))^{2}}{\pi(y)}=\left|\left|\frac{K^{\ell}}{\pi}-1\right|\right|^{2}_{2}. The usual route to bounding convergence is to “bound \ell^{1} by \ell^{2} and then bound \ell^{2} using eigenvalues.” More precisely, 4||K_{x}^{\ell}-\pi||_{\text{TV}}^{2}\leq\chi_{x}^{2}(\ell)=\sum_{\beta_{i}\neq 1}f_{i}^{2}(x)\beta_{i}^{2\ell}, (1.2) where the sum runs over all nontrivial eigenvalues of K and \{f_{i}(x)\} is an orthonormal basis of eigenvectors of eigenvalues \beta_{i} . In [ DLR25 ] , we found an elegant basis of eigenvectors (which is no simple task in problems with highly degenerate eigenspaces), but, alas, these eigenvectors were not orthogonal and so we were forced to work with the average \ell^{2} distance \chi_{\text{avg}}^{2}(\ell)=\sum_{x}\pi(x)\chi_{x}^{2}(\ell)=\sum_{\beta_{i}\neq 1}\beta_{i}^{2\ell}. The explicit form of the eigenvalues and multiplicities from Section 1 was enough to prove sharp cutoff for \chi_{\text{avg}}^{2}(\ell) at \ell=\frac{\log 2}{2}\frac{n}{\log n} . This could then be refined to show ( [ DLR25 , Theorem 1.1] ) that \chi_{x}^{2}(\ell) tends to zero for all x if \ell\geq(1+\varepsilon)\frac{\log 2}{2}\frac{n}{\log n} , and also that \chi_{x}^{2}(\ell) tends to \infty for “most x ” after order \frac{n}{\log n} steps. In contrast, previous analysis ( [ Dia05 ] , [ DZ21 ] ) had shown that the chain started at the all-zeros state mixes in a bounded number of steps in both \ell^{1} and \ell^{2} . This leaves the natural question “how does the mixing time get from bounded to order \frac{n}{\log n} ?” For example, what happens if the chain starts at the state (0,\cdots,0,1) , or similarly a state with i ones with i constant or slowly growing with n ? More detailed descriptions and extensive references to previous work may be found in the introduction to [ DLR25 ] . Here, we now turn to a description of the present paper. Set \ell^{2}(\pi)=\{f:C_{2}^{n}\to\mathbb{C}\} with the inner product \langle f,g\rangle=\sum_{x}f(x)\overline{g(x)}\pi(x) . The transition matrix K(x,y) operates on \ell^{2} as Kf(x)=\sum_{y}K(x,y)f(y). By construction, K is a self-adjoint operator which commutes with the action of S_{n} on \ell^{2}(\pi) (meaning that for all x,y\in C_{2}^{n} and s\in S_{n} , we have K(x,y)=K(x^{s},y^{s}) ). So as a representation of S_{n} , \ell^{2}(\pi) decomposes as a direct sum of irreducible representations of S_{n} . Schur’s lemma implies that the operator K sends isotypic pieces of this decomposition into themselves, and decomposing further into eigenspaces of K refines this. (See [ Dia88 ] – particularly Section 7 for material on the symmetric group – or [ Jam78 ] for this classical approach.) One result of our development is a complete description of how the isotypic pieces decompose relative to the eigenvalue multiplicities ( Corollary 4.3 below). The Lie algebra \mathfrak{sl}_{2}(\mathbb{C}) also acts on \ell^{2}(\pi) (explained in Section 4 ), commuting with the action of S_{n} . Schur–Weyl duality implies that \mathfrak{sl}_{2} and S_{n} are each the full centralizer of the other. One main accomplishment of the present paper is to refine these symmetry decompositions into a “magical” orthonormal basis of \ell^{2}(\pi) , which does not depend on K(x,y) . Thus this basis is available for other Markov chains on C_{2}^{n} that commute with the action of S_{n} , some of which are compiled in [ DLR25 , Section 6.1] . We then subsequently use properties of the transition matrix to transform this basis into an orthonormal basis of eigenvectors of K , described in