N random walkers that hit node v in a graph - MathOverflow most recent 30 from mathoverflow.net 2019-10-20T17:56:17Z https://mathoverflow.net/feeds/question/173366 https://creativecommons.org/licenses/by-sa/4.0/rdf https://mathoverflow.net/q/173366 1 N random walkers that hit node v in a graph user1894963 https://mathoverflow.net/users/54678 2014-07-05T14:37:21Z 2014-11-02T20:11:57Z <p>Consider a finite, undirected graph <strong>G</strong>, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start at three different nodes in the graph), I would like to determine the probability that <strong>all of the three random walkers will <em>together</em></strong> hit a specific node v at: - the same time. - different times. Given that the three nodes are randomly chosen.</p> <p>Thank you</p> https://mathoverflow.net/questions/173366/-/173370#173370 1 Answer by R W for N random walkers that hit node v in a graph R W https://mathoverflow.net/users/8588 2014-07-05T15:26:54Z 2014-07-05T15:26:54Z <p>Since you are talking about finite (and presumable connected) graphs, a.e. sample path (no matter where it starts) visits all vertices, so that the answer to your second question (about probability of visiting the same point at possibly different times) is 1. As for the first question, the answer depends on whether your graph is bipartite or not (in the first case the random walk has period 2, whereas in the second case it is aperiodic). If the random walk is aperiodic then the probability is 1. If not, this is the probability that all \$n\$ starting points belong to the same component of the bipartite decomposition, i.e., \$(P/(P+Q))^n+(Q/(P+Q))^n\$, where \$P\$ and \$Q\$ are the cardinalities of the bipartite decomposition components. </p>