TITLE:Stopping Rules and Time Reversal for Random Walks on Graphs
SPEAKER: Andrew Beveridge
WHEN: December 1, 4-5:30pm
WHERE: PPB 300
ABSTRACT: Consider a directed graph $G$ and a random walk on it. Looking at such a walk in reverse gives a random walk on a related directed graph $\hat{G}$. When $G$ is an undirected graph, we have $G=\hat{G}$. One can use and intelligent stopping rule that “looks where it is going” to halt a random walk so that the distribution of the final state is a desired distribution $\tau$. This leads to a number of exact mixing measures that are related to the classical mixing measures (such as the relaxation time). We discuss the effect of time reversal on stopping rules by considering families of rules from singletons to a specified target distribution. We describe a duality between stopping rules on $G$ and stopping rules on $\hat{G}$. In particular, we give a natural proof that the “average mixing time” of a random walk on $G$ is equal to the time it takes for a random walk on $\hat{G}$ to “forget where it started,” which was originally proved by Lovasz and Winkler via linear programming.
Joint work with Laszlo Lovasz.
