Return to Colloquia & Seminar listing
Swarms of Random Walkers
Student-Run Discrete Mathematics| Speaker: | Alexander Waagen, UC Davis |
| Location: | 1147 MSB |
| Start time: | Fri, Jan 7 2011, 11:00AM |
Description
A recent result, due to Ding, Lee, and Peres (2010), shows that
the expected cover time of a reversible Markov chain can be approximated
in near linear time. This allows one to approximate, for instance, the
cover time of a simple random walk on an undirected graph.
An open question is whether or not the expected cover time of a
non-reversible Markov chain, such as a simple random walk on a directed
graph, can be approximated in polynomial time as well. I will discuss a
possible approach to this problem: using swarms of random walkers to
analyze stopping times on non-reversible Markov chains.