The Role of Kemeny's Constant in Properties of Markov Chains

被引：56
作者：
Hunter, Jeffrey J. [1 ]
机构：
[1] Auckland Univ Technol, Sch Comp & Math Sci, Auckland 1142, New Zealand
来源：
COMMUNICATIONS IN STATISTICS-THEORY AND METHODS | 2014年 / 43卷 / 07期
关键词：
Directed graphs; Markov chains; Mixing; Kemeny constant; Kirchhoff index; 60J10; WIENER; INDEX; TIMES;
D O I：
10.1080/03610926.2012.741742
中图分类号：
O21 [概率论与数理统计]; C8 [统计学];
学科分类号：
020208 ; 070103 ; 0714 ;
摘要：
In a finite irreducible Markov chain with stationary probabilities {pi(i)} and mean first passage times m(ij) (mean recurrence time when i=j) it was first shown, by Kemeny and Snell (1960), that Sigma(j)pi(j)m(ij) is a constant, K, (Kemeny's constant) not depending on i. A variety of techniques for finding expressions and bounds for K are given. The main interpretation focuses on its role as the expected time to mixing in a Markov chain. Various applications are considered including perturbation results, mixing on directed graphs and its relation to the Kirchhoff index of regular graphs.
引用
收藏
页码：1309 / 1321
页数：13
相关论文
共 34 条
  • [1] [Anonymous], 1995, Reversible markov chains and random walks on graphs
  • [2] [Anonymous], 2003, J THEORET BIOL
  • [3] [Anonymous], 1984, Random walks and electric networks
  • [4] The Kemeny Constant for Finite Homogeneous Ergodic Markov Chains
    Catral, M.
    Kirkland, S. J.
    Neumann, M.
    Sze, N-S.
    [J]. JOURNAL OF SCIENTIFIC COMPUTING, 2010, 45 (1-3) : 151 - 166
  • [5] Chandra A. K., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P574, DOI 10.1145/73007.73062
  • [6] DOYLE P, 2009, KEMENY CONSTANT MARK
  • [7] DOYLE P, 2003, KEMENYS CONSTANT
  • [8] Grinstead C, 2006, INTRO PROBABILITY
  • [9] Grinstead CM., 1997, Introduction to Probability
  • [10] The quasi-Wiener and the Kirchhoff indices coincide
    Gutman, I
    Mohar, B
    [J]. JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1996, 36 (05): : 982 - 985
1234