No Access

Markov chains, -trivial monoids and representation theory

Arvind Ayyer

Department of Mathematics, Indian Institute of Science, Bangalore - 560012, India

Search for more papers by this author

Anne Schilling

Department of Mathematics, University of California Davis, One Shields Ave., Davis, California 95616-8633, USA

Search for more papers by this author

Benjamin Steinberg

Department of Mathematics, City College of New York, Convent Avenue at 138th Street, New York, 10031, USA

Search for more papers by this author

, and

Nicolas M. Thiéry

Laboratoire de Recherche en Informatique, Université Paris-Sud, Orsay, F-91405, France

CNRS, Orsay, F-91405, France

Search for more papers by this author

https://doi.org/10.1142/S0218196715400081Cited by:25 (Source: Crossref)

Abstract

We develop a general theory of Markov chains realizable as random walks on -trivial monoids. It provides explicit and simple formulas for the eigenvalues of the transition matrix, for multiplicities of the eigenvalues via Möbius inversion along a lattice, a condition for diagonalizability of the transition matrix and some techniques for bounding the mixing time. In addition, we discuss several examples, such as Toom–Tsetlin models, an exchange walk for finite Coxeter groups, as well as examples previously studied by the authors, such as nonabelian sandpile models and the promotion Markov chain on posets. Many of these examples can be viewed as random walks on quotients of free tree monoids, a new class of monoids whose combinatorics we develop.

Dedicated to Stuart Margolis on the occasion of his sixtieth birthday

Keywords:

AMSC: 60J10, 05E10, 20M30, 47D03, 60C05

References

