Random walks on rings and modules

Ayyer, Arvind¹ ; Steinberg, Benjamin²

¹ Department of Mathematics Indian Institute of Science Bangalore 560012 India
² Department of Mathematics City College of New York Convent Avenue at 138th Street New York, New York 10031 USA

Algebraic Combinatorics, Tome 3 (2020) no. 2, pp. 309-329.

Résumé

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).

Détail

Reçu le : 2018-08-14
Révisé le : 2019-08-08
Accepté le : 2019-08-09
Publié le : 2020-04-01

DOI : 10.5802/alco.94

Classification : 60J10, 20M30, 13M99, 05E10, 60C05
Mots-clés : Random walks, rings, modules, monoids, representation theory

Licence : CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

Bibliographie

[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 | Zbl | DOI | MR

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

[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 | Zbl | MR | DOI

[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 | Zbl | MR | DOI

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

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

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

[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 | DOI

[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 | Zbl | MR | DOI

[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 | Zbl | MR | DOI

[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 | DOI | mathdoc-id | MR

[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 | DOI | MR | Zbl

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

[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 | MR | DOI | Zbl

[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 | DOI | Zbl | MR

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

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

[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 | Zbl | MR

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

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

[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 | Zbl | DOI | MR

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

[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 | MR

[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 | Zbl | MR | DOI

[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 | Zbl | MR | DOI

[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 | Zbl | MR | DOI

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

[29] Hildebrand, Martin Random processes of the form $X_{n+1}=a_n{X}_n+b_n\left(\mathrm{mod}p\right)$, Ann. Probab., Volume 21 (1993) no. 2, pp. 710-720 | DOI | MR

[30] Hildebrand, Martin Random processes of the form $X_{n+1}=a_n{X}_n+b_n\left(\mathrm{mod}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 | MR | DOI

[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 | Zbl | MR | DOI

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

[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 | Zbl | MR | DOI

[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 | Zbl | MR | DOI

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

[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 | MR

[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 | MR

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

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

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

[41] Steinberg, Benjamin In modules over finite rings $Rv=Rw⟺R^{\times }v=R^{\times }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 | DOI | Zbl | MR

[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 | Zbl | DOI | MR

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

[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 | Zbl | DOI | MR