# N random walkers that hit node v in a graph

Consider a finite, undirected graph G, 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 all of the three random walkers will together hit a specific node v at: - the same time. - different times. Given that the three nodes are randomly chosen.

Thank you

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.
• Given points $x,y$ from the state space let $T(x,y)$ be the set of times $t\ge 0$ such that $y$ is attainable from $x$ in $t$ steps. Then either for any $x,y$ the set $T(x,y)$ contains all sufficiently large integers (aperiodic case), or for any $x,y$ the parity of all numbers in $T(x,y)$ is the same (bipartite case). The simplest examples are the standard Cayley graphs of the groups $\mathbb Z_{2d+1}$ and $\mathbb Z_{2d}$, respectively. – R W Jul 5 '14 at 21:37