P. Abramenko and K. S. Brown , Buildings: Theory and Applications Graduate Texts in Mathematics 248 ( Springer , New York , 2008 ) . Crossref, Google Scholar
O. Angel, A. Holroyd and D. Romik, Ann. Probab. 37(5), 1970 (2009). Crossref, Web of Science, Google Scholar
J. Almeida , Finite Semigroups and Universal Algebra , Series in Algebra 3 ( World Scientific Publishing , River Edge, NJ , 1994 ) . Google Scholar
J. Almeidaet al., Trans. Amer. Math. Soc. 361(3), 1429 (2009). Crossref, Web of Science, Google Scholar
C. A. Athanasiadis and P. Diaconis, Adv. Appl. Math. 45(3), 410 (2010). Crossref, Web of Science, Google Scholar
A. Ayyer , J. Statist. Mech.: Theory Exp. P02034 ( 2011 ) . Crossref, Web of Science, Google Scholar
A. Ayyer, S. Klee and A. Schilling, J. Algebraic Combin. 39(4), 853 (2014). Crossref, Web of Science, Google Scholar
A. Ayyer , S. Klee and A. Schilling , Fields Inst. Commun. 71 , 285 ( 2014 ) , arXiv:1307.7499 . Crossref, Google Scholar
A. Ayyer, A. Schilling, B. Steinberg and N. M. Thiéry, Directed nonabelian sandpile models on trees, (2013) , arXiv.1305.1697 . Google Scholar
A. Ayyer and V. Strehl, The spectrum of an asymmetric annihilation process, 22nd Int. Conf. on Formal Power Series and Algebraic Combinatorics (FPSAC 2010) (Nancy, 2010) pp. 461–472. Google Scholar
A. Ayyer and V. Strehl, Advances in Combinatorics, eds. I. S. Kotsireas and E. V. Zima (Springer, Berlin Heidelberg, 2013) pp. 101–120. Crossref, Google Scholar
P. Bak, C. Tang and K. Wiesenfeld, Phys. Rev. Lett. 59(4), 381 (1987). Crossref, Web of Science, Google Scholar
I. Benjaminiet al., Trans. Amer. Math. Soc. 357(8), 3013 (2005). Crossref, Web of Science, Google Scholar
A. Berman and R. J. Plemmons , Nonnegative Matrices in the Mathematical Sciences , Computer Science and Applied Mathematics ( Academic Press , New York , 1979 ) . Google Scholar
T. P. Bidigare, Hyperplane arrangement face algebras and their associated Markov chains, ProQuest LLC, Ann Arbor, MI, 1997. Thesis (Ph.D.)–University of Michigan . Google Scholar
P. Bidigare, P. Hanlon and D. Rockmore, Duke Math. J. 99(1), 135 (1999). Crossref, Web of Science, Google Scholar
L. J. Billera, K. S. Brown and P. Diaconis, Amer. Math. Monthly 106(6), 502 (1999). Crossref, Web of Science, Google Scholar
A. Björner, Building bridges, Bolyai Society Mathematics Studies 19 (Springer, Berlin, 2008) pp. 165–203. Google Scholar
A. Björner , Electron. Commun. Probab. 14 , 36 ( 2009 ) . Crossref, Web of Science, Google Scholar
A. Björner and F. Brenti , Combinatorics of Coxeter groups , Graduate Texts in Mathematics 231 ( Springer , New York , 2005 ) . Google Scholar
K. S. Brown, J. Theor. Probab. 13(3), 871 (2000). Crossref, Web of Science, Google Scholar
K. S. Brown and P. Diaconis, Ann. Probab. 26(4), 1813 (1998). Crossref, Web of Science, Google Scholar
R. V. Book and F. Otto , String-rewriting Systems , Texts and Monographs in Computer Science ( Springer-Verlag , New York , 1993 ) . Crossref, Google Scholar
L. Carlitz, Fibonacci Quart. 16(3), 255 (1978). Web of Science, Google Scholar
R. W. Carter, J. Algebra 104(1), 89 (1986). Crossref, Web of Science, Google Scholar
T. Ceccherini-Silberstein , F. Scarabotti and F. Tolli , Harmonic Analysis on Finite Groups , Cambridge Studies in Advanced Mathematics 108 ( Cambridge University Press , Cambridge , 2008 ) . Crossref, Google Scholar
B. W. Charet al., Maple Reference Manual, 5th edn. (WATCOM Publications, 1988). Google Scholar
F. Chung and R. Graham, Adv. Appl. Math. 48(1), 37 (2012). Crossref, Web of Science, Google Scholar
A. H. Clifford and G. B. Preston , The Algebraic Theory of Semigroups , Mathematical Surveys I ( American Mathematical Society , Providence, R.I. , 1961 ) . Crossref, Google Scholar
T. Denton, A combinatorial formula for orthogonal idempotents in the 0-Hecke algebra of the symmetric group, Electron. J. Combin. 18 (1) (2011) Research Paper 28, 20 pp . Google Scholar
T. Denton et al. , Sém. Lothar. Combin. 64 , 44 ( 2011 ) , 2010/ . Google Scholar
B. Derridaet al., J. Phys. A 24(20), 4805 (1991). Crossref, Google Scholar
B. Derridaet al., Phys. Rev. Lett. 67(2), 165 (1991). Crossref, Web of Science, Google Scholar
L. Devroye and G. Lugosi , Combinatorial Methods in Density Estimation , Springer Series in Statistics Series ( Springer-Verlag , 2001 ) . Crossref, Google Scholar
D. Dhar, Phys. Rev. Lett. 64(14), 1613 (1990). Crossref, Web of Science, Google Scholar
D. Dhar, Physica A 263(1), 4 (1999). Crossref, Web of Science, Google Scholar
P. Diaconis , Group Representations in Probability and Statistics , Institute of Mathematical Statistics Lecture Notes — Monograph Series 11 ( Institute of Mathematical Statistics , Hayward, CA , 1988 ) . Crossref, Google Scholar
P. Diaconis, From shuffling cards to walking around the building: An introduction to modern Markov chain theory, Proc. Int. Cong. MathematiciansI (Berlin, 1998) pp. 187–204. Google Scholar
P. Diaconis and A. Ram, Ann. Probab. 40(5), 1861 (2012). Crossref, Web of Science, Google Scholar
P. Diaconis and M. Shahshahani, Z. Wahrsch. Verw. Gebiete 57(2), 159 (1981). Crossref, Google Scholar
P. Diaconis and M. Shahshahani, Random Matrices and their Applications, Contemporary Mathematics 50 (American Mathematical Society Providence, RI, 1986) pp. 183–195. Crossref, Google Scholar
R. P. Dobrow and J. A. Fill, Ann. Appl. Probab. 5(1), 1 (1995). Crossref, Web of Science, Google Scholar
P. Edelman and C. Greene, Adv. Math. 63(1), 42 (1987). Crossref, Web of Science, Google Scholar
S. Eilenberg , Automata, Languages, and Machines , Pure and Applied Mathematics 59 ( Academic Press , New York , 1976 ) . Google Scholar
G. Z. Elston, J. Pure Appl. Algebra 136(3), 231 (1999). Crossref, Web of Science, Google Scholar
P. Erdős and A. Rényi , Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 , 215 ( 1961 ) . Google Scholar
S. Even and J. Gillis, Math. Proc. Cambridge Philos. Soc. 79(1), 135 (1976). Crossref, Web of Science, Google Scholar
M. Fayers, J. Pure Appl. Algebra 199(3), 27 (2005). Crossref, Web of Science, Google Scholar
J. A. Fill and L. Holst, Random Structures Algorithms 8(3), 179 (1996). Crossref, Web of Science, Google Scholar
P. Flajolet, D. Gardy and L. Thimonier, Discrete Appl. Math. 39(3), 207 (1992). Crossref, Web of Science, Google Scholar
O. Ganyushkin, V. Mazorchuk and B. Steinberg, Proc. Amer. Math. Soc. 137(11), 3585 (2009). Crossref, Web of Science, Google Scholar
J. A. Green , Ann. of Math. (2) 54 , 163 ( 1951 ) . Crossref, Web of Science, Google Scholar
M. D. Haiman, Discrete Math. 99(3), 79 (1992). Crossref, Web of Science, Google Scholar
W. J. Hendricks , J. Appl. Probab. 9 , 231 ( 1972 ) . Crossref, Web of Science, Google Scholar
F. Hivert, A. Schilling and N. Thiéry, Algebra Number Theory 7(3), 595 (2013). Crossref, Web of Science, Google Scholar
G. Högnäs and A. Mukherjea , Probability Measures on Semigroups , 2nd edn. , Probability and Its Applications ( Springer , New York , 2011 ) . Crossref, Google Scholar
D. Holt, Kbmag — knuth-bendix for monoids and automatic groups version 2.4. University of Warwick (1998) . Google Scholar
J. M. Howie , Fundamentals of Semigroup Theory , London Mathematical Society Monographs, New Series 12 ( The Clarendon Press, Oxford University Press , New York , 1995 ) . Crossref, Google Scholar
K. Krohn , J. Rhodes and B. Tilson , Algebraic Theory of Machines, Languages, and Semigroups , eds. Michael A. Arbib , Kenneth Krohn and John L. Rhodes ( Academic Press , New York , 1968 ) . Google Scholar
J. L. Lebowitz, C. Neuhauser and K. Ravishankar, Stochastic Process. Appl. 64(2), 187 (1996). Crossref, Web of Science, Google Scholar
D. A. Levin , Y. Peres and E. L. Wilmer , Markov Chains and Mixing Times , eds. James G. Propp and David B. Wilson ( American Mathematical Society , Providence, RI , 2009 ) . Google Scholar
M. Lothaire , Algebraic Combinatorics on Words , Encyclopedia of Mathematics and Its Applications 90 ( Cambridge University Press , Cambridge , 2002 ) . Crossref, Google Scholar
C. Malvenuto and C. Reutenauer, Discrete Math. 132(3), 137 (1994). Crossref, Web of Science, Google Scholar
S. Margolis and B. Steinberg, Algebr. Represent. Theory 14(1), 131 (2011). Crossref, Web of Science, Google Scholar
S. Margolis and B. Steinberg, Compos. Math. 148(5), 1516 (2012). Crossref, Web of Science, Google Scholar
R. May, Electron. J. Combin. 15(1), 31 (2008). Crossref, Google Scholar
V. Mazorchuk and B. Steinberg, J. Algebraic Combin. 36(3), 333 (2012). Crossref, Web of Science, Google Scholar
D. B. McAlister , J. Algebra 22 , 183 ( 1972 ) . Crossref, Web of Science, Google Scholar
D. J. Newman and L. Shepp , Amer. Math. Monthly 67 , 58 ( 1960 ) . Crossref, Google Scholar
P. N. Norton, J. Austral. Math. Soc. Ser. A 27(3), 337 (1979). Crossref, Google Scholar
OEIS Foundation Inc, The on-line encyclopedia of integer sequences (2012) . Google Scholar
J.-É. Pin , Mathematical Foundations of Automata Theory ( 2013 ) . Google Scholar
M. S. Putcha, Proc. London Math. Soc. (3) 73(3), 623 (1996). Crossref, Web of Science, Google Scholar
M. S. Putcha, J. Algebra 205(1), 53 (1998). Crossref, Web of Science, Google Scholar
J. Rhodes and B. Steinberg , The q-theory of Finite Semigroups , Springer Monographs in Mathematics ( Springer , New York , 2009 ) . Crossref, Google Scholar
J. Rhodes and Y. Zalcstein, Monoids and Semigroups with Applications (World Scientific Publisher, River Edge, NJ, 1991) pp. 334–367. Link, Google Scholar
F. V. Saliola, Internat. J. Algebra Comput. 17(8), 1593 (2007). Link, Web of Science, Google Scholar
F. Saliola, Adv. Appl. Math. 48(2), 306 (2012). Crossref, Web of Science, Google Scholar
M. P. Schützenberger , Discrete Math. 2 , 73 ( 1972 ) . Crossref, Google Scholar
R. P. Stanley, European J. Combin. 5(4), 359 (1984). Crossref, Google Scholar
R. P. Stanley, Promotion and evacuation, Electron. J. Combin. 16(2) (2009) 1–24, Special volume in honor of Anders Bjorner, Research Paper 9 . Google Scholar
W. A. Stein et al., Sage Mathematics Software (Version 5.9), The Sage Development Team (2013), http://www.sagemath.org . Google Scholar
B. Steinberg, J. Combin. Theory Ser. A 113(5), 866 (2006). Crossref, Web of Science, Google Scholar
B. Steinberg, Adv. Math. 217(4), 1521 (2008). Crossref, Web of Science, Google Scholar
The Sage-Combinat community. Sage-Combinat: Enhancing Sage as a toolbox for computer exploration in algebraic combinatorics (2008), http://combinat.sagemath.org . Google Scholar
A. L. Toom , Multicomponent Random Systems 6 , eds. R. L. Dobrushin and Ya. G. Sinai ( Marcel Dekker , 1980 ) . Google Scholar
G. M. Ziegler , Lectures on Polytopes , Graduate Texts in Mathematics 152 ( Springer-Verlag , New York , 1995 ) . Crossref, Google Scholar