UPPER BOUNDS ON MIXING TIME OF FINITE MARKOV CHAINS

被引:1
作者
Rhodes, John [1 ]
Schilling, Anne [2 ]
机构
[1] Univ Calif Berkeley, Dept Math, Berkeley, CA 94720 USA
[2] Univ Calif Davis, Dept Math, Davis, CA 95616 USA
基金
瑞典研究理事会;
关键词
Markov chains; Karnofsky-Rhodes expansion; McCammond expansion; mixing time; RANDOM-WALKS; THEOREM;
D O I
10.1137/21M1421994
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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).
引用
收藏
页码:3031 / 3057
页数:27
相关论文
共 49 条
  • [1] Elections with partially ordered preferences
    Ackerman, Michael
    Choi, Sul-Young
    Coughlin, Peter
    Gottlieb, Eric
    Wood, Japheth
    [J]. PUBLIC CHOICE, 2013, 157 (1-2) : 145 - 168
  • [2] TUTORIAL ON LARGE DEVIATIONS FOR THE BINOMIAL-DISTRIBUTION
    ARRATIA, R
    GORDON, L
    [J]. BULLETIN OF MATHEMATICAL BIOLOGY, 1989, 51 (01) : 125 - 131
  • [3] Functions of random walks on hyperplane arrangements
    Athanasiadis, Christos A.
    Diaconis, Persi
    [J]. ADVANCES IN APPLIED MATHEMATICS, 2010, 45 (03) : 410 - 437
  • [4] Markov chains, R-trivial monoids and representation theory
    Ayyer, Arvind
    Schilling, Anne
    Steinberg, Benjamin
    Thiery, Nicolas M.
    [J]. INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2015, 25 (1-2) : 169 - 231
  • [5] Directed Nonabelian Sandpile Models on Trees
    Ayyer, Arvind
    Schilling, Anne
    Steinberg, Benjamin
    Thiery, Nicolas M.
    [J]. COMMUNICATIONS IN MATHEMATICAL PHYSICS, 2015, 335 (03) : 1065 - 1098
  • [6] Combinatorial Markov chains on linear extensions
    Ayyer, Arvind
    Klee, Steven
    Schilling, Anne
    [J]. JOURNAL OF ALGEBRAIC COMBINATORICS, 2014, 39 (04) : 853 - 881
  • [7] Berstel J., 2010, CODES AND AUTOMATA, V129
  • [8] A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
    Bidigare, P
    Hanlon, P
    Rockmore, D
    [J]. DUKE MATHEMATICAL JOURNAL, 1999, 99 (01) : 135 - 174
  • [9] Random walks and plane arrangements in three dimensions
    Billera, LJ
    Brown, KS
    Diaconis, P
    [J]. AMERICAN MATHEMATICAL MONTHLY, 1999, 106 (06) : 502 - 524
  • [10] Bj A., 2008, BOLYAI SOC MATH STUD, V19, P165, DOI [10.1007/978-3-540-85221-65, DOI 10.1007/978-3-540-85221-65]