Consider a random walk on an connected, non-bipartite, undirected graph G. Show that, in the long run, the walk will traverse each edge with equal probability.

Note: The walk can traverse each edge in two directions.


If I understand the model correctly, at any vertex the particle chooses one of the outgoing edges with equal probability. If that is the case, then the transition probabilities of the discrete-time Markov chain are given by: $$ P_{i,j} = \frac{1}{E_i}, $$ where $E_i$ is number of edges connected to vertex $i$.

One can they verify that the stationary measure of this chain (assuming finite state space) is : $$ \pi_i = \frac{E_i}{\sum_k E_k}. $$

Since, any outgoing edge will be selected uniformly at random, the fraction of the times the chain will traverse an edge $e_{i,j}$ is then $$ \frac{1}{\sum_k E_k}, $$ which is the same for any edge $e_{i,j}$.


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.