Algebraic Graph Theory Seminar - Steve Kirkland

Title: Kemeny's Constant for Markov Chains

Abstract:

Markov chains are a much-studied class of stochastic processes, and it is well-known that if the transition matrix A associated with a Markov chain possesses a certain property (called primitivity), then the long-term behaviour of the Markov chain is described by a particular eigenvector of A, known as the stationary distribution vector. Rather less well-known is Kemeny’s constant for a Markov chain, which can be interpreted in terms of the expected number of time steps taken to arrive at a randomly chosen state, starting from initial state i. In particular, if Kemeny’s constant is small, then we can think of the Markov chain as possessing good mixing properties.

In this talk, we will give a short overview of Kemeny’s constant, and discuss some results dealing with the problem of minimising Kemeny’s constant over transition matrices that are subject various constraints. We will also describe some results showing that Kemeny’s constant can exhibit surprising behaviour when the transition matrix is perturbed. Throughout,  the techniques used rely on matrix theory and graph theory.