= Solution
For the usual undirected graph with at least two vertices, a <simple random walk> chooses a neighbor uniformly at each step, so $P_{ij}=1/d_i$ when $i$ and $j$ are adjacent and zero otherwise, where $d_i$ is the <degree of a vertex>. The <handshaking lemma> gives $\sum_id_i=2|E|$. Thus the <stationary distribution of a graph random walk> is
$$
\boxed{\pi_i=\frac{d_i}{2|E|}.}
$$
For adjacent $i,j$, $\pi_iP_{ij}=1/(2|E|)=\pi_jP_{ji}$, and for nonadjacent pairs both sides vanish. By <detailed balance>, this is an <invariant distribution> and the walk started from it is a <reversible Markov chain>. Connectedness makes the finite walk an <irreducible Markov chain>, giving uniqueness of its <invariant distribution>. No aperiodicity assumption is needed for uniqueness, so a bipartite graph is allowed.
If the connected graph has a single isolated vertex, the usual neighbor-choice formula is undefined. With the natural absorbing convention $P_{11}=1$, its unique <invariant distribution> is $\pi_1=1$ and it is reversible. The degree-normalization formula presupposes at least one edge.
Back to article page
