 Stationary distribution of a graph random walk

On a finite connected loopless undirected graph with at least two graph vertices, the stationary distribution of a graph random walk for the simple random walk isMore generally, for positive symmetric edge electrical conductances with no killing, replace the vertex degree by $c_x={\sum }_y{c}_{xy}$ and $2|E|$ by ${\sum }_x{c}_x$. The detailed balance identity $\pi (x)P(x,y)=\pi (y)P(y,x)$ proves stationarity directly.

The stationary distribution is uniform precisely when the connected unweighted graph is regular. For a star with $m\ge 1$ leaves, the center has stationary mass $1/2$ and each leaf has stationary mass $1/(2m)$. Starting at the center, the probability distribution alternates between center and leaves, so it does not converge to stationarity without an aperiodicity mechanism such as a positive holding probability. For a disconnected graph, different closed components admit different stationary mixtures; isolated graph vertices require an explicit transition convention.