Seminar Details
2013-02-05 (14.00) : Mixing times on the cycle - can we decrease it?
At Euler building
Organized by Mathematical Engineering
Speaker :
Gerencser, Balazs
Abstract :
We want to quickly generate a uniform random node of a graph using a Markov chain. The set of allowed transitions are given as the edges of
the graph but we can choose the transition probabilities. We start with the simple case of finding a quick reversible Markov chain on a cycle.
We then try to decrease the mixing time by different extensions: allowing non-reversible or time-inhomogeneous Markov chains or adding a small number of random edges to the cycle.