Return to Colloquia & Seminar listing
Swarms of Random Walkers
Student-Run Discrete Math Seminar| Speaker: | Alexander Waagen, UC Davis |
| Location: | 1147 MSB |
| Start time: | Fri, Jan 7 2011, 11:00AM |
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.