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!
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.