Asymptotic estimates for multiple point ranges of transient random walks on graphs

Kazuki Okamura · 2026

Read Asymptotic estimates for multiple point ranges of transient random walks on graphs by Kazuki Okamura (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00648.txt.

Introduction

Okamura studies random walks on graphs in this 2026 maths paper. A walk moves step by step along the edges of a graph. He asks how many sites the walk visits at least a set number of times, and how many it visits just that many times.

Past work got firm bounds for walks on groups, where symmetry helps. Okamura swaps that symmetry for one plain rule: a uniform bound on the tail of the first return time. Under this rule he proves upper and lower bounds that grow in a straight line. With a stronger rule, the same bounds hold with near certainty. For smooth transient cases the bounds meet, which gives a strong law of large numbers. He then uses the bounds to study sums built from local times.

Catalog record

CREATORKazuki Okamura
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.00648

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Asymptotic estimates for multiple point ranges of transient random walks on graphs Kazuki Okamura Abstract . 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. 1. Introduction and main results 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 \displaystyle j\geq 1 , we consider the number \displaystyle R_{n}^{j} of sites visited at least \displaystyle j times by time \displaystyle n , and the number \displaystyle R_{n}^{(j)} of sites visited exactly \displaystyle j times by time \displaystyle n . Here \displaystyle 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 \displaystyle R_{n}^{j} and \displaystyle R_{n}^{(j)} has been investigated by several authors. For transient random walks, Erdős and Taylor [ 5 ] showed the strong law of large numbers for the simple random walk on the integer lattice \displaystyle\mathbb{Z}^{d},d\geq 3 . Pitt [ 14 ] showed the strong law of large numbers for a transient random walk on a countable Abelian group. Derriennic [ 4 ] 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 [ 6 ] and Hamana [ 7 , 8 ] . 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 \displaystyle R_{n}^{j} and \displaystyle 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 [ 13 , Corollary 2.3] and by Kumagai and Nakamura [ 10 , Proposition 5.7] . 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 [ 2 ] investigated moments of the local times of transient random walks on \displaystyle\mathbb{Z}^{d} . Asymont and Korshunov [ 1 ] considered a more general class of functions of the local times. Recently, Chang, Chen, Meng and Peng [ 3 ] 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 \displaystyle f with \displaystyle f(0)=0 , let \displaystyle G_{n}(f) be the sum obtained by applying \displaystyle f to the local time of each site visited up to time \displaystyle n . Combining a decomposition by local time levels with our estimates for exact multiple point ranges \displaystyle R_{n}^{(j)} , we obtain asymptotic results for \displaystyle G_{n}(f) under suitable summability conditions on \displaystyle f . The local time results are graph analogues of known results in the lattice and group settings and include an extension of [ 3 , Theorem 2] and of the \displaystyle L^{2} -convergence part of [ 1 , Theorem 1] . 1.1. Framework and main results Let \displaystyle\mathcal{X} be a countable set. Let \displaystyle(X_{n})_{n=0}^{\infty} be an irreducible Markov chain on \displaystyle\mathcal{X} . If \displaystyle P(X_{0}=x)=1 , then we denote the law of the Markov chain \displaystyle(X_{n})_{n} by \displaystyle P^{x} . We denote the expectation with respect to \displaystyle P^{x} by \displaystyle E^{x} . Let \displaystyle\ell(n,x)\coloneqq|\{i\in\{1,\dots,n\}:X_{i}=x\}| . For \displaystyle j\geq 1 and \displaystyle n\geq 1 , let R_{n}^{j}\coloneqq\left|\left\{x\in\mathcal{X}:\ell(n,x)\geq j\right\}\right| and R_{n}^{(j)}\coloneqq\left|\left\{x\in\mathcal{X}:\ell(n,x)=j\right\}\right|. We remark that \displaystyle R_{n}\coloneqq R_{n}^{1} is the range of the random walk and \displaystyle R_{n}^{j}=R_{n}^{(j)}+R_{n}^{j+1} . For \displaystyle x\in\mathcal{X} , let \displaystyle T_{x}\coloneqq\inf\{n\geq 1:X_{n}=x\} . Let F_{\inf}\coloneqq\inf_{x\in\mathcal{X}}P^{x}(T_{x}<\infty),\ \textup{ and }\ F_{\sup}\coloneqq\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 \displaystyle(U_{0}) holds if \lim_{n\to\infty}\sup_{x\in\mathcal{X}}P_{x}(n<T_{x}<\infty)=0, and that \displaystyle(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.1 . If \displaystyle(U_{0}) holds, then, for every \displaystyle j\geq 1 , \displaystyle\displaystyle(F_{\inf})^{j-1}(1-F_{\sup}) \displaystyle\displaystyle\leq\liminf_{n\to\infty}\frac{\inf_{x\in\mathcal{X}}E^{x}\left[R_{n}^{j}\right]}{n} \displaystyle\displaystyle\leq\limsup_{n\to\infty}\frac{\sup_{x\in\mathcal{X}}E^{x}\left[R_{n}^{j}\right]}{n}\leq(F_{\sup})^{j-1}(1-F_{\inf}) and \displaystyle\displaystyle(F_{\inf})^{j-1}(1-F_{\sup})^{2} \displaystyle\displaystyle\leq\liminf_{n\to\infty}\frac{\inf_{x\in\mathcal{X}}E^{x}\left[R_{n}^{(j)}\right]}{n} \displaystyle\displaystyle\leq\limsup_{n\to\infty}\frac{\sup_{x\in\mathcal{X}}E^{x}\left[R_{n}^{(j)}\right]}{n}\leq(F_{\sup})^{j-1}(1-F_{\inf})^{2}. If the Markov chain \displaystyle(X_{n})_{n} is the simple random walk on a vertex-transitive graph or the random walk on a countable group, then \displaystyle F_{\sup}=F_{\inf} . If the Markov chain \displaystyle(X_{n}) is recurrent, then \displaystyle F_{\sup}=F_{\inf}=1 . \displaystyle(U_{0}) is identical with the condition in [ 13 , Lemma 2.1] . Theorem 1.2 . If \displaystyle(U_{1}) holds, then, for every \displaystyle j\geq 1 and every \displaystyle x\in\mathcal{X} , the following statements hold \displaystyle P^{x} -a.s.: \limsup_{n\to\infty}\frac{R_{n}^{j}}{n}\leq(F_{\sup})^{j-1}(1-F_{\inf}).\ (1.1) \limsup_{n\to\infty}\frac{R_{n}^{(j)}}{n}\leq(F_{\sup})^{j-1}(1-F_{\inf})^{2}. (1.2) \liminf_{n\to\infty}\frac{R_{n}^{j}}{n}\geq(F_{\inf})^{j-1}(1-F_{\sup}).\ (1.3) \liminf_{n\to\infty}\frac{R_{n}^{(j)}}{n}\geq(F_{\inf})^{j-1}(1-F_{\sup})^{2}. (1.4) In Section 4 , we give a sufficient condition for \displaystyle(U_{1}) in terms of heat kernel. To our knowledge, the Nash-type on-diagonal heat kernel upper bounds needed to verify \displaystyle(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 [ 15 ] for example. We remark that there exist infinite vertex-transitive graphs which are not Cayley graphs of groups, as shown by Woess [ 18 ] . 2. Proofs In this section, we prove Theorems 1.1 and 1.2 . As an outline, we follow [ 14 ] ; in particular, we use induction on \displaystyle j

Read the complete text