Discrete Mathematics and Optimization Seminar
Mar. 28th, 2011
Roberto Imbuzeiro Oliveira
On the coalescence time of reversible random walks
Abstract: Consider a system of coalescing random walks over a finite graph G. 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.

We will show that, if G is vertex-transitive, the expected value of C is at most a K times larger than the maximum expected meeting time of two of the random walks, where K does not depend on G. This will be obtained from a more general result on coalescences of reversible random walks, which solves an open problem of Aldous and Fill. Our proof tools include a new (and very elementary) exponential inequality for the meeting time of a reversible Markov chain and a deterministic trajectory, which we believe to be of independent interest.

(Reference: arXiv:1009.0664)