9
$\begingroup$

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$?

$\endgroup$
4
  • 3
    $\begingroup$ Is that even true in a regular tree?! $\endgroup$ Commented Jul 8, 2021 at 20:21
  • 1
    $\begingroup$ @FedorPetrov: They cannot for a lazy random walk, I suppose? $\endgroup$ Commented Jul 8, 2021 at 21:44
  • 1
    $\begingroup$ Hmm, what's "lazy"? (I should know... :) but...). $\endgroup$
    – Wlod AA
    Commented Jul 9, 2021 at 5:50
  • $\begingroup$ Ah, I just googled that lazy means that we may also stay (with probability 1/2). $\endgroup$ Commented Jul 9, 2021 at 8:05

1 Answer 1

9
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .