×

A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements. (English) Zbl 0955.60043

The Tsetlin library (or move-to-front scheme) is a Markov chain providing a model for a self-regulating filing system. The states of the chain are the linear arrangements of \(n\) objects. Transitions change a given arrangement by moving some object to the first place. The transition probability for this move depends on the object moved. This chain has been studied by several authors [see J. A. Fill, J. Theor. Probab. 9, No. 1, 113-160 (1996; Zbl 0837.60063)]. In this paper a sequence of generalizations of the Tsetlin library is introduced. For instance: Instead of moving just one object to the front a subset is moved retaining the relative order within the subset. This is the simplest case of a pop shuffle. Further generalizations culminate in a geometric model: a family of Markov chains within a setting of hyperplane arrangements. This family is general enough to include all chains studied in the paper. The central result is the determination of the eigenvalues of the transition matrix together with their multiplicities. This spectral result is used to give upper bounds on the convergence rates of the chain to its stationary distribution.

MSC:

60G50 Sums of independent random variables; random walks
06A07 Combinatorics of partially ordered sets

Citations:

Zbl 0837.60063
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dave Bayer and Persi Diaconis, Trailing the dovetail shuffle to its lair , Ann. Appl. Probab. 2 (1992), no. 2, 294-313. · Zbl 0757.60003
[2] K. Brown and P. Diaconis, Random walk and hyperplane arrangements , · Zbl 0938.60064
[3] Persi Diaconis, Group representations in probability and statistics , Institute of Mathematical Statistics Lecture Notes-Monograph Series, 11, Institute of Mathematical Statistics, Hayward, CA, 1988. · Zbl 0695.60012
[4] Persi Diaconis, The cutoff phenomenon in finite Markov chains , Proc. Nat. Acad. Sci. U.S.A. 93 (1996), no. 4, 1659-1664. JSTOR: · Zbl 0849.60070
[5] Persi Diaconis, James Allen Fill, and Jim Pitman, Analysis of top to random shuffles , Combin. Probab. Comput. 1 (1992), no. 2, 135-155. · Zbl 0798.60008
[6] Persi Diaconis, Michael McGrath, and Jim Pitman, Riffle shuffles, cycles, and descents , Combinatorica 15 (1995), no. 1, 11-29. · Zbl 0828.05003
[7] Peter Donnelly, The heaps process, libraries, and size-biased permutations , J. Appl. Probab. 28 (1991), no. 2, 321-335. JSTOR: · Zbl 0727.60078
[8] James Allen Fill, An exact formula for the move-to-front rule for self-organizing lists , J. Theoret. Probab. 9 (1996), no. 1, 113-160. · Zbl 0837.60063
[9] James Allen Fill and Lars Holst, On the distribution of search cost for the move-to-front rule , Random Structures Algorithms 8 (1996), no. 3, 179-186. · Zbl 0852.60089
[10] Phil Hanlon, The action of \(S_ n\) on the components of the Hodge decomposition of Hochschild homology , Michigan Math. J. 37 (1990), no. 1, 105-124. · Zbl 0701.16010
[11] Sanjiv Kapoor and Edward M. Reingold, Stochastic rearrangement rules for self-organizing data structures , Algorithmica 6 (1991), no. 2, 278-291. · Zbl 0711.68033
[12] Peter Orlik and Hiroaki Terao, Arrangements of hyperplanes , Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 300, Springer-Verlag, Berlin, 1992. · Zbl 0757.55001
[13] R. M. Phatarfod, On the matrix occurring in a linear search problem , J. Appl. Probab. 28 (1991), no. 2, 336-346. JSTOR: · Zbl 0731.60062
[14] Richard P. Stanley, Enumerative combinatorics. Vol. I , The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986. · Zbl 0608.05001
[15] Alexandre Varchenko, Bilinear form of real configuration of hyperplanes , Adv. Math. 97 (1993), no. 1, 110-144. · Zbl 0777.52006
[16] Thomas Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes , Mem. Amer. Math. Soc. 1 (1975), no. issue 1, 154, vii+102. · Zbl 0296.50010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.