# ALGEBRAIC COMBINATORICS

Random walks on rings and modules
Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 309-329.

We consider two natural models of random walks on a module $V$ over a finite commutative ring $R$ driven simultaneously by addition of random elements in $V$, and multiplication by random elements in $R$. In the coin-toss walk, either one of the two operations is performed depending on the flip of a coin. In the affine walk, random elements $a\in R,b\in V$ are sampled independently, and the current state $x$ is taken to $ax+b$. For both models, we obtain the complete spectrum of the transition matrix from the representation theory of the monoid of all affine maps on $V$ under a suitable hypothesis on the measure on $V$ (the measure on $R$ can be arbitrary).

Revised: 2019-08-07
Accepted: 2019-08-08
Published online: 2020-04-01
DOI: https://doi.org/10.5802/alco.94
Classification: 60J10,  20M30,  13M99,  05E10,  60C05
Keywords: Random walks, rings, modules, monoids, representation theory
@article{ALCO_2020__3_2_309_0,
author = {Ayyer, Arvind and Steinberg, Benjamin},
title = {Random walks on rings and modules},
journal = {Algebraic Combinatorics},
pages = {309--329},
publisher = {MathOA foundation},
volume = {3},
number = {2},
year = {2020},
doi = {10.5802/alco.94},
language = {en},
url = {alco.centre-mersenne.org/item/ALCO_2020__3_2_309_0/}
}
Ayyer, Arvind; Steinberg, Benjamin. Random walks on rings and modules. Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 309-329. doi : 10.5802/alco.94. https://alco.centre-mersenne.org/item/ALCO_2020__3_2_309_0/

[1] Almeida, Jorge; Margolis, Stuart; Steinberg, Benjamin; Volkov, Mikhail Representation theory of finite semigroups, semigroup radicals and formal language theory, Trans. Am. Math. Soc., Volume 361 (2009) no. 3, pp. 1429-1461 | Article | MR 2457405 | Zbl 1185.20058

[2] Asci, Claudio Generating uniform random vectors, J. Theor. Probab., Volume 14 (2001) no. 2, pp. 333-356 | Article | MR 1838732 | Zbl 1005.65007

[3] Asci, Claudio Asymptotic behavior of an affine random recursion in ${\mathbf{Z}}_{p}^{k}$ defined by a matrix with an eigenvalue of size 1, Stat. Probab. Lett., Volume 79 (2009) no. 11, pp. 1421-1428 | Article | MR 2537517 | Zbl 1171.65007

[4] Asci, Claudio Generating uniform random vectors in ${Z}_{p}^{k}$: the general case, J. Theor. Probab., Volume 22 (2009) no. 3, pp. 791-809 | Article | MR 2530113 | Zbl 1228.60078

[5] Asci, Claudio Convergence in total variation of an affine random recursion in ${\left[0,p\right)}^{k}$ to a uniform random vector, Markov Process. Relat. Fields, Volume 19 (2013) no. 1, pp. 125-140 | MR 3088426 | Zbl 1311.60012

[6] Athanasiadis, Christos A.; Diaconis, Persi Functions of random walks on hyperplane arrangements, Adv. Appl. Math., Volume 45 (2010) no. 3, pp. 410-437 | Article | MR 2669077 | Zbl 1239.60071

[7] Ayyer, Arvind; Klee, Steven; Schilling, Anne Combinatorial Markov chains on linear extensions, J. Algebr. Comb., Volume 39 (2014) no. 4, pp. 853-881 | Article | MR 3199029 | Zbl 1292.05156

[8] Ayyer, Arvind; Klee, Steven; Schilling, Anne Markov chains for promotion operators, Algebraic Monoids, Group Embeddings, and Algebraic Combinatorics (Fields Inst. Commun.), Springer-Verlag New York, 2014 no. 71, pp. 285-304 | Article

[9] Ayyer, Arvind; Schilling, Anne; Steinberg, Benjamin; Thiéry, Nicolas M. Directed Nonabelian Sandpile Models on Trees, Commun. Math. Phys., Volume 335 (2015) no. 3, pp. 1065-1098 | Article | MR 3320305 | Zbl 06421358

[10] Ayyer, Arvind; Schilling, Anne; Steinberg, Benjamin; Thiéry, Nicolas M. Markov chains, $ℛ$-trivial monoids and representation theory, Int. J. Algebra Comput., Volume 25 (2015) no. 1-2, pp. 169-231 | Article | MR 3325881 | Zbl 1310.60105

