
Discrete Mathematics and Optimization Seminar

Mar. 28th, 2011
Roberto Imbuzeiro Oliveira
On the coalescence time of reversible random walks
IMPA

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 vertextransitive, 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)



