January 01, 1970
We study multiple point ranges for random walks on graphs, extending known asymptotic results obtained for random walks on groups. A distinctive feature is that algebraic and translation-invariance assumptions are replaced by a uniform tail condition on the first return time to the starting point. Under this condition, we obtain upper and lower bounds of linear order for the expectations of the number of sites visited at least a given number of times and the number of sites visited exactly that number of times. We also prove the corresponding almost sure bounds under a stronger condition. In spatially homogeneous transient cases, these bounds coincide and yield a strong law of large numbers. We apply these estimates to derive asymptotic results for functions of the local times.
The range of a random walk is one of the basic quantities measuring how much of the state space the walk has explored. It counts sites without distinguishing how many times they have been visited. In order to describe the occupation structure more finely, we count sites according to their number of visits. For each \(j \ge 1\), we consider the number \(R_n^j\) of sites visited at least \(j\) times by time \(n\), and the number \(R_n^{(j)}\) of sites visited exactly \(j\) times by time \(n\). Here \(R_n^{1}\) is the single point range. These quantities are closely related to self-intersections and to the local times of the walk.
The asymptotic behavior for the multiple point ranges \(R_n^{j}\) and \(R_n^{(j)}\) has been investigated by several authors. For transient random walks, Erdős and Taylor [1] showed the strong law of large numbers for the simple random walk on the integer lattice \(\mathbb{Z}^d, d \ge 3\). Pitt [2] showed the strong law of large numbers for a transient random walk on a countable Abelian group. Derriennic [3] considered a more general class of random walks including the case of random walks on countable non-Abelian groups. Multiple point ranges for the two-dimensional random walk have also been considered by Flatto [4] and Hamana [5], [6]. These works rely on the homogeneous structure of the underlying space. In particular, group structures make it possible to use ergodic methods. For random walks on general graphs, such tools do not apply. This motivates the use of assumptions formulated in terms of return probabilities, rather than algebraic structure.
The aim of this paper is to obtain analogues of known asymptotic results for multiple point ranges for random walks on graphs. Instead of relying on translation invariance or ergodic arguments, we assume a uniform tail condition for the first return time to the starting point. Under this condition, we prove upper and lower bounds of linear order for the expectations of \(R_n^j\) and \(R_n^{(j)}\). Furthermore, under a stronger uniform tail condition, we obtain the corresponding almost sure bounds. If the probability of returning to the starting point is independent of the starting point and is strictly less than one, then the upper and lower bounds coincide and a strong law of large numbers holds.
The case of sites visited at least once corresponds to the single point range. Our results also recover estimates for the single point range, and the uniform tail condition here is weaker than the one used by the author [7] and by Kumagai and Nakamura [8]. As discussed in Section 4, this condition can be verified through on-diagonal heat kernel upper bounds. It is therefore applicable to a broad class of transient random walks on graphs.
Multiple point ranges are closely related to functions of the local times. For transient random walks on lattices and groups, asymptotic properties of local time functionals have been studied by several authors. Becker and König [9] investigated moments of the local times of transient random walks on \(\mathbb{Z}^d\). Asymont and Korshunov [10] considered a more general class of functions of the local times. Recently, Chang, Chen, Meng and Peng [11] obtained further limit results for such functionals. These results are proved for integer lattices and groups.
We consider the corresponding problem for random walks on graphs in Section 3. For a non-negative function \(f\) with \(f(0)=0\), let \(G_n(f)\) be the sum obtained by applying \(f\) to the local time of each site visited up to time \(n\). Combining a decomposition by local time levels with our estimates for exact multiple point ranges \(R_n^{(j)}\), we obtain asymptotic results for \(G_n(f)\) under suitable summability conditions on \(f\). The local time results are graph analogues of known results in the lattice and group settings and include an extension of [11] and of the \(L^2\)-convergence part of [10].
Let \(\mathcal{X}\) be a countable set. Let \((X_n)_{n=0}^{\infty}\) be an irreducible Markov chain on \(\mathcal{X}\). If \(P(X_0 = x) = 1\), then we denote the law of the Markov chain \((X_n)_n\) by \(P^x\). We denote the expectation with respect to \(P^x\) by \(E^x\).
Let \(\ell(n,x) \mathrel{\vcenter{:}}= |\{i \in \{1,\dots,n\} : X_i = x \}|\). For \(j \ge 1\) and \(n \ge 1\), let \[R_n^{j} \mathrel{\vcenter{:}}= \left|\left\{x \in \mathcal{X} : \ell(n,x) \ge j\right\}\right|\] and \[R_n^{(j)} \mathrel{\vcenter{:}}= \left|\left\{x \in \mathcal{X} : \ell(n,x) = j\right\}\right|.\] We remark that \(R_n \mathrel{\vcenter{:}}= R_n^1\) is the range of the random walk and \(R_{n}^{j} = R_{n}^{(j)} + R_n^{j+1}\).
For \(x \in \mathcal{X}\), let \(T_{x} \mathrel{\vcenter{:}}= \inf\{n \ge 1 : X_n = x \}\). Let \[F_{\inf} \mathrel{\vcenter{:}}= \inf_{x \in \mathcal{X}} P^x (T_x < \infty), \;\mathrm{ and } \; F_{\sup} \mathrel{\vcenter{:}}= \sup_{x \in \mathcal{X}} P^x (T_x < \infty).\]
We introduce the following uniform tail condition for the first return time to the starting point. We say that \((U_0)\) holds if \[\lim_{n \to \infty} \sup_{x \in \mathcal{X}} P_x (n < T_x < \infty) = 0,\] and that \((U_1)\) holds if \[\sup_{x \in \mathcal{X}} P_x (n < T_x < \infty) = O\left((\log n)^{-1-\delta} \right), \;n \to \infty.\]
Theorem 1. If \((U_0)\) holds, then, for every \(j \ge 1\), \[\begin{align} (F_{\inf})^{j-1} (1-F_{\sup}) &\le \liminf_{n \to \infty} \frac{\inf_{x \in \mathcal{X}} E^{x} \left[R_n^j \right]}{n} \\ &\le \limsup_{n \to \infty} \frac{\sup_{x \in \mathcal{X}} E^{x} \left[R_n^j \right]}{n} \le (F_{\sup})^{j-1} (1-F_{\inf}) \end{align}\] and \[\begin{align} (F_{\inf})^{j-1} (1-F_{\sup})^2 &\le \liminf_{n \to \infty} \frac{\inf_{x \in \mathcal{X}} E^{x} \left[R_n^{(j)} \right]}{n} \\ &\le \limsup_{n \to \infty} \frac{\sup_{x \in \mathcal{X}} E^{x} \left[R_n^{(j)} \right]}{n} \le (F_{\sup})^{j-1} (1-F_{\inf})^2. \end{align}\]
If the Markov chain \((X_n)_n\) is the simple random walk on a vertex-transitive graph or the random walk on a countable group, then \(F_{\sup} = F_{\inf}\). If the Markov chain \((X_n)\) is recurrent, then \(F_{\sup} = F_{\inf} = 1\). \((U_0)\) is identical with the condition in [7].
Theorem 2. If \((U_1)\) holds, then, for every \(j \ge 1\) and every \(x \in \mathcal{X}\), the following statements hold \(P^x\)-a.s.: \[\label{eq:upper-SLLN-1} \limsup_{n \to \infty} \frac{R_n^j}{n} \le (F_{\sup})^{j-1} (1-F_{\inf}). \;\qquad{(1)}\] \[\label{eq:upper-SLLN-2} \limsup_{n \to \infty} \frac{R_n^{(j)}}{n} \le (F_{\sup})^{j-1} (1-F_{\inf})^2.\qquad{(2)}\] \[\label{eq:lower-SLLN-1} \liminf_{n \to \infty} \frac{R_n^j}{n} \ge (F_{\inf})^{j-1} (1-F_{\sup}). \;\qquad{(3)}\] \[\label{eq:lower-SLLN-2} \liminf_{n \to \infty} \frac{R_n^{(j)}}{n} \ge (F_{\inf})^{j-1} (1-F_{\sup})^2.\qquad{(4)}\]
In Section 4, we give a sufficient condition for \((U_1)\) in terms of heat kernel. To our knowledge, the Nash-type on-diagonal heat kernel upper bounds needed to verify \((U_1)\) are not known to hold for all transient random walks on countable groups. However, under additional assumptions, Nash-type bounds and related estimates have been studied extensively; see Saloff-Coste and Zheng [12] for example. We remark that there exist infinite vertex-transitive graphs which are not Cayley graphs of groups, as shown by Woess [13].
In this section, we prove Theorems 1 and 2. As an outline, we follow [2]; in particular, we use induction on \(j\) in the estimates of expectations. However, we cannot apply the ergodic theorem and several parts of the argument have to be changed significantly. The main difficulty is to estimate \(E_{m,n}\) defined in 10 below. In [2], this part is handled by the ergodic theorem; here we use the uniform tail condition \((U_1)\) instead.
Let \(\mathcal{A}_{k}^{n} \mathrel{\vcenter{:}}= \left\{X_k \ne X_{\ell}, k+1 \le \ell \le n \right\}\) for \(k < n\) and \(\mathcal{A}_{n}^{n}\) be the whole event. Let \(\mathcal{B}_{k}^{(j)} \mathrel{\vcenter{:}}= \left\{ |\{i \in \{1,\dots,k\} : X_i = X_{k} \}| = j \right\}\). We remark that \(\mathcal{B}_{k}^{(j)} = \emptyset\) if \(j > k\). Then, \[R^{(j)}_{n} = \sum_{k=1}^{n} {\boldsymbol{1}}_{\mathcal{B}_{k}^{(j)} \cap \mathcal{A}_{k}^{n}}, \mathrm{ and } R^{j}_{n} = \sum_{k=1}^{n} {\boldsymbol{1}}_{\mathcal{B}_{k}^{(j)}}.\] Hence, for every \(x \in \mathcal{X}\), \[\label{eq:basic-exp-1} E^x \left[ R^{(j)}_{n} \right] = \sum_{k=1}^{n} P^x \left(\mathcal{B}_{k}^{(j)} \cap \mathcal{A}_{k}^{n}\right) \mathrm{ and } E^x \left[ R^{j}_{n} \right] = \sum_{k=1}^{n} P^x \left(\mathcal{B}_{k}^{(j)} \right).\tag{1}\]
For \(n \ge 0\), let \[F_{\inf} (n) \mathrel{\vcenter{:}}= \inf_{x \in \mathcal{X}} P^x (T_x \le n) \;\mathrm{ and } \; F_{\sup} (n) \mathrel{\vcenter{:}}= \sup_{x \in \mathcal{X}} P^x (T_x \le n).\]
Then, by the Markov property, \[\label{eq:basic-Markov-ineq} 1 - F_{\sup}(n-k) \le P^x \left( \mathcal{A}_{k}^{n} \, \middle| \, \mathcal{B}_{k}^{(j)} \right) \le 1 - F_{\inf}(n-k), \;x \in \mathcal{X}.\tag{2}\]
First, we deal with the upper bounds. By 1 and 2 , \[E^x \left[ R^{(j)}_{n} \right] \ge \sum_{k=1}^{n} P^x \left(\mathcal{B}_{k}^{(j)} \right) (1- F_{\sup}(n-k)), \;x \in \mathcal{X}.\] Using this, 1 , and the fact that \(F_{\sup}(m) \le F_{\sup}\) for each \(m \ge 1\), it holds that \[\label{eq:comparision-ineq-1} E^x \left[ R^{(j)}_{n} \right] \ge (1-F_{\sup}) E^x \left[ R^{j}_{n} \right], \;x \in \mathcal{X}.\tag{3}\] Since \(R_n^j - R_n^{j+1} = R_n^{(j)}\), \[E^x \left[ R^{j+1}_{n} \right] \le F_{\sup} E^x \left[ R^{j}_{n} \right], \;x \in \mathcal{X},\] and hence, \[\label{eq:exp-unif-upperbound} \sup_{x \in \mathcal{X}} E^x \left[ R^{j+1}_{n} \right] \le F_{\sup} \sup_{x \in \mathcal{X}} E^x \left[ R^{j}_{n} \right].\tag{4}\]
We see that \[\limsup_{n \to \infty} \frac{\sup_{x \in \mathcal{X}} E^{x} \left[R_n \right]}{n} \le 1 - F_{\inf}.\] Hence, by induction on \(j\), \[\label{eq:upper-exp-1} \limsup_{n \to \infty} \frac{\sup_{x \in \mathcal{X}} E^{x} \left[R_n^j \right]}{n} \le (F_{\sup})^{j-1} (1 - F_{\inf}).\tag{5}\]
We consider \(E^x \left[ R^{(j)}_{n} \right]\). By 1 and 2 , \[\label{eq:upper-exp-2} E^x \left[ R^{(j)}_{n} \right] \le \sum_{k=1}^{n} P^x \left(\mathcal{B}_{k}^{(j)} \right) (1- F_{\inf}(n-k)), \;x \in \mathcal{X}.\tag{6}\] By \((U_0)\), it holds that \[\lim_{n \to \infty} F_{\inf} (n) = F_{\inf} \;\mathrm{ and } \; \lim_{n \to \infty} F_{\sup} (n) = F_{\sup}.\]
Let \(\epsilon > 0\). Let \(N_{\epsilon}\) be an integer such that for every \(n > N_{\epsilon}\), \(F_{\inf}(n) \ge F_{\inf} - \epsilon\). Then, for every \(n > N_{\epsilon}\) and \(x \in \mathcal{X}\), \[\sum_{k=1}^{n} P^x \left(\mathcal{B}_{k}^{(j)} \right) (1- F_{\inf}(n-k)) \le (1 - F_{\inf} + \epsilon) \sum_{k=1}^{n - N_{\epsilon}} P^x \left(\mathcal{B}_{k}^{(j)} \right) + N_{\epsilon}.\] Combining this with 6 and 1 , \[\label{eq:comparision-ineq-2-1} E^x \left[ R^{(j)}_{n} \right] \le (1 - F_{\inf} + \epsilon) E^x \left[ R^{j}_{n} \right] + N_{\epsilon}, \;n > N_{\epsilon}, \;x \in \mathcal{X}.\tag{7}\] By this and 5 , \[\limsup_{n \to \infty} \frac{\sup_{x \in \mathcal{X}} E^{x} \left[R_n^{(j)} \right]}{n} \le (1 - F_{\inf} + \epsilon) (F_{\sup})^{j-1} (1 - F_{\inf}).\] Letting \(\epsilon \to +0\), \[\limsup_{n \to \infty} \frac{\sup_{x \in \mathcal{X}} E^{x} \left[R_n^{(j)} \right]}{n} \le (F_{\sup})^{j-1} (1 - F_{\inf})^2.\]
We now deal with the lower bound. By 7 and \(R_n^j - R_n^{j+1} = R_n^{(j)}\), \[(F_{\inf} - \epsilon) E^x \left[ R^{j}_{n} \right] \le E^x \left[ R^{j+1}_{n} \right] + N_{\epsilon}, \;n > N_{\epsilon}, \;x \in \mathcal{X}.\] Hence, \[(F_{\inf} - \epsilon) \inf_{x \in \mathcal{X}} E^x \left[ R^{j}_{n} \right] \le \inf_{x \in \mathcal{X}} E^x \left[ R^{j+1}_{n} \right] + N_{\epsilon}, \;n > N_{\epsilon}.\] Dividing by \(n\) and letting \(n \to \infty\), \[(F_{\inf} - \epsilon) \liminf_{n \to \infty} \frac{\inf_{x \in \mathcal{X}} E^{x} \left[R_n^j \right]}{n} \le \liminf_{n \to \infty} \frac{\inf_{x \in \mathcal{X}} E^{x} \left[R_n^{j+1} \right]}{n}.\] Letting \(\epsilon \to +0\), \[F_{\inf} \liminf_{n \to \infty} \frac{\inf_{x \in \mathcal{X}} E^{x} \left[R_n^j \right]}{n} \le \liminf_{n \to \infty} \frac{\inf_{x \in \mathcal{X}} E^{x} \left[R_n^{j+1} \right]}{n}.\]
By using the last-exit decomposition as in the proof of [7], we obtain that \[\label{eq:exp-lower-most-basic} E^{x} \left[R_n \right] \ge \sum_{k=1}^{n} \inf_{y \in \mathcal{X}} P^y (T_y \ge k) \ge n \inf_{y \in \mathcal{X}} P^y (T_y = \infty) = n(1 - F_{\sup}).\tag{8}\]
It follows that \[\liminf_{n \to \infty} \frac{\inf_{x \in \mathcal{X}} E^{x} \left[R_n \right]}{n} \ge 1 - F_{\sup}.\] Therefore, by induction on \(j\), \[\label{eq:lower-exp-1} \liminf_{n \to \infty} \frac{\inf_{x \in \mathcal{X}} E^{x} \left[R_n^j \right]}{n} \ge (F_{\inf})^{j-1} (1 - F_{\sup}).\tag{9}\] By this and 3 , \[\liminf_{n \to \infty} \frac{\inf_{x \in \mathcal{X}} E^{x} \left[R_n^{(j)} \right]}{n} \ge (F_{\inf})^{j-1} (1 - F_{\sup})^2.\] This completes the proof.
We first deal with the upper estimates.
Let \[T^{j}_{k,n} \mathrel{\vcenter{:}}= \left|\left\{x \in \mathcal{X} \colon \ell(kn,x) - \ell((k-1)n,x) \ge j \right\}\right|\] and \[T^{(j)}_{k,n} \mathrel{\vcenter{:}}= \left|\left\{x \in \mathcal{X} \colon \ell(kn,x) - \ell((k-1)n,x) = j \right\}\right|.\] Let \(\mathcal{R}_{k,n} \mathrel{\vcenter{:}}= \left\{X_{i} \colon (k-1)n + 1 \le i \le kn \right\}\) and \[\label{eq:Emn} E_{m,n} \mathrel{\vcenter{:}}= \left|\bigcup_{k_1, k_2 \in \{1, \dots, m\}, k_1 \ne k_2} \mathcal{R}_{k_1, n} \cap \mathcal{R}_{k_2, n} \right|.\tag{10}\]
Then, \[R_{mn}^{j} \le \sum_{k=1}^{m} T^{j}_{k,n} + E_{m,n}, \;\mathrm{ and } \; R_{mn}^{(j)} \le \sum_{k=1}^{m} T^{(j)}_{k,n} + E_{m,n}.\] For notational convenience, let \[F^{(u)}_{j} \mathrel{\vcenter{:}}= (F_{\sup})^{j-1} (1-F_{\inf}), \;\mathrm{ and } \;F^{(u)}_{(j)} \mathrel{\vcenter{:}}= (F_{\sup})^{j-1} (1-F_{\inf})^2.\] Then, for every \(\epsilon > 0\), \[P^x \left(R_{mn}^{j} \ge mn(F_j^{(u)} + \epsilon)\right) \le P^x \left( \sum_{k=1}^{m} T^{j}_{k,n} \ge mn \left(F_j^{(u)} + \frac{\epsilon}{2} \right) \right) + P^x \left( E_{m,n} \ge mn \frac{\epsilon}{2} \right).\]
We first give an upper bound for \(\displaystyle P^x \left( \sum_{k=1}^{m} T^{j}_{k,n} \ge mn \left(F_j^{(u)} + \frac{\epsilon}{2} \right) \right)\).
Lemma 3. For every \(\epsilon > 0\), there exists \(\theta(\epsilon) > 0\) such that for every random variable \(Y\) on a probability space satisfying \(|Y| \le 1\), \[\label{eq:every-bdd-rv-Laplace} E\left[\exp(\theta(\epsilon) Y) \right] \le 1 + \theta(\epsilon) (E[Y] + \epsilon) \le \exp\left( \theta(\epsilon) (E[Y] + \epsilon) \right).\qquad{(5)}\]
Proof. By the Lebesgue convergence theorem and the fact that \(E[Y^n] \le 1\), \[E\left[\exp(\theta(\epsilon) Y) \right] = \sum_{n=0}^{\infty} \frac{\theta^n}{n!} E[Y^n] \le 1 + \theta E[Y] + \frac{\theta^2}{2} \exp(\theta).\] Let \(\theta(\epsilon)\) be a positive constant such that \(\theta \exp(\theta) = \epsilon\). Then, using the inequality \(1+x \le \exp(x)\), we have ?? . ◻
Lemma 4. For every \(\epsilon > 0\), there exists \(N(\epsilon) \in \mathbb{N}\) such that for every \(n \ge N(\epsilon)\), \[\label{eq:multi-range-Laplace} \sup_{x \in \mathcal{X}} E^x \left[\exp\left(\frac{\theta(\epsilon/2)}{n} R_n^j \right) \right] \le \exp\left(\theta(\epsilon/2) (F_j^{(u)} + \epsilon) \right),\qquad{(6)}\] where \(\theta (\cdot)\) is the function appearing in Lemma 3.
Proof. Since \(0 \le R^j_n \le n\), by Lemma 3, \[\sup_{x \in \mathcal{X}} E^x \left[\exp\left(\frac{\theta(\epsilon/2)}{n} R_n^j \right) \right] \le \exp\left( \theta(\epsilon/2) \left(\frac{E^x \left[R_n^j \right] }{n} + \frac{\epsilon}{2} \right) \right).\] By Theorem 1, there exists \(N(\epsilon) \in \mathbb{N}\) such that for every \(n \ge N(\epsilon)\), \(\displaystyle \frac{E^x \left[R_n^j \right] }{n} \le F_j^{(u)} + \frac{\epsilon}{2}\). Hence, ?? holds for every \(n \ge N(\epsilon)\). ◻
Lemma 5. For every \(\epsilon > 0\), there exist \(C(\epsilon) > 0\) and \(N_1 (\epsilon) \in \mathbb{N}\) such that for every \(n \ge N_1 (\epsilon)\) and every \(m \in \mathbb{N}\), \[\label{eq:multi-range-tail} \sup_{x \in \mathcal{X}} P^x \left( \sum_{k=1}^{m} T^{j}_{k,n} \ge mn \left(F_j^{(u)} + \frac{\epsilon}{2} \right) \right) \le \exp\left(-C(\epsilon) m \right).\qquad{(7)}\]
Proof. By the Markov property, for every \(\lambda > 0\) and \(x \in \mathcal{X}\), \[P^x \left( \sum_{k=1}^{m} T^{j}_{k,n} \ge mn \left(F_j^{(u)} + \frac{\epsilon}{2} \right) \right) \le \exp\left(-\lambda mn \left(F_j^{(u)} + \frac{\epsilon}{2} \right) \right) E^x \left[ \prod_{k=1}^{m} \exp\left( \lambda T^{j}_{k,n} \right) \right]\] \[\le \left( \exp\left(-\lambda n \left(F_j^{(u)} + \frac{\epsilon}{2} \right) \right) \sup_{x \in \mathcal{X}} E^x \left[ \exp(\lambda R^j_n) \right] \right)^m.\] Let \(n \ge N(\epsilon/4)\) and \(\lambda = \frac{1}{n} \theta(\epsilon/8)\). Then, by Lemma 4, \[\exp\left(-\lambda n \left(F_j^{(u)} + \frac{\epsilon}{2} \right) \right) \sup_{x \in \mathcal{X}} E^x \left[ \exp(\lambda R^j_n) \right] \le \exp\left(- \frac{\epsilon}{4} \theta(\epsilon/8)\right).\] Thus the assertion holds for \(\displaystyle C(\epsilon) \mathrel{\vcenter{:}}= \frac{\epsilon}{4} \theta(\epsilon/8)\) and \(N_1 (\epsilon) \mathrel{\vcenter{:}}= N(\epsilon/4)\). ◻
Second, we give an upper bound for \(\displaystyle P^x \left( E_{m,n} \ge mn \frac{\epsilon}{2} \right)\). Let \[\mathcal{A}_{k}^{\infty} \mathrel{\vcenter{:}}= \left\{X_{\ell} \ne X_k, \ell \ge k+1 \right\} = \bigcap_{n \ge k+1} \mathcal{A}_{k}^n.\] Then, by the same argument as in [2], it holds that for \(n^{\prime} < n\), \[E_{m,n} \le \sum_{k=1}^{mn} {\boldsymbol{1}}_{\mathcal{A}_{k}^{k+n^{\prime}} \setminus \mathcal{A}_{k}^{\infty}} + mn^{\prime}.\]
Henceforth, we denote the integer part of a real number \(x\) by \(\lfloor x \rfloor\). For \(n \ge 2\), let \[\label{eq:def-n-prime} n^{\prime} \mathrel{\vcenter{:}}= \left\lfloor \frac{n}{\log n} \right\rfloor.\tag{11}\] Then, there exists \(N_2 (\epsilon) \in \mathbb{N}\) such that for every \(n \ge N_2 (\epsilon)\), \(n^{\prime}/n < \epsilon/4\). Hence, it holds that for every \(n \ge N_2 (\epsilon)\) and every \(m \ge 1\), \[\label{eq:Emn-upper} P^x \left( E_{m,n} \ge mn \frac{\epsilon}{2} \right) \le P^x \left( \sum_{k=1}^{mn} {\boldsymbol{1}}_{\mathcal{A}_{k}^{k+n^{\prime}} \setminus \mathcal{A}_{k}^{\infty}} \ge mn \frac{\epsilon}{4} \right) \le \frac{4}{\epsilon} \sup_{x \in \mathcal{X}} P^x (n^{\prime} < T_x < \infty).\tag{12}\]
By \((U_1)\), there exists a constant \(C_0\) such that \[\label{eq:c0} \sup_{x \in \mathcal{X}} P^x (n < T_x < \infty) \le C_0 (\log n)^{-1-\delta}, \;\;n \ge 1.\tag{13}\]
Thus, for every \(\epsilon > 0\), every \(n \ge N_1 (\epsilon) + N_2 (\epsilon)\) and every \(m \in \mathbb{N}\), it follows that \[P^x \left(R_{mn}^{j} \ge mn(F_j^{(u)} + \epsilon)\right) \le \exp\left(-C(\epsilon) m \right) + \frac{4C_0}{\epsilon} (\log n - \log \log n)^{-1-\delta}.\]
Let \(\eta > 0\).
For \(m_k = r_k = \lfloor (1+\eta)^{k/2} \rfloor\), \[\exp\left(-C(\epsilon) m_k \right) + \frac{4C_0}{\epsilon} (\log r_k - \log \log r_k)^{-1-\delta} = O\left(k^{-1-\delta}\right), \;k \to \infty.\] Let \(a_k \mathrel{\vcenter{:}}= m_k r_k\). Then, \[\sum_{k=1}^{\infty} P^x \left(R_{a_k}^{j} \ge a_k (F_j^{(u)} + \epsilon)\right) < +\infty,\] and by the Borel-Cantelli lemma, \[\label{eq:lacunary-upper} \limsup_{k \to \infty} \frac{R_{a_k}^{j}}{a_k} \le F_j^{(u)} + \epsilon, \;\mathrm{ P^x-a.s.}\tag{14}\] For \(a_k \le n \le a_{k+1}\), \(\displaystyle \frac{R^j_n}{n} \le \frac{a_{k+1}}{a_k} \frac{R_{a_{k+1}}^{j}}{a_{k+1}}\). By this estimate and the equality \(\displaystyle \lim_{k \to \infty} \frac{a_{k+1}}{a_k} = 1+\eta\), \[\limsup_{n \to \infty} \frac{R_{n}^{j}}{n} \le (1+\eta)(F_j^{(u)} + \epsilon), \;\mathrm{ P^x-a.s.}\] By letting \(\eta \to 0\) and \(\epsilon \to 0\), we see that ?? holds \(P^x\)-a.s.
We now deal with \(R^{(j)}_n\). In the same manner as in the derivation of 14 , we obtain that \[\limsup_{k \to \infty} \frac{R_{a_k}^{(j)}}{a_k} \le F_{(j)}^{(u)} + \epsilon, \;\mathrm{ P^x-a.s.}\] Since \[R_n^{(j)} \le R_{a_{k+1}}^{(j)} + a_{k+1} - a_k, \;a_k \le n \le a_{k+1},\] it holds that \[\limsup_{n \to \infty} \frac{R_n^{(j)}}{n} \le \limsup_{k \to \infty} \frac{a_{k+1}}{a_k} \frac{R_{a_{k+1}}^{(j)}}{a_{k+1}} + \frac{a_{k+1} - a_k}{a_k} \le (1+\eta)(F_{(j)}^{(u)} + \epsilon) + \eta, \;\mathrm{ P^x-a.s.}\] By letting \(\eta \to 0\) and \(\epsilon \to 0\), we see that ?? holds \(P^x\)-a.s.
We now deal with the lower estimates.
We see that \[R_{mn}^{j} \ge \sum_{k=1}^{m} (T^{j}_{k,n} - E_{m,n}), \;\mathrm{ and } \; R_{mn}^{(j)} \ge \sum_{k=1}^{m} (T^{(j)}_{k,n} - E_{m,n}).\] For ease of notation, let \[F^{(l)}_{j} \mathrel{\vcenter{:}}= (F_{\inf})^{j-1} (1-F_{\sup}), \;\mathrm{ and } \;F^{(l)}_{(j)} \mathrel{\vcenter{:}}= (F_{\inf})^{j-1} (1-F_{\sup})^2.\] Then, for every \(\epsilon > 0\), \[P^x \left(R_{mn}^{j} \le mn(F_j^{(l)} - \epsilon)\right) \le P^x \left( \sum_{k=1}^{m} T^{j}_{k,n} \le mn \left(F_j^{(l)} - \frac{\epsilon}{2} \right) \right) + P^x \left( E_{m,n} \ge n \frac{\epsilon}{2} \right).\]
We first give an upper bound for \(\displaystyle P^x \left( \sum_{k=1}^{m} T^{j}_{k,n} \le mn \left(F_j^{(l)} - \frac{\epsilon}{2} \right) \right)\). By Theorem 1, it holds that for every \(\epsilon > 0\), there exists \(N(\epsilon) \in \mathbb{N}\) such that for every \(n \ge N(\epsilon)\), \(\displaystyle \frac{E^x \left[R_n^j \right] }{n} \ge F_j^{(l)} - \frac{\epsilon}{4}\), which is equivalent with \(\displaystyle \frac{E^x \left[n - R_n^j \right] }{n} \le 1 - F_j^{(l)} + \frac{\epsilon}{4}\).
In the same manner as in the proof of Lemma 4, we can show that for every \(\epsilon > 0\), there exists \(N(\epsilon) \in \mathbb{N}\) such that for every \(n \ge N(\epsilon)\), \[\sup_{x \in \mathcal{X}} E^x \left[\exp\left(\frac{\theta(\epsilon/8)}{n} (n-R_n^j) \right) \right] \le \exp\left(\theta(\epsilon/8) \left(1 - F_j^{(l)} + \frac{3\epsilon}{8} \right) \right).\]
Since \(T^{j}_{k,n} \le n\), by the Markov property, for every \(\lambda > 0\) and \(x \in \mathcal{X}\), \[P^x \left( \sum_{k=1}^{m} T^{j}_{k,n} \le mn \left(F_j^{(l)} - \frac{\epsilon}{2} \right) \right) = P^x \left( \sum_{k=1}^{m} (n-T^{j}_{k,n}) \ge mn \left(1 - F_j^{(l)} + \frac{\epsilon}{2} \right) \right)\] \[\le \exp\left(-\lambda mn \left(1 - F_j^{(l)} + \frac{\epsilon}{2} \right) \right) E^x \left[ \prod_{k=1}^{m} \exp\left( \lambda (n-T^{j}_{k,n}) \right) \right]\] \[\le \left( \exp\left(-\lambda n \left(1 - F_j^{(l)} + \frac{\epsilon}{2} \right) \right) \sup_{x \in \mathcal{X}} E^x \left[ \exp\left(\lambda (n-R^j_n) \right) \right] \right)^m.\]
In the same manner as in the proof of Lemma 5, we can show that for every \(\epsilon > 0\), there exist \(C(\epsilon) > 0\) and \(N_3 (\epsilon) \in \mathbb{N}\) such that for every \(n \ge N_3 (\epsilon)\) and every \(m \in \mathbb{N}\), \[\sup_{x \in \mathcal{X}} P^x \left( \sum_{k=1}^{m} T^{j}_{k,n} \le mn \left(F_j^{(l)} - \frac{\epsilon}{2} \right) \right) \le \exp\left(-C(\epsilon) m \right).\]
Second, we give an upper bound for \(\displaystyle P^x \left( E_{m,n} \ge n \frac{\epsilon}{2} \right)\). Let \(n^{\prime}\) be as in 11 . As in 12 , by using \((U_1)\), we see that there exists \(N_4 (\epsilon) \in \mathbb{N}\) such that for every \(n \ge N_4 (\epsilon)\) and \(m \in \mathbb{N}\) satisfying \(mn^{\prime}/n < \epsilon/4\), \[\label{eq:Emn-upper-2} P^x \left( E_{m,n} \ge n \frac{\epsilon}{2} \right) \le \frac{2m}{\epsilon - 2m n^{\prime}/n} \sup_{x \in \mathcal{X}} P^x (n^{\prime} < T_x < \infty).\tag{15}\]
Recall 13 . Thus we obtain that for every \(\epsilon > 0\), for every \(n \ge N_3 (\epsilon) + N_4 (\epsilon)\) and every \(m \in \mathbb{N}\) satisfying \(mn^{\prime}/n < \epsilon/4\), \[P^x \left(R_{mn}^{j} \le mn(F_j^{(l)} - \epsilon)\right) \le \exp\left(-C(\epsilon) m \right) + \frac{4C_0}{\epsilon} m (\log n - \log \log n)^{-1-\delta}.\]
Let \(\eta > 0\). For \(m_k = \lfloor (\log k)^2 \rfloor\) and \(r_k = \lfloor (1+\eta)^k \rfloor\), it holds that \(m_k (r_k)^{\prime} / r_k < \epsilon/4\) for large \(k\), and, \[\exp\left(-C(\epsilon) m_k \right) + \frac{4C_0}{\epsilon} m_k (\log r_k - \log \log r_k)^{-1-\delta} = O\left(k^{-1- \frac{\delta}{2}} \right), \;k \to \infty.\]
Let \(b_k \mathrel{\vcenter{:}}= m_k r_k\). Then, \[\sum_{k=1}^{\infty} P^x \left(R_{b_k}^{j} \le b_k (F_j^{(l)} - \epsilon)\right) < +\infty.\] Hence, by the Borel-Cantelli lemma, \[\liminf_{k \to \infty} \frac{R_{b_k}^{j}}{b_k} \ge F_j^{(l)} - \epsilon, \;\mathrm{ P^x-a.s.}\] It holds that for \(b_k \le n \le b_{k+1}\), \(\displaystyle \frac{R^j_n}{n} \ge \frac{b_{k}}{b_{k+1}} \frac{R_{b_{k}}^{j}}{b_{k}}\). By this estimate and the equality \(\displaystyle \lim_{k \to \infty} \frac{b_{k}}{b_{k+1}} = \frac{1}{1+\eta}\), \[\label{eq:lacunary-lower} \liminf_{n \to \infty} \frac{R_{n}^{j}}{n} \ge \frac{F_j^{(l)} - \epsilon}{1+\eta}, \;\mathrm{ P^x-a.s.}\tag{16}\] Letting \(\eta \to 0\) and \(\epsilon \to 0\), we see that ?? holds \(P^x\)-a.s.
We now deal with \(R^{(j)}_n\). In the same manner as in the derivation of 16 , \[\liminf_{k \to \infty} \frac{R_{b_k}^{(j)}}{b_k} \ge F_{(j)}^{(l)} - \epsilon, \;\mathrm{ P^x-a.s.}\] Since \[R_n^{(j)} \ge R_{b_{k}}^{(j)} - (b_{k+1} - b_k), \;b_k \le n \le b_{k+1},\] it holds that \[\liminf_{n \to \infty} \frac{R_n^{(j)}}{n} \ge \liminf_{k \to \infty} \frac{b_{k}}{b_{k+1}} \frac{R_{b_{k}}^{(j)}}{b_{k}} - \frac{b_{k+1} - b_k}{b_k} \ge \frac{F_{(j)}^{(l)} - \epsilon}{1+\eta} - \eta, \;\mathrm{ P^x-a.s.}\] Letting \(\eta \to 0\) and \(\epsilon \to 0\), we see that ?? holds \(P^x\)-a.s.
Let \(f\) be a non-negative function on \(\mathbb{N} \cup \{0\}\) such that \(f(0) = 0\). Let \[G_n (f) \mathrel{\vcenter{:}}= \sum_{x \in \mathcal{X}} f(\ell(n,x)).\] Let \[C_{\inf}(f) \mathrel{\vcenter{:}}= \sum_{j \ge 1} f(j) (F_{\inf})^{j-1} (1-F_{\sup})^2\] and \[C_{\sup}(f) \mathrel{\vcenter{:}}= \sum_{j \ge 1} f(j) (F_{\sup})^{j-1} (1-F_{\inf})^2.\]
Since \(f(0) = 0\), we see that \[G_n (f) = \sum_{j \ge 1} f(j) R_n^{(j)}.\]
The following theorem extends [11] and the \(L^2\)-convergence part of [10].
Theorem 6. Let \(p \ge 1\). Assume that \((U_1)\) holds and \[\sum_{j \ge 1} \frac{f(j)^p}{j^{p-1}} (F_{\sup})^{j} < \infty.\] Then \[\label{eq:L2-sup-upper} \lim_{n \to \infty} E^x \left[ \left(\left( \frac{G_n (f)}{n} - C_{\sup}(f) \right)_{+}\right)^p \right] = 0\qquad{(8)}\] and \[\label{eq:L2-inf-lower} \lim_{n \to \infty} E^x \left[ \left(\left( \frac{G_n (f)}{n} - C_{\inf}(f) \right)_{-}\right)^p \right] = 0.\qquad{(9)}\]
Proof. We remark that for every \(a, b \in \mathbb{R}\), \[((a+b)_{+})^p \le (a_{+} + b_{+})^p \le 2^{p-1}((a_{+})^p + (b_{+})^p).\]
Let \(f_N (j) \mathrel{\vcenter{:}}= f(j) {\boldsymbol{1}}_{\{1,\dots, N\}}(j)\). Then, using \(C_{\sup}(f) \ge C_{\sup}(f_N)\), \[\left( \frac{G_n (f)}{n} - C_{\sup}(f) \right)_+ \le \left( \frac{G_n (f_N)}{n} - C_{\sup}(f) \right)_{+} + \frac{G_n (f) - G_n (f_N)}{n}.\]
By 4 , \[\label{eq:exp-upper-unif} \sup_x E^x \left[R_n^{(j)} \right] \le \sup_x E^x \left[R_n^{j} \right] \le (F_{\sup})^{j-1} \sup_x E^x \left[R_n \right] \le n (F_{\sup})^{j-1}.\tag{17}\]
Let \(q\) be the conjugate exponent of \(p\), i.e., \(\frac{1}{p} + \frac{1}{q} = 1\), with the convention \(q=\infty\) if \(p=1\). Using the Hölder inequality and \(n = \sum_{j \ge 1} j R_n^{(j)}\), \[\sum_{j \ge N+1} f(j) R_n^{(j)} = \sum_{j \ge N+1} \frac{f(j)}{j} (j R_n^{(j)})^{1/p} \cdot (j R_n^{(j)})^{1/q} \le n^{1/q} \left(\sum_{j \ge N+1} \frac{f(j)^p}{j^{p-1}} R_n^{(j)}\right)^{1/p}.\] Hence, \[\left( \frac{G_n (f)}{n} - \frac{G_n (f_N)}{n} \right)^p \le \sum_{j \ge N+1} \frac{f(j)^p}{j^{p-1}} \frac{R_n^{(j)}}{n}.\] Using this and 17 , \[E^x \left[ \left( \frac{G_n (f)}{n} - \frac{G_n (f_N)}{n} \right)^p \right] \le \sum_{j \ge N+1} \frac{f(j)^p}{j^{p-1}}(F_{\sup})^{j-1}.\]
Since \(\frac{G_n (f_N)}{n} \le \max_{1 \le j \le N} f(j)\), ?? and the Lebesgue convergence theorem yield that \[\lim_{n \to \infty} E^x \left[ \left( \left( \frac{G_n (f_N)}{n} - C_{\sup}(f_N) \right)_{+} \right)^p \right] = 0.\] Using this and \(C_{\sup}(f_N) \le C_{\sup}(f)\), we obtain that \[\lim_{n \to \infty} E^x \left[ \left( \left( \frac{G_n (f_N)}{n} - C_{\sup}(f) \right)_{+} \right)^p \right] = 0.\]
Hence, \[\limsup_{n \to \infty} E^x \left[ \left(\left( \frac{G_n (f)}{n} - C_{\sup}(f) \right)_{+}\right)^p \right] \le 2^{p-1} \sum_{j \ge N+1} \frac{f(j)^p}{j^{p-1}}(F_{\sup})^{j-1}.\] Letting \(N \to \infty\), we have ?? . The same argument gives ?? . ◻
Proposition 7. Assume that \((U_1)\) holds and \(F_{\inf} < 1\). Then for every \(x \in \mathcal{X}\), \[\label{eq:inf-sup-sandwich} C_{\inf}(f) \le \liminf_{n \to \infty} \frac{G_n (f)}{n} \le C_{\sup}(f), \;\mathrm{ P^x-a.s.}\qquad{(10)}\]
Proof. The lower bound follows from the non-negativity of \(f\) and Theorem 2. If \(C_{\sup}(f) = \infty\), the upper bound is obvious. Assume that \(C_{\sup}(f) < \infty\). By Theorem 6 for \(p=1\), there exists a sequence \((n_k)_k\) such that \[\lim_{k \to \infty} \left( \frac{G_{n_k} (f)}{n_k} - C_{\sup}(f) \right)_{+} = 0, \;\mathrm{ P^x-a.s.}\] This is equivalent to \[\limsup_{k \to \infty} \frac{G_{n_k} (f)}{n_k} \le C_{\sup}(f), \;\mathrm{ P^x-a.s.}\] This implies the upper bound. ◻
If \(f(j) = j\) and \(F_{\inf} = 1\), then \(G_n (f) = n\) and \(C_{\sup}(f) = 0\) so that ?? fails.
The following lower bound on the expectation plays a role similar to that of [11].
Lemma 8. Let \(x \in \mathcal{X}, n \ge 1\). Then,
(i) \(E^x \left[ R_n^{(1)} \right] \ge (1-F_{\sup})^2 n\).
(ii) If \(j \ge 2\), then for every \(\ell \in \{1,\dots, n\}\), \[E^x \left[ R_n^{(j)} \right] \ge (1-F_{\sup})^2 \ell F_{\inf}\left( \left\lfloor
\frac{n-\ell}{j-1} \right\rfloor\right)^{j-1}.\]
Proof. For \(y \in \mathcal{X}\), let \(T_y^{(1)} \mathrel{\vcenter{:}}= T_y\) and \[T_y^{(j)} \mathrel{\vcenter{:}}= \inf \left\{n > T_y^{(j-1)} \colon X_n = y \right\}, \;j \ge 2.\]
By the Markov property, we obtain that \[\label{eq:multi-ineq-Markov} P^y \left( T_y^{(j)} \le n \right) \ge P^y \left( T_y \le \left\lfloor \frac{n}{j} \right\rfloor \right)^{j}, \;j \ge 1, n \ge 1, y \in \mathcal{X}.\tag{18}\] We also see that \[E^x \left[ R_n^j \right] = \sum_{y \in \mathcal{X}} P^x \left( T_y^{(j)} \le n \right).\] By this and the Markov property, \[E^x \left[ R_n^j \right] = \sum_{y \in \mathcal{X}} \sum_{k = 1}^{n} P^x \left( T_y^{(j)} \le n, T_y = k \right) = \sum_{y \in \mathcal{X}} \sum_{k = 1}^{n} P^x \left( T_y = k \right) P^y \left( T_y^{(j-1)} \le n - k \right).\] By this and 18 , \[E^x \left[ R_n^j \right] \ge \sum_{y \in \mathcal{X}} P^x \left( T_y \le \ell \right) P^y \left( T_y^{(j-1)} \le n - \ell \right) \ge E^x \left[R_{\ell}\right] F_{\inf}\left( \left\lfloor \frac{n-\ell}{j-1} \right\rfloor\right)^{j-1}.\] Applying 3 and 8 , we obtain the assertion. ◻
We now consider the following stronger uniform tail condition \((U_2)\): \[\sup_{x} P^x (n < T_x < \infty) = O(n^{-\delta}), \;n \to \infty, \delta > 0.\] This condition was considered in [8]. The simple random walk on \(\mathbb{Z}^d, d \ge 3\), satisfies this condition.
The following corresponds to [11].
Proposition 9. Assume that \((U_2)\) holds, that \(0 < F_{\inf} \le F_{\sup} < 1\), and that \(p \ge 1\). Let \(\alpha > p-2 + \frac{p-1}{\delta}\). Let \(f(0) \mathrel{\vcenter{:}}= 0\) and \(f(j) \mathrel{\vcenter{:}}= j^{\alpha/p} F_{\inf}^{- j/p}\) for \(j \ge 1\). Then \[\lim_{n \to \infty} E^x \left[ \left( \frac{G_n (f)}{n} \right)^p \right] = \infty.\]
Proof. We first remark that \[E^x \left[ \left( \frac{G_n (f)}{n} \right)^p \right] \ge \frac{1}{n^p} \sum_{j \ge 1} f(j)^p E^x \left[\left(R_n^{(j)}\right)^p\right] \ge \frac{1}{n^p} \sum_{j \ge 2} f(j)^p E^x \left[R_n^{(j)}\right].\] By Lemma 8, \[\frac{1}{n^p} \sum_{j \ge 2} f(j)^p E^x \left[R_n^{(j)}\right] \ge \frac{(1-F_{\sup})^2}{n^p} \left\lfloor \frac{n}{2} \right\rfloor \sum_{j \ge 2} j^{\alpha} F_{\inf}^{-j} F_{\inf}\left( \left\lfloor \frac{n}{2(j-1)} \right\rfloor\right)^{j-1}.\] By \((U_2)\), there exists \(C > 0\) such that for every \(n \ge 1\) and every \(j \ge 2\), \[F_{\inf}\left( \left\lfloor \frac{n}{2(j-1)} \right\rfloor\right) \ge \left(1 - C \left(\frac{j-1}{n}\right)^{\delta}\right)_{+} F_{\inf}.\] Hence it suffices to show that \[\label{eq:lim-infty-sum-j} \lim_{n \to \infty} \frac{1}{n^{p-1}} \sum_{j \ge 2} j^{\alpha} \left(\left(1 - C \left(\frac{j-1}{n}\right)^{\delta}\right)_{+}\right)^{j-1} = \infty.\tag{19}\]
Let \(a > 0\) such that \(C a^{\delta + 1} < 1/2\). If \(j - 1 \le \lfloor a n^{\delta/(1+\delta)} \rfloor\), then \[\left(1 - C \left(\frac{j-1}{n}\right)^{\delta}\right)^{j-1} \ge 1 - C \frac{(j-1)^{1+\delta}}{n^{\delta}} \ge \frac{1}{2}.\] Hence \[\sum_{j \ge 2} j^{\alpha} \left(\left(1 - C \left(\frac{j-1}{n}\right)^{\delta}\right)_{+}\right)^{j-1} \ge \frac{1}{2} \sum_{j=2}^{\lfloor a n^{\delta/(1+\delta)} \rfloor + 1} j^{\alpha}\] and the right-hand side grows on the scale of \(n^{(\alpha + 1) \delta / (\delta + 1)}\). By the assumption, \((\alpha + 1) \delta > (p-1) (\delta + 1)\) and we obtain 19 . ◻
Remark 10. Suppose that the assumptions of Proposition 9 hold. If, additionally, \(p > 1\) and \(F_{\sup} < F_{\inf}^{1/p}\), then \(C_{\sup}(f) < \infty\) and \[\lim_{n \to \infty} E^x \left[ \left( \frac{G_n (f)}{n} - C_{\sup}(f) \right)_{+} \right] = \lim_{n \to \infty} E^x \left[ \left( \frac{G_n (f)}{n} - C_{\inf}(f) \right)_{-} \right] = 0.\] If \(F_{\inf} = F_{\sup} < 1\) and \(p >1\), then \(F_{\sup} < F_{\inf}^{1/p}\).
In general, the strict inequality \(F_{\inf} < F_{\sup}\) can occur. See [7]. By the same argument as in the proof of [7], one can show that \[(F_{\inf})^{j-1} (1-F_{\sup}) = \liminf_{n \to \infty} \frac{\inf_{x \in \mathcal{X}} E^{x} \left[R_n^j \right]}{n}\] \[< \limsup_{n \to \infty} \frac{\sup_{x \in \mathcal{X}} E^{x} \left[R_n^j \right]}{n} = (F_{\sup})^{j-1} (1-F_{\inf})\] for each \(j\).
We give a sufficient condition for \((U_1)\). Let \(p_n (x,y) \mathrel{\vcenter{:}}= P^x (X_n = y)\). Then we have the trivial estimate \(P^x (n < T_x < \infty) \le \sum_{k=n+1}^{\infty} p_k (x,x)\).
Specifically, if there exists a constant \(C_0\) such that \[\label{eq:Nash-type} p_n (x,x) \le \frac{C_0}{n (\log (n+1))^{2+\delta}}\tag{20}\] holds for every \(x \in \mathcal{X}, n \ge 1\), then \((U_1)\) holds.
Proposition 11. Assume that \((X_n)_n\) is the simple random walk on an infinite connected simple graph with bounded degrees. Then the Nash-type inequality 20 is stable under rough isometries between graphs.
Proof. We apply results of Tessera [14]. Let \(\gamma(t) \mathrel{\vcenter{:}}= C_0 t^{-1} (\log (t+1))^{-2-\delta}\). Then there exists an increasing positive function \(\varphi\) such that \(t = \int_0^{1/\gamma(t)} \varphi(v)^2 \frac{dv}{v}\) for every \(t \ge 1\). Moreover, \(\varphi(v) \sim \frac{\sqrt{C_0 v}}{\log(v+1)^{1+\delta/2}}\) as \(v \to \infty\).
Let \(\mathcal{X}_1\) and \(\mathcal{X}_2\) be two infinite connected simple graphs with bounded degrees. Assume that 20 holds for the simple random walk on \(\mathcal{X}_1\). By [14], the Sobolev inequality associated with \(\varphi\) holds for \(\mathcal{X}_1\). By [14], the Sobolev inequality is stable under rough isometries, and hence, the Sobolev inequality associated with \(\varphi\) also holds for \(\mathcal{X}_2\). By [14], 20 also holds for the simple random walk on \(\mathcal{X}_2\). ◻
The Laakso-type graph constructed in Murugan [15] is an infinite connected simple graph with bounded degrees such that there exist two constants \(C_1\) and \(C_2\) such that the inequalities \[\label{eq:Nash-type-both} \frac{C_1}{n (\log (n+1))^{2+\delta}} \le p_n (x,x) + p_{n+1}(x,x) \le \frac{C_2}{n (\log (n+1))^{2+\delta}}\tag{21}\] hold for every \(x \in \mathcal{X}, n \ge 1\).
Every infinite, connected, locally finite, vertex-transitive graph with polynomial volume growth does not satisfy 21 , because every such graph is roughly isometric to a Cayley graph of a virtually nilpotent group by Trofimov [16] and the claim follows from Hebisch and Saloff-Coste [17].
There are examples of random walks on \(\mathbb{Z}\) with long-range jumps satisfying 21 . By Murugan and Saloff-Coste [18], if there exist two constants \(C_3\) and \(C_4\) such that the inequalities \[C_3
\frac{(\log(e+|x-y|))^{2+\delta}}{(1+|x-y|)^2} \le p(x,y) = p(y,x) \le C_4 \frac{(\log(e+|x-y|))^{2+\delta}}{(1+|x-y|)^2}\] hold for every \(x, y \in \mathcal{X}\), then 21
holds.
The author is supported by JSPS KAKENHI JP22K13928.