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?
3
-
2$\begingroup$ My guess would be that if your graph $G$ "looks" like a $2 + (-1)^n$-dimensional lattice at scale, say, $n^n$, then the limit inerior/superior will be something like $-(2 \pm 1)/2$. $\endgroup$– Mateusz KwaśnickiCommented Jan 13, 2022 at 12:31
-
$\begingroup$ But how can you make the dimension change in different scales if the graph is transitive? $\endgroup$– DorCommented Jan 13, 2022 at 16:52
-
$\begingroup$ @Dor: Good point, of course. I got the question wrong. $\endgroup$– Mateusz KwaśnickiCommented Jan 14, 2022 at 17:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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
answered Jan 13, 2022 at 19:23