Sum-of-squares proofs of logarithmic Sobolev inequalities on finite Markov chains

Hamza Fawzi
University of Cambridge

Logarithmic Sobolev inequalities play an important role in understanding the mixing times of Markov chains on finite state spaces. It is typically not easy to determine, or indeed approximate, the optimal constant for which such inequalities hold. In this talk, I will describe a semidefinite programming relaxation to produce a lower bound on the logarithmic Sobolev constant of a finite Markov chain. Numerical experiments show that the solution to this relaxation is often very close to the true constant. Finally, we use this relaxation to obtain a sum-of-squares proof that the logarithmic Sobolev constant is equal to half the Poincaré constant for the specific case of a simple random walk on the odd n-cycle, with n in {5,7,…,21}. Previously this was known only for n=5 and even n. Joint work with Oisín Faust.

Presentation (PDF File)

Back to Entropy Inequalities, Quantum Information and Quantum Physics