Stationary distribution of random walk on a graph

Question

If you do a random walk on an undirected, connected graph, is the stationary distribution for the probability that you have just traversed edge $e$ uniform over all edges no matter what the graph looks like?

Answer 1

Adding something to @gmath answer:

if we want to find the probability that you have just traversed an edge $p_{ij}$, knowing that the distribution on the vertex is stationary ($\pi$), we have

$$ p_{ij}=\frac{\pi_i}{d_i}+\frac{\pi_j}{d_j}=\frac{1}{e} $$

So the distribution on the edge is uniform.

Returning to the original problem, we reach the stationary distribution only if the graph is non bipartite (acyclic in directed graph).

In the bipartite case, we have also a similar stationary distribution, but only by performing two step on the random walk at a time.

An invariant of the distribution of probability in a bipartite graph is in fact the probability to be on a vertex on the left (or right) side of the graph on an even (or odd) step of the random walk.

The two asymptotic distribution that alternate are built like the one above: if $P_R$ is the sum of probability on the right side, and $e$ the number of edges, then every node on the right has a probability of $$ \pi(x)=\mbox{deg}(x)*P_R/e $$ and similar to the left. The other asymptotic distribution has $P_R$ and $P_L$ switched.

In both cases, the probability distribution on the edges is $1/e$, so it holds everywhere.

Answer 2

The stationary measure of a vertex is proportional to its degree. Let $G$ be a graph with $e$ edges. Then for any vertex the stationary probability measure is $$\pi(x) = \deg(x)/2e.$$ To see it is stationary, note $p(x,y) = 1/\deg(x)$ if $x$ is incident to $y$. Hence $$ \sum_{x} \pi(x) p(x,y) = \sum_{x\sim y} \deg(x)\frac{1}{2e\deg(x)} = \deg(y)/2e = \pi(y).$$