Seminar | September 18 | 2-3 p.m. | 891 Evans Hall
Nick Bhattacharya, UC Berkeley
We will first discuss the problem of sampling from a given distribution on a graph. We then discuss a more problem - given a set of configurations on the vertices of a graph (for example colorings), how do we sample from that? These problems are addressed by the so-called Glauber Dynamics and the Metropolis Algorithm.
Second, we will give some basic results relating mixing times, total variation distance and couplings. The techniques will illustrated with examples throughout. Time permitting, we may discuss some advanced techniques for coupling Markov chains across their entire trajectories.