$q$-deformations of the Tsetlin library
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911561743859712 |
|---|---|
| author | Ayyer, Arvind Brauner, Sarah de Gier, Jan Schilling, Anne |
| author_facet | Ayyer, Arvind Brauner, Sarah de Gier, Jan Schilling, Anne |
| contents | The Tsetlin library is a random shuffling process on permutations of $n$ letters, where each letter $i$ can be interpreted as a book; book $i$ is brought to the front of the bookshelf with an assigned probability $x_i$. We define a $q$-deformation of the Tsetlin library by replacing the symmetric group action on permutations by the action of the type $A$ Iwahori-Hecke algebra. We compute the stationary distribution and spectrum of this Markov chain by relating it to a Markov chain on complete flags over the finite field vector space $\mathbb{F}_q^n$ and applying techniques from semigroup theory. We prove that for a natural choice of $x_i$ the total variation distance mixing time of the $q$-Tsetlin library on permutations of $n$ is $O(n)$ compared to $Θ(n \log n)$ for the Tsetlin library at $q=1$, which demonstrates a phase transition. We also generalize the $q$-Tsetlin library to words (with repeated letters), and compute its stationary distribution and spectrum. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_21195 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | $q$-deformations of the Tsetlin library Ayyer, Arvind Brauner, Sarah de Gier, Jan Schilling, Anne Combinatorics Probability Representation Theory 60J10, 05A05, 05A15, 20M30 The Tsetlin library is a random shuffling process on permutations of $n$ letters, where each letter $i$ can be interpreted as a book; book $i$ is brought to the front of the bookshelf with an assigned probability $x_i$. We define a $q$-deformation of the Tsetlin library by replacing the symmetric group action on permutations by the action of the type $A$ Iwahori-Hecke algebra. We compute the stationary distribution and spectrum of this Markov chain by relating it to a Markov chain on complete flags over the finite field vector space $\mathbb{F}_q^n$ and applying techniques from semigroup theory. We prove that for a natural choice of $x_i$ the total variation distance mixing time of the $q$-Tsetlin library on permutations of $n$ is $O(n)$ compared to $Θ(n \log n)$ for the Tsetlin library at $q=1$, which demonstrates a phase transition. We also generalize the $q$-Tsetlin library to words (with repeated letters), and compute its stationary distribution and spectrum. |
| title | $q$-deformations of the Tsetlin library |
| topic | Combinatorics Probability Representation Theory 60J10, 05A05, 05A15, 20M30 |
| url | https://arxiv.org/abs/2601.21195 |