Directed Forests and the Constancy of Kemeny's Constant

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.