Consider $n$ individuals performing an independent random walk on the same digraph. For simplicity assume that the graph is strongly connected. What can we say regarding the expected number of individuals at a node?

For instance, if this were a single individual performing a random walk modeled by a discrete time Markov chain, the stationary distribution would be enough.

Do closed forms exist for multiple individuals when walks are modeled by Markov chains?

If not can a reference be provided for walks/graph classes for which they do exist?

  • $\begingroup$ If the individuals have no influence on each other, you only need to look at combination of multiple stationary distributions, so the relation to random walks drops out. $\endgroup$ – quarague Mar 19 at 7:56
  • $\begingroup$ @quarague Yes, I understand that. However this gets messy with the multiple combinations. Perhaps something analytic like in this paper $\endgroup$ – kva Mar 19 at 8:02
  • $\begingroup$ The paper you linked looks at questions on when and where different random walkers meet. This depends on the specific random walks. If I understand your question correctly, you are only interested at the outcome. So if one random walker is at a specific vertex with probability $p$ according to the stationary distribution, then the expected number with $n$ random walkers is just $np$. $\endgroup$ – quarague Mar 19 at 8:27

Your Answer

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

Browse other questions tagged or ask your own question.