Seminar by Lap Chi Lau

Please Note: This seminar will be given in person.

Fastest Mixing Time, Reweighted Eigenvalues, and Cheeger Inequalities

The fastest mixing time problem is to design a Markov chain with a targeted stationary distribution with minimum mixing time.  This problem was studied since 2004, but only recently it was shown that the fastest mixing time of a reversible Markov chain is closely related to the vertex expansion of the underlying undirected graph.  We further extend this result by proving that the fastest mixing time of a general Markov chain is closely related to the vertex expansion of the underlying directed graph.  The main ingredients are the definition of the reweighted eigenvalue of a directed graph and a new Cheeger-type inequality for directed graphs.  No background is assumed.

Joint work with Tsz Chiu Kwok, Kam Chuen Tung, Robert Wang, based on

https://arxiv.org/abs/2203.06168 and https://arxiv.org/abs/2211.09776.