[11] Ayyer, Arvind; Singla, Pooja Random motion on finite rings, I: commutative rings (2016) (to appear in Algebr. Represent. Theory, https://arxiv.org/abs/1605.05089)

[12] Bass, Hyman $K$-theory and stable algebra, Publications Mathématiques de l’IHÉS, Volume 22 (1964), pp. 5-60 | Article | Numdam | MR 0174604

[13] Bate, Michael E.; Connor, Stephen B. Mixing time and cutoff for a random walk on the ring of integers mod $n$, Bernoulli, Volume 24 (2018) no. 2, pp. 993-1009 | Article | MR 3706784 | Zbl 1429.60008

[14] Benson, David J. Representations and cohomology. I: Basic representation theory of finite groups and associative algebras, Cambridge Studies in Advanced Mathematics, Volume 30, Cambridge University Press, Cambridge, 1998, xii+246 pages | MR 1644252 | Zbl 0908.20001

[15] Bidigare, Pat; Hanlon, Phil; Rockmore, Dan A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements, Duke Math. J., Volume 99 (1999) no. 1, pp. 135-174 | Article | MR 1700744 | Zbl 0955.60043

[16] Björner, Anders Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries, Building bridges (Bolyai Soc. Math. Stud.) Volume 19, Springer, Berlin, 2008, pp. 165-203 | Article | MR 2484640 | Zbl 1158.60344

[17] Björner, Anders Note: Random-to-front shuffles on trees, Electron. Commun. Probab., Volume 14 (2009), pp. 36-41 | Article | MR 2481664 | Zbl 1190.60059

[18] Brown, Kenneth S. Semigroups, rings, and Markov chains, J. Theor. Probab., Volume 13 (2000) no. 3, pp. 871-938 | Article | MR 1785534 | Zbl 0980.60014

[19] Brown, Kenneth S. Semigroup and ring theoretical methods in probability, Representations of finite dimensional algebras and related topics in Lie theory and geometry (Fields Inst. Commun.) Volume 40, Amer. Math. Soc., Providence, RI, 2004, pp. 3-26 | MR 2057147 | Zbl 1043.60055

[20] Brown, Kenneth S.; Diaconis, Persi Random walks and hyperplane arrangements, Ann. Probab., Volume 26 (1998) no. 4, pp. 1813-1854 | MR 1675083 | Zbl 0938.60064

[21] Chen, Ting-Li; Hwang, Chii-Ruey Accelerating reversible Markov chains, Stat. Probab. Lett., Volume 83 (2013) no. 9, pp. 1956-1962 | Article | MR 3079029 | Zbl 1285.60076

[22] Chung, Fan R. K.; Diaconis, Persi; Graham, Ronald L. Random walks arising in random number generation, Ann. Probab., Volume 15 (1987) no. 3, pp. 1148-1165 | Article | MR 893921 | Zbl 0622.60016

[23] Chung, Fan R. K.; Graham, Ronald L. Edge flipping in graphs, Adv. Appl. Math., Volume 48 (2012) no. 1, pp. 37-63 | Article | MR 2845506 | Zbl 1234.05210

[24] Diaconis, Persi From shuffling cards to walking around the building: an introduction to modern Markov chain theory, Proceedings of the International Congress of Mathematicians, Vol. I (Berlin, 1998) (Doc. Math.) (1998) no. Extra Vol. ICM, pp. 187-204 | Zbl 0902.60052

[25] Diaconis, Persi; Holmes, Susan; Neal, Radford M. Analysis of a nonreversible Markov chain sampler, Ann. Appl. Probab., Volume 10 (2000) no. 3, pp. 726-752 | Article | MR 1789978 | Zbl 1083.60516

[26] Ding, Jiu; Zhou, Aihui Eigenvalues of rank-one updated matrices with some applications, Appl. Math. Lett., Volume 20 (2007) no. 12, pp. 1223-1226 | Article | MR 2384251 | Zbl 1139.15003

[27] Ganyushkin, Olexandr; Mazorchuk, Volodymyr; Steinberg, Benjamin On the irreducible representations of a finite semigroup, Proc. Am. Math. Soc., Volume 137 (2009) no. 11, pp. 3585-3592 | Article | MR 2529864 | Zbl 1184.20054

[28] Green, James A. On the structure of semigroups, Ann. Math. (2), Volume 54 (1951), pp. 163-172 | Article | Zbl 0043.25601

[29] Hildebrand, Martin Random processes of the form ${X}_{n+1}={a}_{n}{X}_{n}+{b}_{n}\phantom{\rule{4pt}{0ex}}\left(\mathrm{mod}\phantom{\rule{4pt}{0ex}}p\right)$, Ann. Probab., Volume 21 (1993) no. 2, pp. 710-720 | Article

[30] Hildebrand, Martin Random processes of the form ${X}_{n+1}={a}_{n}{X}_{n}+{b}_{n}\phantom{\rule{4pt}{0ex}}\left(\mathrm{mod}\phantom{\rule{4pt}{0ex}}p\right)$ where ${b}_{n}$ takes on a single value, Random discrete structures (Minneapolis, MN, 1993) (IMA Vol. Math. Appl.) Volume 76, Springer, New York, 1996, pp. 153-174 | Article | MR 1395613

[31] Hildebrand, Martin A lower bound for the Chung-Diaconis-Graham random process, Proc. Am. Math. Soc., Volume 137 (2009) no. 4, pp. 1479-1487 | Article | MR 2465674 | Zbl 1159.60008

[32] Hildebrand, Martin; McCollum, Joseph Generating random vectors in ${\left(ℤ/pℤ\right)}^{d}$ via an affine random process, J. Theor. Probab., Volume 21 (2008) no. 4, pp. 802-811 | Article | MR 2443637 | Zbl 1159.65004

[33] Huang, Lu-Jing; Mao, Yong-Hua On some mixing times for nonreversible finite Markov chains, J. Appl. Probab., Volume 54 (2017) no. 2, pp. 627-637 | Article | MR 3668487 | Zbl 1397.60108

[34] Kaiser, Marcus; Jack, Robert L.; Zimmer, Johannes Acceleration of convergence to equilibrium in Markov chains by breaking detailed balance, J. Stat. Phys., Volume 168 (2017) no. 2, pp. 259-287 | Article | MR 3667361 | Zbl 1376.82059

[35] McAlister, Donald B. Characters of finite semigroups, J. Algebra, Volume 22 (1972), pp. 183-200 | Article | MR 301125 | Zbl 0251.20072

[36] Rhodes, John; Zalcstein, Yechezkel Elementary representation and character theory of finite semigroups and its application, Monoids and semigroups with applications (Berkeley, CA, 1989), World Sci. Publ., River Edge, NJ, 1991, pp. 334-367 | Zbl 0799.20062

[37] Rosenblatt, Murray Stationary measures for random walks on semigroups, Semigroups (Proc. Sympos., Wayne State Univ., Detroit, Mich., 1968), Academic Press, New York, 1969, pp. 209-220 | Zbl 0188.49105

[38] Saliola, Franco Eigenvectors for a random walk on a left-regular band, Adv. Appl. Math., Volume 48 (2012) no. 2, pp. 306-311 | Article | MR 2873878 | Zbl 1252.60008

[39] Serre, Jean-Pierre Linear representations of finite groups, Graduate Texts in Mathematics, Volume 42, Springer-Verlag, New York, 1977, x+170 pages (Translated from the second French edition by Leonard L. Scott) | MR 450380 | Zbl 0355.20006

[40] Stanley, Richard P. Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, Volume 49, Cambridge University Press, Cambridge, 1997, xii+325 pages (With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original) | MR 1442260 | Zbl 0889.05001

[41] Steinberg, Benjamin In modules over finite rings $Rv=Rw⟺{R}^{×}v={R}^{×}w$ (https://mathoverflow.net/q/211739 (version: 2017-06-14))

[42] Steinberg, Benjamin Möbius functions and semigroup representation theory, J. Comb. Theory, Ser. A, Volume 113 (2006) no. 5, pp. 866-881 | Article | Zbl 1148.20049

[43] Steinberg, Benjamin Möbius functions and semigroup representation theory. II. Character formulas and multiplicities, Adv. Math., Volume 217 (2008) no. 4, pp. 1521-1557 | Article | Zbl 1155.20057

[44] Steinberg, Benjamin Representation theory of finite monoids, Universitext, Springer, Cham, 2016, xxiv+317 pages | Article | MR 3525092 | Zbl 1428.20003

[45] Wood, Jay A. Duality for modules over finite rings and applications to coding theory, Am. J. Math., Volume 121 (1999) no. 3, pp. 555-575 | Article | MR 1738408 | Zbl 0968.94012