Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Petra Berenbrink

LFCS Seminar: Petra Berenbrink

— filed under:

Speeding up random walks

  • LFCS Seminar
When Dec 13, 2011
from 04:00 PM to 05:00 PM
Where IF 4.31-4.33
Contact Name
Add event to calendar vCal


First we consider the following marking random walk process on a connected undirected graph G. Let v denote the vertex visited by the random walk in the current step. If v has not been marked before, then mark it. If v is already marked, then mark a randomly chosen unmarked neighbor of v, if any. In the next step proceed to a random neighbor, according to the random walk process. We also consider a variant of the process, which first assigns to each vertex a global random rank. Our results imply that on many important graph classes, random walks which are allowed to mark (cover) neighbors, have same cover time as the corresponding centralized coupon collecting process.

Then consider  a modified random walk which makes transitions using unvisited edges whenever possible.  Our main result is the following: Let G=G(r,n) be a random r-regular graph of constant even degree r >= 4, and vertex set of size n.  We prove that with high probability, the cover time of G by the walk is O(n). This is to be compared with the O(n log n) cover time of  G by a simple random walk.

We  provide  empirical evidence to suggest that the  same process behaves asymptotically worse on random regular graphs of odd degree, and that a related process which moves to an unvisited neighbour whenever possible, behaves asymptotically worse on random regular graphs of  even  degree. As far as we know, this is the first theoretical analysis of the cover time of a non-Markovian process on a general class of graphs. Our study supports the intuitive idea that  random walks which prefer unvisited vertices or edges may have  an improved cover time.

Joint work with Colin Cooper, Robert Elsaesser, Tom Friedetzky, Tomasz Radzik and Thomas Sauerwald

Document Actions