Let $G = (V,E)$ be an undirected finite graph and let $\deg(i)$ be the degree of a vertex $i$. Let the transition matrix $P$ of the random walk be given by
$$
P(i,j) = \begin{cases}
\frac{1}{\text{deg}(i)}, & (i,j) \in E \\
0, & (i,j) \notin E
\end{cases}
$$
and let the walk be reversible wrt some stationary distribution. Find a stationary distribution.
If $\pi$ is a stationary distribution $\pi(i)\times \frac{1}{\text{deg}(i)} = \pi(j)\times \frac{1}{\text{deg}(j)}$ since we have have reversibility. May I know which $\pi$ would satisfy this?
Best Answer
Assuming the graph is connected: Since $\pi(i) / \deg(i)$ is constant, you're looking for $\pi$ to be proportional to $\deg(i)$ and to have the property that $\sum_x \pi(x) = 1$. These two properties completely specify $\pi$.
To be a bit more explicit: consider $m(i) = \deg(i)$; this is a stationary measure. Then, the stationary distribution is $\pi(i) = m(i) / \sum_x \pi(x)$.