Random walk on a finite graph. Why will I reach every vertex?

314 Views Asked by At

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?

1

There are 1 best solutions below

5
On

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.