Please Note: This seminar will be given in person.
|
Probability seminar series Lap Chi Lau Room: M3 3127 |
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.
