Recurrence of the Simple Random Walk Path

January 2, 2008
Ori Gurel-Gurevich | Weizmann Institute of Science

A simple random walk (SRW) on a graph is a Markov chain whose state space is the vertex set and the next state distribution is uniform among the neighbors of the current state. A graph is called recurrent if a SRW on it returns to the starting vertex with probability 1, and called transient otherwise. The path of a walk on a graph is simply the set of edges this walk has traversed.

Our main result is that the path of a SRW on any graph is a recurrent graph. The proof uses the electrical network interpretation of random walks.

We will give a sketch of the proof, including the necessary background, and discuss related questions and conjectures.

Based on joint works with Itai Benjamini, Russell Lyons and Oded Schramm.

Speaker Details

Ori Gurel-Gurevich is currently finishing his PhD at the Weizmann Institute of Science in Israel. He received his MSc and BSc from Tel-Aviv University and worked as a Mathematical researcher in the Israel Defense Forces.