Assume that we have a finite weighted (connected) graph where the random walk chooses an adjacent vertex with probability proportional to the weights of the edges incident to the current vertex.

It is somehow clear that the random walk will reach every vertex of the graph (probably infinitely often) but how can I shows this?


The family $(X_n(\omega))$ has infinitely many $n$ but the $X_n$ are vertex valued, so they are finitely many diferent ones. This proves that at least one vertex will be visited infinitely many times. Now, you (I suppose) assume that the conductances are strictly positive, hence the Markov chain is irreducible, this implies that every vertex in a communication class is either visited finitely often or infinitely many times.

  • $\begingroup$ "...every vertex in a communication class is either visited finitely often or..." So there could be a vertex that is visited zero times?! $\endgroup$ – nabla Apr 27 '17 at 23:12
  • $\begingroup$ Ok I understand, on a finite network it is not possible that every vertex is visited only finitely many times. So in this case every vertex must be visited infinitely many times. Thank you! $\endgroup$ – nabla Apr 27 '17 at 23:25
  • 1
    $\begingroup$ @nabla: Intuitively, the waiting time to visit a vertex $v$ is roughly geometric. Every time you visit $v$'s neighbors, you have a chance of visiting $v$. So the chance of not visiting $v$ tends to 0 in a finite chain. It's a bit of a tautology because you'll also require that you visit $v$'s neighbors infinitely many times, but the nice thing about finite markov chains is that all states in a communication class are the same, so if one is recurrent then so are the others. $\endgroup$ – Alex R. Apr 27 '17 at 23:28
  • $\begingroup$ Is there a way to prove the statement rigorously?? $\endgroup$ – nabla Apr 28 '17 at 10:07
  • $\begingroup$ What of all statements? And what do you mean precisely with rigorously? $\endgroup$ – Will M. Apr 28 '17 at 17:17

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.