Return to Colloquia & Seminar listing
Recurrence of the Simple Random Walk PathMathematical Physics & Probability
|Speaker: ||Ori Gurel-Gurevich, Microsoft Research|
|Location: ||2112 MSB|
|Start time: ||Wed, Nov 26 2008, 4:10PM|
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
We will give a sketch of the proof, including the necessary background,
and discuss related questions, conjectures and results.
Based on joint works with Itai Benjamini, Russell Lyons and Oded Schramm.