Convex Relative Entropy Decay in Markov Chains

Abstract—We look at irreducible continuous time Markov chains with a finite or countably infinite number of states, and a unique stationary distribution pi. If the Markov chain has distribution µt at time t, its relative entropy to stationarity is denoted by h(µt|pi). This is a monotonically decreasing function of time, and decays to 0 at an exponential rate in most natural examples of Markov chains arising in applications. In this paper, we focus on the second derivative properties of h(µt|pi). In particular we examine when relative entropy to stationarity exhibits convex decay, independent of the starting distribution. It has been shown that convexity of h(µt|pi) in a Markov chain can lead to sharper bounds on the rate of relative entropy decay, and thus on the mixing time of the Markov chain. We study certain finite state Markov chains as well as countable state Markov chains arising from stable Jackson queueing networks