{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T02:07:17Z","timestamp":1773194837505,"version":"3.50.1"},"reference-count":77,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2015,2]]},"abstract":"<jats:p>We develop a general theory of Markov chains realizable as random walks on [Formula: see text]-trivial monoids. It provides explicit and simple formulas for the eigenvalues of the transition matrix, for multiplicities of the eigenvalues via M\u00f6bius 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\u2013Tsetlin 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.<\/jats:p>","DOI":"10.1142\/s0218196715400081","type":"journal-article","created":{"date-parts":[[2015,1,9]],"date-time":"2015-01-09T08:33:15Z","timestamp":1420792395000},"page":"169-231","source":"Crossref","is-referenced-by-count":30,"title":["Markov chains, ${\\mathscr R}$-trivial monoids and representation theory"],"prefix":"10.1142","volume":"25","author":[{"given":"Arvind","family":"Ayyer","sequence":"first","affiliation":[{"name":"Department of Mathematics, Indian Institute of Science, Bangalore - 560012, India"}]},{"given":"Anne","family":"Schilling","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California Davis, One Shields Ave., Davis, California 95616-8633, USA"}]},{"given":"Benjamin","family":"Steinberg","sequence":"additional","affiliation":[{"name":"Department of Mathematics, City College of New York, Convent Avenue at 138th Street, New York, 10031, USA"}]},{"given":"Nicolas M.","family":"Thi\u00e9ry","sequence":"additional","affiliation":[{"name":"Laboratoire de Recherche en Informatique, Universit\u00e9 Paris-Sud, Orsay, F-91405, France"},{"name":"CNRS, Orsay, F-91405, France"}]}],"member":"219","published-online":{"date-parts":[[2015,3,25]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-78835-7"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOP456"},{"key":"rf3","series-title":"Series in Algebra","volume-title":"Finite Semigroups and Universal Algebra","volume":"3","author":"Almeida J.","year":"1994"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-08-04712-0"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2010.02.001"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2011\/02\/P02034"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-013-0470-9"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-0938-4_13"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30979-3_5"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.59.381"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-05-03610-X"},{"key":"rf14","series-title":"Computer Science and Applied Mathematics","volume-title":"Nonnegative Matrices in the Mathematical Sciences","author":"Berman A.","year":"1979"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-99-09906-4"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.2307\/2589463"},{"key":"rf18","doi-asserted-by":"crossref","unstructured":"A.\u00a0Bj\u00f6rner, Building bridges, Bolyai Society Mathematics Studies\u00a019 (Springer, Berlin, 2008)\u00a0pp. 165\u2013203.","DOI":"10.1007\/978-3-540-85221-6_5"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v14-1445"},{"key":"rf20","series-title":"Graduate Texts in Mathematics","volume-title":"Combinatorics of Coxeter groups","volume":"231","author":"Bj\u00f6rner A.","year":"2005"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007822931408"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1022855884"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"rf24","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1080\/00150517.1978.12430325","volume":"16","author":"Carlitz L.","year":"1978","journal-title":"Fibonacci Quart."},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(86)90238-3"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511619823"},{"key":"rf27","volume-title":"Maple Reference Manual","author":"Char B. W.","year":"1988"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2011.06.002"},{"key":"rf29","series-title":"Mathematical Surveys","volume-title":"The Algebraic Theory of Semigroups","author":"Clifford A. H.","year":"1961"},{"key":"rf31","first-page":"44","volume":"64","author":"Denton T.","year":"2011","journal-title":"S\u00e9m. Lothar. Combin."},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/24\/20\/015"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.67.165"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0125-7"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.64.1613"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(98)00493-2"},{"key":"rf37","series-title":"Institute of Mathematical Statistics Lecture Notes \u2014 Monograph Series","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0086177","volume-title":"Group Representations in Probability and Statistics","volume":"11","author":"Diaconis P.","year":"1988"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOP674"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1007\/BF00535487"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/050\/841092"},{"key":"rf42","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004824"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(87)90063-6"},{"key":"rf44","series-title":"Pure and Applied Mathematics","volume-title":"Automata, Languages, and Machines","volume":"59","author":"Eilenberg S.","year":"1976"},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(97)00172-2"},{"key":"rf46","first-page":"215","volume":"6","author":"Erd\u0151s P.","year":"1961","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"rf47","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100052154"},{"key":"rf48","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2004.12.001"},{"key":"rf49","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199605)8:3<179::AID-RSA2>3.0.CO;2-V"},{"key":"rf50","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90177-C"},{"key":"rf51","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-09-09857-8"},{"key":"rf52","doi-asserted-by":"publisher","DOI":"10.2307\/1969317"},{"key":"rf53","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90368-P"},{"key":"rf54","doi-asserted-by":"publisher","DOI":"10.2307\/3212655"},{"key":"rf55","doi-asserted-by":"publisher","DOI":"10.2140\/ant.2013.7.595"},{"key":"rf56","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-77548-7"},{"key":"rf58","series-title":"London Mathematical Society Monographs, New Series","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198511946.001.0001","volume-title":"Fundamentals of Semigroup Theory","volume":"12","author":"Howie J. M.","year":"1995"},{"key":"rf59","volume-title":"Algebraic Theory of Machines, Languages, and Semigroups","author":"Krohn K.","year":"1968"},{"key":"rf60","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(96)00088-9"},{"key":"rf61","volume-title":"Markov Chains and Mixing Times","author":"Levin D. A.","year":"2009"},{"key":"rf62","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019"},{"key":"rf63","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)00569-D"},{"key":"rf64","doi-asserted-by":"publisher","DOI":"10.1007\/s10468-009-9181-2"},{"key":"rf65","doi-asserted-by":"publisher","DOI":"10.1112\/S0010437X1200022X"},{"key":"rf66","doi-asserted-by":"crossref","first-page":"31","DOI":"10.37236\/906","volume":"15","author":"May R.","year":"2008","journal-title":"Electron. J. Combin."},{"key":"rf67","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-011-0336-y"},{"key":"rf68","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(72)90111-1"},{"key":"rf69","doi-asserted-by":"publisher","DOI":"10.2307\/2308930"},{"key":"rf70","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700012453"},{"key":"rf72","volume-title":"Mathematical Foundations of Automata Theory","author":"Pin J.-\u00c9.","year":"2013"},{"key":"rf73","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-73.3.623"},{"key":"rf74","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.1997.7395"},{"key":"rf75","doi-asserted-by":"publisher","DOI":"10.1007\/b104443"},{"key":"rf76","doi-asserted-by":"crossref","unstructured":"J.\u00a0Rhodes and Y.\u00a0Zalcstein, Monoids and Semigroups with Applications (World Scientific Publisher, River Edge, NJ, 1991)\u00a0pp. 334\u2013367.","DOI":"10.1142\/9789814540803"},{"key":"rf77","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196707004219"},{"key":"rf78","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2011.09.002"},{"key":"rf79","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(72)90062-3"},{"key":"rf80","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(84)80039-6"},{"key":"rf83","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2005.08.004"},{"key":"rf84","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2007.12.001"},{"key":"rf86","volume-title":"Multicomponent Random Systems","volume":"6","author":"Toom A. L.","year":"1980"},{"key":"rf87","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196715400081","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T15:58:14Z","timestamp":1747411094000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196715400081"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2]]},"references-count":77,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2015,3,25]]},"published-print":{"date-parts":[[2015,2]]}},"alternative-id":["10.1142\/S0218196715400081"],"URL":"https:\/\/doi.org\/10.1142\/s0218196715400081","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2]]}}}