Coalescent random walks on graphs

Jianjun Paul Tian, Zhenqiu Liu

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Inspired by coalescent theory in biology, we introduce a stochastic model called "multi-person simple random walks" or "coalescent random walks" on a graph G. There are any finite number of persons distributed randomly at the vertices of G. In each step of this discrete time Markov chain, we randomly pick up a person and move it to a random adjacent vertex. To study this model, we introduce the tensor powers of graphs and the tensor products of Markov processes. Then the coalescent random walk on graph G becomes the simple random walk on a tensor power of G. We give estimates of expected number of steps for these persons to meet all together at a specific vertex. For regular graphs, our estimates are exact.

Original languageEnglish (US)
Pages (from-to)144-154
Number of pages11
JournalJournal of Computational and Applied Mathematics
Issue number1 SPECIAL ISSUE
StatePublished - May 1 2007

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Coalescent random walks on graphs'. Together they form a unique fingerprint.

Cite this