Entropy contractions in Markov chains: Half-step, full-step and continuous-time

This paper considers the speed of convergence (mixing) of a finite Markov kernel P with respect to the Kullback-Leibler divergence (entropy). Given a Markov kernel one defines either a discrete-time Markov chain (with the n-step transition kernel given by the matrix power Pn) or a continuous-time Markov process (with the time-t transition kernel given by et(P −Id)). The contraction of entropy for n = 1 or t = 0+ are characterized by the famous functional inequalities, the strong data processing inequality (SDPI) and the modified log-Sobolev inequality (MLSI), respectively. When P = KK∗ is written as the product of a kernel and its adjoint, one could also consider the “half-step” contraction, which is the SDPI for K, while the “full-step” contraction refers to the SDPI for P . The work [18] claimed that these contraction coefficients (half-step, full-step, and continuous-time) are generally comparable, that is their ratio is bounded from above and below by two absolute constants. We disprove this and related conjectures by working out a number of different counterexamples. In particular, we construct (a) a continuous-time Markov process that contracts arbitrarily faster than its discrete-time counterpart; and (b) a kernel P such that Pm+1 contracts arbitrarily better than Pm. Hence, our main conclusion is that the four standard inequalities comparing five common notions of entropy and variance contraction are generally not improvable (even in the subclass of factorizable Markov chains). In the process of analyzing the counterexamples, we survey and sharpen the tools for bounding the contraction coefficients and characterize properties of extremizers of the respective functional inequalities. For example, we show that while the MLSI extremizers always have full support (unless the MLSI constant equals twice the spectral gap), the SDPI extremizers can have partial support. As our examples range from Bernoulli-Laplace model, random walks on graphs, to birth-death chains, the paper is also intended as a survey on computing MLSI, SDPI and other constants for these types of commonly occurring Markov chains.