On the coalescence time of reversible random walks

Details On the coalescence time of reversible random walks On the coalescence time of reversible random walks

2010-09-03

arxiv.org/abs/1009.0664v3

Mathematics

Probability

29 pages in 11pt font with 3/2 line spacing. v2 has an extra reference and corrects a minor error in the proof of the last cla

Scientific paper

Consider a system of coalescing random walks where each individual performs random walk over a finite graph G, or (more generally) evolves according to some reversible Markov chain generator Q. Let C be the first time at which all walkers have coalesced into a single cluster. C is closely related to the consensus time of the voter model for this G or Q. We prove that the expected value of C is at most a constant multiple of the largest hitting time of an element in the state space. This solves a problem posed by Aldous and Fill and gives sharp bounds in many examples, including all vertex-transitive graphs. We also obtain results on the expected time until only k>1 clusters remain. Our proof tools include a new exponential inequality for the meeting time of a reversible Markov chain and a deterministic trajectory, which we believe to be of independent interest.

Affiliated with

Also associated with

No associations

Rating

On the coalescence time of reversible random walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the coalescence time of reversible random walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the coalescence time of reversible random walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-684932