Consider a random walk on an infinite connected vertex-transitive graph. Let $f(t)=P_{o,o}^{2t}$ be the probability that the random walk is at its origin at time $2t$. What can be said about the asymptotics of $f(t)$? Specifically, I would like to know whether $\lim_{t\to\infty}\frac {\log f(t)}{\log t}$ always exists (possibly $-\infty$). If not, how large can the ratio between the limit-superior and limit-inferior be?
Asymptotics of Return Probabilities in Random Walks on Transitive Graphs
pr.probabilityrandom walks
Best Answer
the limit $L=\lim_{t\to\infty}\frac {\log f(t)}{\log t}$ always exists, in the wide sense. If a transitive graph does not have polynomial growth, then the limit is $-\infty$, while if it has polynomial growth, the exponent is necessarily an integer $d$ by Trofimov's [1] extension of Gromov's Theorem, and in that case the limit $L$ equals $-d/2$. For a discussion with references see page 226 in [2], or Theorems 14.12 and 14.19 in [3] or Corr. 6.2.5 in [4].
[1] Trofimov, V.I. (1984) Graphs with polynomial growth. Mat. Sb. (N.S.), 123(165)(3), 407–421. English translation: Math. USSR-Sb. 51 (1985), no. 2, 405–417. MR: 735714
[2] Lyons, Russell, and Yuval Peres. Probability on trees and networks. Vol. 42. Cambridge University Press, 2017.
[3] Woess, W. (2000) Random Walks on Infinite Graphs and Groups. Vol. 138 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge. MR: 2001k:60006
[4] http://pi.math.cornell.edu/~lsc/papers/surv.pdf