Enumerative theory for the Tsetlin library

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of simplicial complexes (05E45) Symmetric groups (20B30) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Review text

The paper presents a mathematically rigorous investigation into the enumerative theory of the Tsetlin library, a classical Markov chain on the symmetric group \( S_n \), where the stationary distribution follows the Luce model. The authors resolve several longstanding open problems concerning the distribution of specific subsets of the chain, such as the top \( k \) and bottom \( k \) elements, while embedding their findings in the broader context of hyperplane arrangements and related stochastic processes.\N\NAt the heart of the authors' provided analysis is the stationary distribution \( \pi(\sigma) \), defined as\N\[\N\pi(\sigma) = \frac{\theta_{\sigma(1)}}{w_n} \cdot \frac{\theta_{\sigma(2)}}{w_n - \theta_{\sigma(1)}} \cdots \frac{\theta_{\sigma(n)}}{\theta_{\sigma(n)}},\N\]\Nwhere \( w_n = \sum_{i=1}^n \theta_i \), and \( \{\theta_i\} \) are weights associated with the items. This representation captures the Luce model, a weighted sampling scheme without replacement. The authors meticulously derive properties of this distribution, focusing on questions of practical and theoretical significance, such as the probability of fixed points, cycles, inversions, and subsequences. The obtained results extend beyond the classical Tsetlin library to encompass the Bidigare-Hanlon-Rockmore walks on chambers of hyperplane arrangements.\N\NThe major mathematical strength of the paper lies in: rigorously deriving the distributions of the top \( k \) elements under the Luce model and, in Theorem 3.1, establishing bounds on the infinity distance \( d_\infty(P, Q) \) between the true distribution \( P \) and an independent product approximation \( Q \), given by\N\[\NQ(\sigma_1, \sigma_2, \ldots, \sigma_k) = \prod_{i=1}^k \theta_{\sigma_i},\N\]\Nwhere \( \{\sigma_i\} \) are drawn independently. The bound,\N\[\Nd_\infty(P, Q) \leq 1 - \exp\left(-2 \sum_{j=1}^{k-1} \theta_{(j)} \right),\N\]\Nwhere \( \theta_{(j)} \) are the ordered weights, provides a precise characterization of how closely the product measure approximates the true distribution, especially for small \( k \). Furthermore, in Theorem 3.2, the asymptotic behavior of the total variation distance under triangular arrays of weights is considered, showing that\N\[\N\|P - Q\|_{\text{TV}} \sim 1 - e^{-\lambda},\N\]\Nwhere \( \lambda \) is a parameter depending on the squared weights. The results are complemented by examples providing useful details about the convergence properties and also highlighting scenarios where the product measure fails to approximate the true distribution adequately.\N\NThe paper's treatment of the bottom \( k \) elements in Section 4 is equally compelling. Indeed, by considering the reverse of the Tsetlin chain, the authors derive conditions under which the sequence of permutations \( \{\sigma_n\} \) converges in law. Using tools such as exponential random variables and their order statistics, the authors establish that convergence occurs if and only if the series\N\[\Nf(x) = \sum_{i=1}^\infty e^{-\theta_i x}\N\]\Nsatisfies \( x_0 < \infty \) and \( f(x_0) = \infty \), where \( x_0 = \inf \{x : f(x) < \infty\} \). It is worth mentioning that the latter condition reveals dependencies on the growth rate of the weights \( \{\theta_i\} \), underscoring the intricate structure of the stationary distribution. The integral representation of the limiting joint distributions further ehnances the provided theoretical contributions, as demonstrated by the example of Sukhatme weights.\N\NThe authors also extend their framework to hyperplane walks, particularly the Bidigare-Hanlon-Rockmore walks, which generalize the Tsetlin library to higher-dimensional settings. The stationary distribution in these models is characterized as the outcome of a weighted sampling without replacement procedure, akin to the Luce model in lower dimensions. Since this latter point is a key contribution, let us provide more details about the related derivations. Indeed, the generalization builds on the foundational principles of the Tsetlin library while introducing substantial structural complexity. Let us recall that a hyperplane arrangement \( A \) in \( \mathbb{R}^d \) is defined as a finite collection of affine hyperplanes \( \{H_1, H_2, \ldots, H_k\} \), which partition the space into chambers and faces. Chambers correspond to the connected components of the complement of the union of hyperplanes, while faces are subsets of these chambers that lie on one or more hyperplanes. The Markov chain associated with the BHR framework operates on the set of chambers \( C \), with the transition mechanism determined by the underlying hyperplane geometry and a set of probabilistic weights. Accordingly, the transition probabilities of the BHR walk are defined using the notion of *Tits projection*. For a chamber \( C \) and a face \( F \), the projection \( \text{PROJ}(C \to F) \) identifies the unique chamber \( C' \) adjacent to \( F \) that is closest to \( C \), measured by the minimal number of hyperplanes crossed. This projection operator forms the basis of the chain's transitions. If \( w_F \geq 0 \) are the weights assigned to each face \( F \), normalized such that \( \sum_{F} w_F = 1 \), the transition kernel \( \kappa(C, C') \) is given by\N\[\N\kappa(C, C') = \sum_{F : \text{PROJ}(C \to F) = C'} w_F,\N\]\Nwhere the summation runs over all faces \( F \) for which \( C' \) is the projected chamber. The resulting Markov chain transitions from a chamber \( C \) by selecting a face \( F \) with probability \( w_F \), projecting \( C \) onto \( F \), and landing in the corresponding chamber \( C' \).\N\NThe stationary distribution \( \pi(C) \) of this Markov chain, which generalizes the Luce measure to higher-dimensional settings, is uniquely determined under the condition that the weights \( \{w_F\} \) are separating, hence implying that the weights are not all concentrated on faces contained within a single hyperplane. Within such a context, the authors rigorously prove that the stationary distribution exists and is unique under this condition, satisfying the detailed balance equation\N\[\N\pi(C) \kappa(C, C') = \pi(C') \kappa(C', C),\N\]\Nand they show that \( \pi(C) \) is proportional to the product of the weights of the faces encountered in a specific weighted sampling scheme, a result which is formally as follows: to generate a sample from \( \pi(C) \):\N\N1. Faces are sequentially sampled without replacement, with probabilities proportional to their weights relative to the remaining set.\N\N2. A starting chamber \( C_0 \) is projected iteratively through the sampled faces, in reverse order, until the final chamber is obtained.\N\NHence, if \( F_1, F_2, \ldots, F_m \) are the sampled faces, the stationary distribution \( \pi(C) \) is given by\N\[\N\pi(C) \propto \prod_{i=1}^m w_{F_i},\N\]\Nwhere the product incorporates the weighted contribution of each face encountered during the projection process.\N\NMoreover, for the special case of the braid arrangement, where the hyperplanes are given by \( H_{ij} = \{x \in \mathbb{R}^d : x_i = x_j\} \) for \( 1 \leq i < j \leq d \), the chambers correspond to permutations of the elements \( \{1, 2, \ldots, d\} \), and the Tits projection reduces to the act of sorting cards according to specified blocks. When the weights \( w_F \) are chosen to correspond to probabilities associated with moving a specific card to the top, the stationary distribution reduces to the classical Luce measure on permutations, illustrating the natural embedding of the Tsetlin library as a one-dimensional case of the BHR framework.\N\NIt is also interesting to note that the authors also show the structural parallels between the stationary distribution in hyperplane walks and weighted sampling without replacement, which underpins the extension of classical combinatorial models to higher dimensions while preserving probabilistic coherence. Associated to the latter, the authors underscore the universality of hyperplane walks by highlighting their applications beyond the braid arrangement. Examples include the Boolean arrangement, where chambers correspond to orthants in \( \mathbb{R}^d \), and graphical arrangements derived from finite graphs. In each case, the stationary distribution encapsulates a weighted sampling process, demonstrating the versatility of the framework.\N\NFor the sake of completeness, the paper could benefit from further elaboration, particularly providing more details w.r.t. the proofs of key theorems, e.g. Th. 4.2, in the handling of tightness conditions for \( \{\sigma_n\} \).\N\NSumming up, the paper represents a substantial contribution to the study of the Tsetlin library and its generalizations. By resolving enumerative questions and embedding them in a broader mathematical framework, the authors provide a unified perspective on these Markov chains. The results are mathematically rigorous, insightful, and also characterized by potentially being useful for future applications, particularly in understanding complex stochastic systems and their stationary behavior.

Recommendations

Cites work

Cited in

(1)

Infinite size-biased orders

This page was built for publication: Enumerative theory for the Tsetlin library

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6565648)