N random walkers that hit node v in a graph - MathOverflowmost recent 30 from mathoverflow.net2019-10-20T17:56:17Zhttps://mathoverflow.net/feeds/question/173366https://creativecommons.org/licenses/by-sa/4.0/rdfhttps://mathoverflow.net/q/1733661N random walkers that hit node v in a graphuser1894963https://mathoverflow.net/users/546782014-07-05T14:37:21Z2014-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#1733701Answer by R W for N random walkers that hit node v in a graphR Whttps://mathoverflow.net/users/85882014-07-05T15:26:54Z2014-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>