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 Answer 1

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$
4
  • $\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$ Jul 5, 2014 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, 2014 at 21:37
  • $\begingroup$ What if the graph is directed? $\endgroup$ Jul 6, 2014 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, 2014 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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