Upper Bounds on Mixing Time of Finite Markov Chains
Pages 3031 - 3057
Abstract
We provide a general framework for computing mixing times of finite Markov chains whose semigroup's minimal ideal is left zero. Our analysis is based on combining results by Brown and Diaconis with our previous work on stationary distributions of finite Markov chains. Stationary distributions can be computed from the Karnofsky--Rhodes and McCammond expansion of the right Cayley graph of the finite semigroup underlying the Markov chain. Using loop graphs, which are planar graphs consisting of a straight line with attached loops, there are rational expressions for the stationary distribution in the probabilities. From these we obtain bounds on the mixing time. In addition, we provide a new Markov chain on linear extension of a poset with $n$ vertices, inspired by but different from the promotion Markov chain of Ayyer, Klee, and the last author. The mixing time of this Markov chain is $O(n \log n)$.
References
[1]
M. Ackerman, S.-Y. Choi, P. Coughlin, E. Gottlieb, and J. Wood, Elections with partially ordered preferences, Public Choice, 157 (2013), pp. 145--168.
[2]
R. Arratia and L. Gordon, Tutorial on large deviations for the binomial distribution, Bull. Math. Biol., 51 (1989), pp. 125--131, https://doi.org/10.1016/S0092-8240(89)80052-7.
[3]
C. A. Athanasiadis and P. Diaconis, Functions of random walks on hyperplane arrangements, Adv. in Appl. Math., 45 (2010), pp. 410--437, https://doi.org/10.1016/j.aam.2010.02.001.
[4]
A. Ayyer, S. Klee, and A. Schilling, Combinatorial Markov chains on linear extensions, J. Algebraic Combin., 39 (2014), pp. 853--881, https://doi.org/10.1007/s10801-013-0470-9.
[5]
A. Ayyer, A. Schilling, B. Steinberg, and N. M. Thiéry, Directed nonabelian sandpile models on trees, Comm. Math. Phys., 335 (2015), pp. 1065--1098, https://doi.org/10.1007/s00220-015-2343-7.
[6]
A. Ayyer, A. Schilling, B. Steinberg, and N. M. Thiéry, Markov chains, $\mathscr{R}$-trivial monoids and representation theory, Internat. J. Algebra Comput., 25 (2015), pp. 169--231, https://doi.org/10.1142/S0218196715400081.
[7]
J. Berstel, D. Perrin, and C. Reutenauer, Codes and Automata, Encyclopedia Math. Appl. 129, Cambridge University Press, Cambridge, UK, 2010.
[8]
P. Bidigare, P. Hanlon, and D. Rockmore, A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements, Duke Math. J., 99 (1999), pp. 135--174, https://doi.org/10.1215/S0012-7094-99-09906-4.
[9]
L. J. Billera, K. S. Brown, and P. Diaconis, Random walks and plane arrangements in three dimensions, Amer. Math. Monthly, 106 (1999), pp. 502--524, https://doi.org/10.2307/2589463.
[10]
A. Björner, Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries, in Building Bridges, Bolyai Soc. Math. Stud. 19, Springer, Berlin, 2008, pp. 165--203, https://doi.org/10.1007/978-3-540-85221-6_5.
[11]
A. Björner, Note: Random-to-front shuffles on trees, Electron. Commun. Probab., 14 (2009), pp. 36--41, https://doi.org/10.1214/ECP.v14-1445.
[12]
L. Breiman, The individual ergodic theorem of information theory, Ann. Math. Statist., 28 (1957), pp. 809--811, https://doi.org/10.1214/aoms/1177706899.
[13]
G. Brightwell and P. Winkler, Counting linear extensions, Order, 8 (1991), pp. 225--242, https://doi.org/10.1007/BF00383444.
[14]
K. S. Brown, Semigroups, rings, and Markov chains, J. Theoret. Probab., 13 (2000), pp. 871--938, https://doi.org/10.1023/A:1007822931408.
[15]
K. S. Brown and P. Diaconis, Random walks and hyperplane arrangements, Ann. Probab., 26 (1998), pp. 1813--1854, https://doi.org/10.1214/aop/1022855884.
[16]
R. Bubley and M. Dyer, Faster random generation of linear extensions, Discrete Math., 201 (1999), pp. 81--88, https://doi.org/10.1016/S0012-365X(98)00333-1.
[17]
M. L. Cetlin, Finite automata and the simulation of the simplest forms of behavior, Uspekhi Mat. Nauk, 18 (1963), pp. 3--28.
[18]
F. Chung and R. Graham, Edge flipping in graphs, Adv. in Appl. Math., 48 (2012), pp. 37--63, https://doi.org/10.1016/j.aam.2011.06.002.
[19]
L. Devroye and G. Lugosi, Combinatorial Methods in Density Estimation, Springer Ser. Statist., Springer, New York, 2001, https://doi.org/10.1007/978-1-4613-0125-7.
[20]
P. Diaconis, From shuffling cards to walking around the building: An introduction to modern Markov chain theory, in Proceedings of the International Congress of Mathematicians, Berlin, 1998, pp. 187--204.
[21]
P. Edelman, T. Hibi, and R. P. Stanley, A recurrence for linear extensions, Order, 6 (1989), pp. 15--18, https://doi.org/10.1007/BF00341632.
[22]
J. A. Fill, An exact formula for the move-to-front rule for self-organizing lists, J. Theoret. Probab., 9 (1996), pp. 113--160, https://doi.org/10.1007/BF02213737.
[23]
P. C. Fishburn and W. V. Gehrlein, A comparative analysis of methods for constructing weak orders from partial orders, J. Math. Sociol., 4 (1975), pp. 93--102, https://doi.org/10.1080/0022250x.1975.9989846.
[24]
R. M. Gray, Entropy and Information Theory, 2nd ed., Springer, New York, 2011, https://doi.org/10.1007/978-1-4419-7970-4.
[25]
M. D. Haiman, Dual equivalence with applications, including a conjecture of Proctor, Discrete Math., 99 (1992), pp. 79--113, https://doi.org/10.1016/0012-365X(92)90368-P.
[26]
W. J. Hendricks, The stationary distribution of an interesting Markov chain, J. Appl. Probab., 9 (1972), pp. 231--233.
[27]
W. J. Hendricks, An extension of a theorem concerning an interesting Markov chain, J. Appl. Probab., 10 (1973), pp. 886--890.
[28]
A. Karzanov and L. Khachiyan, On the conductance of order Markov chains, Order, 8 (1991), pp. 7--15, https://doi.org/10.1007/BF00385809.
[29]
D. E. Knuth, The Art of Computer Programming, Vol. 1, Fundamental Algorithms, 3rd ed., Addison-Wesley, Reading, MA, 1997.
[30]
D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, 2nd ed., Addison-Wesley, Reading, MA, 1998.
[31]
D. A. Levin and Y. Peres, Markov Chains and Mixing Times, 2nd ed., American Mathematical Society, Providence, RI, 2017.
[32]
C. Malvenuto and C. Reutenauer, Evacuation of labelled graphs, Discrete Math., 132 (1994), pp. 137--143, https://doi.org/10.1016/0012-365X(92)00569-D.
[33]
S. Margolis, F. Saliola, and B. Steinberg, Combinatorial topology and the global dimension of algebras arising in combinatorics, J. Eur. Math. Soc. (JEMS), 17 (2015), pp. 3037--3080, https://doi.org/10.4171/JEMS/579.
[34]
J. McCammond, J. Rhodes, and B. Steinberg, Geometric Semigroup Theory, preprint, arXiv:1104.2301 [math.GR], 2011, http://arxiv.org/abs/1104.2301.
[35]
B. McMillan, The basic theorems of information theory, Ann. Math. Statist., 24 (1953), pp. 196--219, https://doi.org/10.1214/aoms/1177729028.
[36]
E. Nestoridi, Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement, Probab. Theory Related Fields, 174 (2019), pp. 929--943, https://doi.org/10.1007/s00440-018-0872-7.
[37]
J. Pike, Eigenfunctions for Random Walks on Hyperplane Arrangements, Ph.D. thesis, University of Southern California, 2013.
[38]
J. Rhodes and A. Schilling, Normal distributions of finite Markov chains, Internat. J. Algebra Comput., 29 (2019), pp. 1431--1449, https://doi.org/10.1142/S0218196719500577.
[39]
J. Rhodes and A. Schilling, Unified theory for finite Markov chains, Adv. Math., 347 (2019), pp. 739--779, https://doi.org/10.1016/j.aim.2019.03.004.
[40]
J. Rhodes and A. Schilling, Mixing time for Markov chain on linear extensions, Sém. Lothar. Combin., 85B (2021), 27.
[41]
J. Rhodes, A. Schilling, and P. V. Silva, Random walks on semaphore codes and delay de Bruijn semigroups, Internat. J. Algebra Comput., 26 (2016), pp. 635--673, https://doi.org/10.1142/S0218196716500284.
[42]
J. Rhodes, A. Schilling, and P. V. Silva, Holonomy theorem for finite semigroups, Internat. J. Algebra Comput., 32 (2022), pp. 443--460, https://doi.org/10.1142/S0218196722500217.
[43]
O. Rioul, This is IT: A primer on Shannon's entropy and information, in Proceedings of L'Information, Séminaire Poincaré XXIII, 2018, pp. 43--77.
[44]
F. Saliola, Eigenvectors for a random walk on a left-regular band, Adv. in Appl. Math., 48 (2012), pp. 306--311, https://doi.org/10.1016/j.aam.2011.09.002.
[45]
M.-P. Schützenberger, Sur certains treillis gauches, C. R. Acad. Sci. Paris, 224 (1947), pp. 776--778.
[46]
C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J., 27 (1948), pp. 379--423 and 623--656.
[47]
R. P. Stanley, Promotion and evacuation, Electron. J. Combin., 16 (2009), 9.
[48]
H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Progr. Theoret. Comput. Sci., Birkhäuser, Boston, MA, 1994, https://doi.org/10.1007/978-1-4612-0289-9.
[49]
Y. Zalcstein, Locally testable languages, J. Comput. System Sci., 6 (1972), pp. 151--167, https://doi.org/10.1016/S0022-0000(72)80020-5.
Index Terms
- Upper Bounds on Mixing Time of Finite Markov Chains
Index terms have been assigned to the content through auto-classification.
Recommendations
Deterministic Random Walks for Rapidly Mixing Chains
The rotor-router model is a deterministic process analogous to a simple random walk on a graph, and the discrepancy of token configurations between the rotor-router model and its corresponding random walk has been investigated in some contexts. Motivated by ...
Case for First Courses on Finite Markov Chain Modeling to Include Sojourn Time Cycle Chart
This education article presents a case for first courses on Markov chain modeling to include the topic “sojourn time cycle chart" (STC chart). This article does so through a teaching module that consists of (i) hypothetical examples illustrating the ...
Perturbation Bounds for the Stationary Distributions of Markov Chains
In this paper, we are interested in investigating the perturbation bounds for the stationary distributions for discrete-time or continuous-time Markov chains on a countable state space. For discrete-time Markov chains, two new normwise bounds are obtained. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
DOI:10.1137/sjdmec.36.4
Issue’s Table of Contents© 2022, Society for Industrial and Applied Mathematics.
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 2022
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Dec 2024