Local limit theorems for sequences of simple random walks on graphs

DOI10.1007/S11118-008-9101-9MaRDI QIDQ956607zbMATH OpenOpenAlexFDO

Authors David A. Croydon, Ben M. Hambly

Publication date 25 November 2008

Published in Potential Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.6194

zbMATH Keywords

generalized Sierpiński carpet local limit therem parabolic Harnack inequality random walk on graphs

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Transition functions, generators and resolvents (60J35)

Abstract: In this article, local limit theorems for sequences of simple random walks on graphs are established. The results formulated are motivated by a variety of random graph models, and explanations are provided as to how they apply to supercritical percolation clusters, graph trees converging to the continuum random tree and the homogenisation problem for nested fractals. A subsequential local limit theorem for the simple random walks on generalised Sierpinski carpet graphs is also presented.

Review text

The following situation is considered. First, a metric space \((E,d)\), a subspace \(F\subset E\), such that its intersection with every closure of a \(B_{E}(x,r)\) (where \(B_{E}(x,r)\) are the open spheres) is compact, an element \(\varrho\in F\), a Radon measure \(\nu\) concentrated on \(F\) and a family \(q_{t}\), \(t>0\) of probability densities on \(F\), continuous in \((t,\cdot )\). Then, for every connected locally finite weighted graph \(G=(V(G),E(G),\mu^{G})\) (i.e. \(\mu^{G}: V(G)^{2}\rightarrow (0,\infty )\), \(\mu_{xy}^{G}= 0\) if and only if \(\{x,y\}\notin E(G)\)), \(d_{G}\) denotes the number of edges in \(E(G)\) on the shortest path from \(x\) to \(y\). Let \(\mu_{x}^{G}=\sum_{y}\mu_{xy}^{G}\) and \(\nu^{G}(A)=\sum_{x\in A}\mu_{x}^{G}\), a Markov chain \((X_{m}^{G})_{m\geq 0}\), \(P_{x}^{G}\) on \(G\) with transition probabilities \(P^{G}(x,y)=\mu_{xy}^{G}/\mu_{x}^{G}\); \(\nu^{G}\) is an invariant measure for it. Let \(p_{m}^{G}(x,y)\) be the corresponding \(m\)-step transition probability and \(q_{m}^{G}(x,y)=(p_{m}^{G}(x,y)+p_{m+1}^{G}(x,y))/2\). Then an imbedding (not isometric) of a sequence \(G^{n}\), \(\varrho\in V(G^{n})\), of such graphs into \(E\) is considered. Some ``assumptions are stated, signifying that the \(G^{n}\) and the corresponding elements approximate in a certain sense \(F\) and the elements denoted with the same letter on \(F\). The first, omitting \(G\) in the indexes \(G^{n}\), has four parts. One is \(\lim_{n}P_{\varrho }^{n}(X_{[\gamma (n)t]}^{n}\in B_{E}(x,r))=\int_{_{B_{F}(x,r)}}q_{t}d\nu\) uniformly on compacts in \(t\in (0,\infty )\), another is \(\lim_{n}\beta (n)^{-1}\nu^{n}(B_{E}(x,r))=\nu (B_{E}(x,r))\), both for \(\beta (n)\), \(\gamma (n)\rightarrow\infty\), another is \(\lim_{n}\sup_{x\in B_{F}(\varrho,r)}d(x,V(G^{n}))=0\) and \(\alpha^{~}(n)+c_{2}\alpha (n)d(x,y)\geq d_{n}(x,y)\geq c_{1}\alpha (n)d(x,y)\) for \(\alpha (n)\rightarrow\infty\), \(\alpha^{~}(n)/\alpha (n) \rightarrow 0\). Assumption 2 is \(\lim_{\delta\rightarrow 0}\limsup_{n}\) of \(\sup \beta (n)|q_{[\gamma (n)t]}^{n}(x)-q_{[\gamma (n)t]}^{n}(y)|\), over \(t\) in every compact \(I\subset (0,\infty )\), \(x,y\in B_{n}(\varrho ,\alpha (n)r)\) and \(d_{n}(x,y)\leq\alpha (n)\delta\), tends to \(0\). Under these two assumptions, the authors prove ``the local limit theorem: \(\lim_{n}\sup_{x\in B_{F}(\varrho ,r),t\in I} |\beta (n)q_{[\gamma (n)t]}^{n}(g_{n}(x))-q_{t}(x)|=0\); \(g_{n}(x)\in V(G^{n})\) minimizing \(d(x,V(G^{n}))\). When another assumption also holds, requiring the existence of ``midpoints in \(F\) and conditions on the \(q\), \(q^{n}\), the author prove a stronger result, with \(\sup_{x\in F,t\geq T}\) instead of \(\sup_{\cdot\cdot }\). Then assumptions 4 and 5 are stated and shown that each, together with a part of assumption 1, implies assumption 2. From assumption 4: for some \(k\geq 2\), for every \(G=G^{n}\), \(x\in V(G)\) there exists \(s_{G}(x)\) such that, for \(R\geq s_{G}(x)\), a ``parabolic Harnack inequality holds. It means that a constant \(C\) exists such that, if \(u(n,z)\geq 0\) is defined for every integer \(n\in [0,R^{k}]\) and \(z\in B_{G}(x,R)\), if \(u(n+1,z)-u(n,z)=\sum_{y\in V(G)}P_{G}(z,y)(u(n,y)-u(n,z))\) (denoted \({\mathcal L}_{G}(u(n,\cdot ))(z)\)) and if \(v(n,z)= u(n+1,z)+u(n,z)\) then \(\sup v\) on \([T/4,T/2]\times B_{G}(x,R/2)\) is \(\leq cinfv\) on \([3T/4,T]\times B_{G}(x,R/2)\). Assumption 5 contains \(R_{G}(x,y)\leq cd_{G}(x,y)^{k}\) with some \(k\in (0,\infty )\), where \(R_{G}(x,y)= \sup_{f:V(G)\rightarrow {\mathbb R},0<{\mathcal E}_{G}(f)<\infty } (|f(x)-f(y)|^{2}{\mathcal E}_{G}(f)^{-1})\), \({\mathcal E}_{G}(f)= -\sum_{x\in V(G)}{\mathcal L}_{G}(f)(x)f(x)\nu^{G}(x)\). Generalizations to the case of \(\nu\)-symmetric Markov transition densities \(p_{t}(x,y)\) (\(q_{t}(y)\) appearing as \(p_{t}(\varrho ,y)\)) and in the case when the \((\mu (x,y))_{_{x,y\in\cup_{n}E(G^n)}}\) is random (under some assumptions on its distribution) are proved. Following the last paragraph (18 p.) requires information from several of the quoted papers; its contents increases significantly the interest of the previous results. It contains examples: lattice graphs, graph trees converging to the continuum random tree, local homogenization for nested fractals, local homogenization for tree-like Vicsek graphs, Sierpiński carpet graph.

Recommendations

Cites work

Cited in

(32)

This page was built for publication: Local limit theorems for sequences of simple random walks on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q956607)