Papers on Random Walks

In a simple random walk on an undirected graph, the next vertex to be visited is chosen uniformly at random from the set of neighbors of the current vertex. The cover time is the expected number of steps until all vertices are visited. Most of my work on random walks involves the cover time and related notions. A list of references appears below. The links included are to personal copies (ps/pdf files) of these papers on my home machine. All these personal copies predated the journal copies. These links do not lead to the respective journal. You are expected to respect all relevant copyright laws.


A power point presentation on the cover time of random walks. 2008

The following papers give bounds on the cover time. The bounds are expressed as functions of the number of vertices in the graph, and are best possible up to low order terms.
A Tight Upper Bound on the Cover Time for Random Walks on Graphs. Random Structures and Algorithms, 6(1), 51--54, 1995.
A Tight Lower Bound on the Cover Time for Random Walks on Graphs. Random Structures and Algorithms, 6(4), 433--438, 1995.

The following paper (with Don Coppersmith and James Shearer) shows upper bounds that are expressed as a function of the "virtual resistance" of a graph, a parameter that measures the regularity of the graph. The more regular a graph is, the better the bounds.
Random Walks on Regular and Irregular Graphs. SIAM Journal on Discrete Mathematics, 9(2), 301--308, 1996.

The following paper refines the spanning tree argument and obtains stronger upper bounds on the cover time. Among other things, it is proved that the path is the tree with highest cover time.
Collecting Coupons on Trees, and the Analysis of Random Walks. Computational Complexity 6 (1996/1997), 341--356.

The following papers (first with Yuri Rabinovich, second with improved analysis with Eden Chlamtac) give a deterministic polynomial time algorithm that approximates the cover time within polylogarithmic factors. The algorithms works regardless of the starting point of the random walk, and extends to arbitrary reversible Markov chains.
Deterministic Approximation of the Cover Time. Random Structures and Algorithms, 23(1), 1--22, 2003.
Improved Approximation of the Minimum Cover Time. Theor. Comput. Sci. 341(1-3): 22-38 (2005).

The following paper (together with Ofer Zeitouni) presents a deterministic algorithm that approximates the cover time of trees to any desired degree of accuracy, though the running time deteriorates the higher the accuracy required.
Deterministic Approximation for the Cover Time of Trees. In arxiv.org, September 2009.

The following papers (the first of which is with Greg Barnes) contain results on the rate at which a random walk discovers previously unvisited vertices (the short term behavior of random walks), and use them to obtain better time-space tradeoffs for randomized s-t connectivity algorithms. The second of these papers introduced the notion of virtual resistance, mentioned above.
Short Random Walks on Graphs. SIAM Journal on Discrete Mathematics, 9(1), 19--28, 1996.
A Spectrum of Time-Space Tradeoffs for Undirected s-t Connectivity. Journal of Computer and System Sciences, 54(2), 305--316, 1997.

The following paper shows a randomized space-efficient algorithm that determines whether a graph is connected. The naive approach is to perform a sufficiently long random walk and check whether all vertices are visited. However, it is difficult to implement this approach in logarithmic space (without making the walk unnecessarily long), because there is insufficient space to record which vertices have been visited. Instead, the method used is based on using random walks to estimate the size of connected components.
A Fast Randomized LOGSPACE Algorithm for Graph Connectivity. Theoretical Computer Science 169, 147--160, 1996.

The following paper (with Roee David) considers random walks in which each edge of the graph has resistance equal to the minimum degree of its endpoints, and at any given vertex, the walk chooses an outgoing edge with probability inversely proportional to the resistance of the the edge. The main result is a proof of a conjecture of Abdullah, Cooper and Draief [2015] that for every connected graph, the cover time of such walks is at most O(n^2).
Random walks with the minimum degree local rule have O(n^2) cover time In arxiv.org, April 2016.