1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I appreciate that, but I am really not familiar with bipartite graphs. Although I read about it, but i don't see that it is applicable in my case (as what I understood is that it divides the nodes into two disjoint sets). Could you please elaborate more and give a simple example. Thank you $\endgroup$ – user1894963 Jul 5 '14 at 18:53
  • $\begingroup$ 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. $\endgroup$ – R W Jul 5 '14 at 21:37
  • $\begingroup$ What if the graph is directed? $\endgroup$ – user1894963 Jul 6 '14 at 10:17
  • $\begingroup$ If any two states still communicate, then it is similar with the exception that in this case the period can be arbitrary (and just 1 or 2 as it was for undirected graphs). If not, one has to look in more detail at the decomposition of the Markov chain into cyclic classes and their complement. $\endgroup$ – R W Jul 6 '14 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.