04.12.2023 (Monday)

PR KCL Probability Seminar: Fastest-Mixing Markov Chain on a Graph

regular seminar Sam Olesker-Taylor (University of Warwick)

at:
15:00 - 16:00
KCL, Strand
room: S4.29
abstract:

Given a graph G = (V,E), consider the set of all discrete-time, reversible Markov chains with equilibrium distribution uniform on V and transitions only across edges E of the graph. We establish a Cheeger-type inequality for the fastest mixing time using the vertex conductance of G. We also consider chains with almost-uniform invariant distribution. Time permitting, we also discuss a construction of a continuous-time chain with exactly-uniform invariant distribution and average jump-rate 1, and mixing time bounded by the d^2 log(n), where d is the graph diameter and n is the number of vertices.

Keywords: Markov chain, mixing time, Cheeger inequality

n/a