Probability of random walk traversal 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}$.