%0 Journal Article %1 oliveira2012coalescence %A Oliveira, Roberto Imbuzeiro %D 2012 %J Trans. Amer. Math. Soc. %K bounds coalescent_theory coalescent_time consensus_time probability_theory random_walks_on_graphs voter_model %N 4 %P 2109--2128 %R 10.1090/S0002-9947-2011-05523-6 %T On the coalescence time of reversible random walks %U http://dx.doi.org/10.1090/S0002-9947-2011-05523-6 %V 364 %X Abstract: Consider a system of coalescing random walks where each individual performs a 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 $ k2$ 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.

@article{oliveira2012coalescence, abstract = { Abstract: Consider a system of coalescing random walks where each individual performs a random walk over a finite graph $ \mathbf {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 $ \mathbf {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\geq 2$ 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. }, added-at = {2016-03-15T22:09:06.000+0100}, author = {Oliveira, Roberto Imbuzeiro}, biburl = {https://www.bibsonomy.org/bibtex/2d5c37f8b5347b27b9edb5b9ccea30106/peter.ralph}, coden = {TAMTAM}, doi = {10.1090/S0002-9947-2011-05523-6}, fjournal = {Transactions of the American Mathematical Society}, interhash = {f19d15917951da45832245daba22968a}, intrahash = {d5c37f8b5347b27b9edb5b9ccea30106}, issn = {0002-9947}, journal = {Trans. Amer. Math. Soc.}, keywords = {bounds coalescent_theory coalescent_time consensus_time probability_theory random_walks_on_graphs voter_model}, mrclass = {60J27 (60K35)}, mrnumber = {2869200}, number = 4, pages = {2109--2128}, timestamp = {2016-03-15T22:09:06.000+0100}, title = {On the coalescence time of reversible random walks}, url = {http://dx.doi.org/10.1090/S0002-9947-2011-05523-6}, volume = 364, year = 2012 }