Probability Seminar: Recurrence of the Simple Random Walk Path
Speakers
Details
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.
Additional Information
This is a Past Event
Event Type
Scientific, Seminar
Date
November 25, 2009
Time
-
Location