Coalescent random walks on graphs (Q875357)

The following problem is considered: Given a connected simple graph with \(n\) vertices and \(m\) edges and assume \(k\) persons distributed on the vertices. Several persons may stand together on a vertex and no restrictions are made on \(k\) in relationship to \(n\). At each time step one person can move to one of his neighbor vertices with equal probability. The article studies the question when all \(k\) persons meet for the first time at a specific vertex. The problem is studied by generalizing the concept of tensor powers to a graph as introduced in a paper by the same authors which is yet unpublished. The continuous time Markov chains over the \(k\)th tensor power of the given graph are used to turn the \(k\)-coalescent random walks into simple random walks on its \(k\)th tensor powers. This method is used to obtain the expectation of the time that \(k\) persons starting with any distribution on the graph first meet at a specific vertex. The authors' work was inspired by coalescent theory in biology.