Found 2 result(s)

01.01.1970 (Thursday)

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

01.01.1970 (Thursday)

FM Probability Seminar - Sam Olesker-Taylor (University of Warwick)

regular seminar Sam Olesker-Taylor (University of Warwick)

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

Keywords: