LFCS Seminar: Petra Berenbrink
Speeding up random walks
What 


When 
Dec 13, 2011 from 04:00 PM to 05:00 PM 
Where  IF 4.314.33 
Contact Name  James Cheney 
Add event to calendar 
vCal iCal 
Abstract:
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 rregular 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 nonMarkovian 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