Let $G$ be an infinite countable non-oriented connected graph with bounded degrees. Let $X(n)$ be the lazy random walk on $G$ and let $u,v$ be two vertices. Does the ratio $P(X(n)=v)/P(X(n)=u)$ tend to the ratio between the degrees of $u$ and $v$?
-
3$\begingroup$ Is that even true in a regular tree?! $\endgroup$– Stefan WitzelCommented Jul 8, 2021 at 20:21
-
1$\begingroup$ @FedorPetrov: They cannot for a lazy random walk, I suppose? $\endgroup$– Mateusz KwaśnickiCommented Jul 8, 2021 at 21:44
-
1$\begingroup$ Hmm, what's "lazy"? (I should know... :) but...). $\endgroup$– Wlod AACommented Jul 9, 2021 at 5:50
-
$\begingroup$ Ah, I just googled that lazy means that we may also stay (with probability 1/2). $\endgroup$– Fedor PetrovCommented Jul 9, 2021 at 8:05
1 Answer
You haven't defined what "the lazy random walk" is. Since you refer to the vertex degrees, I presume that you mean that the transition probabilities are $$ p(x,y) = \begin{cases} \frac12 \;, & \text{if}\; x=y \;,\\ \frac1{2\,\mathbf{deg}\,x } \;, & \text{if}\; x,y\;\text{are neighbours} \;. \end{cases} $$ What you are asking about is known as the strong ratio limit property (SRLP) for Markov chains (one also uses the abbreviation SRLT where T stands for "theorem"). This terminology was introduced by Kingman and Orey in 1964, and the subject was popular in the 60s-70s.
The first observation is that if the SRLP holds then the return probabilities $p^n(x,x)$ should decay subexponentially ($\equiv$ the spectral radius of the random walk is 1), which automatically excludes random walks on non-amenable graphs (these are precisely the ones for which the spectral radius is strictly less than one). An example of a non-amenable graph is provided by homogeneous trees (mentioned in one of the comments).
In what concerns amenable graphs, the SLRP has been proved for random walks on amenable groups (in particular, for simple random walks on the Cayley graphs of finitely generated amenable groups) by Avez in 1973. I am not aware of any results for random walks on arbitrary amenable graphs. However, there is a counterexample to the SLPR for a general (not reversible) Markov chain due to Freeman Dyson and described on pp. 55-56 of Kai Lai Chung's book Markov chains with stationary transition probabilities.