Existence of a stationary distribution for a random walk Consider a random walk on a infinitely countable connected graph.
We assume that each vertex has finitely many neighbors and that we have a uniform bound of the number of neighbors at each vertex.
The probability to move from x to a neighbor y of x is equal to the inverse of the number of neighbors of x.
Can we prove the existence of a invariant probability measure for the corresponding Markov chain? Under which assumptions?
Thanks!
 A: With the given transition law, no invariant probability measure can exist on any connected, undirected graph with finite degrees and a countably infinite set of vertices.
Suppose an invariant probability measure did exist and assigned vertex $x$ probability $\pi_x$.  Set $q_x:=\pi_x/\deg x$.  Then
$$\sum_x q_x=\sum_x \frac{\pi_x}{\deg x}\le \sum_x \pi_x=1.$$
Therefore, $\sum_x q_x$ must be finite, and since some $\pi_x$ must be positive, $\sum_x q_x$ is also positive.
Let $V$ be the  set of vertices.  According to the Markov law, since the measure is invariant,
$$\sum_{y\in V} \pi_y p_{yx} =\pi_x, \qquad \text{for all } x\in V,\tag1$$
where $p_{yx}$ is the probability to make a transition to $x$, starting at $y$.
By assumption, $p_{yx}$ is $1/\deg y$ if $x$ and $y$ are neighbors and $0$ otherwise, so from $(1)$,
$$
\sum_{y \text{ neighbors } x} q_y = \pi_x = q_x \deg x, \qquad \text{for all } x\in V. \tag2 $$
Suppose that there are neighboring vertices $x_0$ and $x_1$ with $q_{x_0}\ne q_{x_1}$.  Without loss of generality, let $q_{x_1}>q_{x_0}$.  Then from $(2)$, $q_{x_1}$ is the average of $q_y$ over the neighbors $y$ of $x_1$, so there must be some neighbor $x_2$ of $x_1$ with $q_{x_2}>q_{x_1}$.  Applying this reasoning repeatedly, we get a sequence $x_0$, $x_1$, $x_2$, $\dots$ of vertices, necessarily distinct, with $q_{x_{i+1}}>q_{x_i}$ for all $i$.  This is impossible as then
$\sum_i q_{x_i}=\infty$.
So, any pair of neighboring vertices $x$ and $y$ must have $q_x=q_y$.  Since the graph is connected, this means that $q_x$ is constant at some value, say $Q$.  This is also impossible as then either $Q=0$ and so $\sum_x q_x=0$ or $Q>0$ and so $\sum_x q_x=\infty$.  Therefore there is no invariant probability measure.
