Kemeny's Constant And An Analogue Of Braess' Paradox For Trees

Abstract

Given an irreducible stochastic matrix M, Kemenyâs constant K(M) measures the expected time for the corresponding Markov chain to transition from any given initial state to a randomly chosen final state. A combinatorially based expression for K(M) is provided in terms of the weights of certain directed forests in a directed graph associated with M, yielding a particularly simple expression in the special case that M is the transition matrix for a random walk on a tree. An analogue of Braessâ paradox is investigated, whereby inserting an edge into an undirected graph can increase the value of Kemenyâs constant for the corresponding random walk. It is shown in particular that for almost all trees, there is an edge whose insertion increases the corresponding value of Kemenyâs constant. Finally, it is proven that for any m â N, almost every tree T has the property that there are at least m trees, none of which are isomorphic to T , such that the values of Kemenyâs constant for the corresponding random walks coincide with the value of Kemenyâs constant for the random walk on T . Several illustrative examples are included.