## Probability Seminar: Recurrence of the Simple Random Walk Path

- Date: 11/25/2009

University of British Columbia

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.

3:00pm - 4:00pm, WMAX 110.