Directed Forests and the Constancy of Kemeny's Constant
Loading...
Date
2019-11-02
Authors
Kirkland, Steve
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Nature
Abstract
Consider a discrete-time, time-homogeneous Markov chain on states 1, ... , n whose transition matrix is irreducible. A result of Kemeny reveals that the expected number of steps needed to arrive at a randomly chosen destination state starting from state j is (surprisingly) independent of the initial state j. In this note, we consider Kemeny's result from the perspective of algebraic combinatorics, and provide an intuitive explanation for its independence on the initial state j. The all minors matrix tree theorem is the key tool employed.
Description
Keywords
Markov chain, Kemeny's constant, All minors matrix tree theorem