= Stationary distribution of a graph random walk
{wiki}
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> is
$$
\pi(x)=\frac{\deg(x)}{2|E|}.
$$
More generally, for positive symmetric <edge> <electrical conductances> with no killing, replace the <vertex degree> by $c_x=\sum_yc_{xy}$ and $2|E|$ by $\sum_xc_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\geq1$ 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.
Back to article page