Does entropy of the random walk control the return probability

Question

Given an infinite connected graph $G$ of bounded degree with vertex set $X$, let $P_x^n$ the time $n$ distribution of the simple random walk started at the vertex $x$ (so $P^n_x(y)$ is the probability that a simple random walk started at $x$ ends at $y$ after $n$ steps). Let further $$ H_n :=\displaystyle \sup_{x \in X} h(P_x^n), \qquad \eta_n := \displaystyle \inf_{x \in X} h(P_x^n) \quad \text{ and } \quad r_n := \displaystyle \sup_{x,y \in X} P_x^n(y). $$ Here $h(\mu) = \sum_y -\mu(y) \ln \mu(y)$ is the entropy of $\mu$. Given that for any measure $\mu$ one has $\displaystyle \sup_{y \in X} \mu(y) \geq e^{-h(\mu)}$, one gets the bound $r_n \geq e^{-H_n}$. One question is:

Question 1: what are upper bounds on $r_n$ in terms of $H_n$ and $h_n$?

Note that in the case of [Cayley graphs of] groups, there is such a bound (the sharpest version known to me is by Peres & Zheng). My question is for "generic" [infinite connected] graphs [of bounded degree].

There is a natural counterpart to the question (which is hopefully easier to get):

Question 2: what are [family of] examples where upper bounds of $r_n$ in terms of $H_n$ and $\eta_n$ are "bad"?

Of course "bad" is not well-defined, but in Cayley graphs it may happen that $r_n$ behaves roughly like $C_1e^{-C_2\sqrt{H_n}}$. I would expect much worse for a graph.

PS: if "generic" needed to be made explicit, then I would say something like: "no finitely generated subgroup of the subgroup of self quasi-isometries of the graph acts co-compactly".

PPS: any result with "lazy random walk" in place of "simple random walk" is also OK.

Answer 1

This is a very partial answer. For simple random walks on Cayley graphs, linear growth of $H_n$ implies that for any $\epsilon>0$, the inequality $r_n \le \exp((\epsilon-1/2)n)$ must hold for infinitely many $n$, see Theorem 1.1 in [1].

For infinite connected graphs of bounded degree, it is possible for $H_n$ to grow linearly while $r_n \asymp cn^{-3/2}$ for even $n$. A simple example is a graph $G$ obtained by adjoining an infinite path to the root of an infinite binary tree. I suspect that slower decay of $r_n$ is not compatible with linear growth of entropy.

(Edit: @tmh Indicated in a comment below that one could get close to decay rate of $1/n$ for $r_n$. So perhaps $1/n$ is a barrier? recall that without any entropy assumptions, the slowest possible decay rate for $r_n$ on an infinite graph of bounded degree is $\;$ const.$/\sqrt{n}$.)

[1] Peres, Yuval, and Tianyi Zheng. "On groups, slow heat kernel decay yields liouville property and sharp entropy bounds." International Mathematics Research Notices 2020, no. 3 (2020): 722-750. https://arxiv.org/abs/1609.05174

Answer 2

Too long for a comment, but I wanted to mention that we encountered some related issues in my recent preprint with Noah Halberstam https://arxiv.org/abs/2203.01540 and thought that the work-arounds we found might be useful to you too.

We would have liked to have argued that if $d(X_0,X_n)$ grows super-diffusively then the Greens function $G(X_0,X_n)$ decays quickly, but this does not seem to be true in general. (Actually we did not find a counterexample, although on page 23 we discuss some constructions related to the comment I wrote, where one has positive speed but slow heat kernel decay.)

For our purposes, we were able to avoid this problem with a nice trick: Introducing spatially-dependent killing to the random walk. If the walk is superdiffusive and one makes the rate of killing decay at a well-chosen rate as a function of the distance from the starting point then return probabilities on the killed network decay quickly but the walk has positive probability to never be killed (see Section 3 of our paper). As such, if you want to use heat kernel estimates to prove some almost-sure property of the random walk, you can run the argument on the network with the spatially-dependent killing to get that the property holds almost surely for the killed walk, then deduce that it also holds almost surely for the original walk by absolute continuity.