Continuum tree limit for the range of random walks on regular trees

DOI10.1214/009117905000000468MaRDI QIDQ2368839zbMATH OpenOpenAlexFDO

Authors Thomas S. A. Duquesne

Publication date 28 April 2006

Published in The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

continuum random treecontour processexploration processheight processlimit theorem

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Functional limit theorems; invariance principles (60F17) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: Let $b$ be an integer greater than 1 and let $W^{ee}=(W_n^{ee};ngeq0)$ be a random walk on the $b$-ary rooted tree $U_b$, starting at the root, going up (resp. down) with probability $1/2+epsilon$ (resp. $1/2-epsilon$), $epsilonin(0,1/2)$, and choosing direction $iin1,\mathrm{...},b$ when going up with probability $a_i$. Here $aa=(a_1,\mathrm{...},a_b)$ stands for some non-degenerated fixed set of weights. We consider the range $W_n^{ee};ngeq0$ that is a subtree of $U_b$. It corresponds to a unique random rooted ordered tree that we denote by $a{u}_{epsilon}$. We rescale the edges of $a{u}_{epsilon}$ by a factor $ee$ and we let $ee$ go to 0: we prove that correlations due to frequent backtracking of the random walk only give rise to a deterministic phenomenon taken into account by a positive factor $gamma(aa)$. More precisely, we prove that $a{u}_{epsilon}$ converges to a continuum random tree encoded by two independent Brownian motions with drift conditioned to stay positive and scaled in time by $gamma(aa)$. We actually state the result in the more general case of a random walk on a tree with an infinite number of branches at each node ($b=infty$) and for a general set of weights $aa=(a_n,ngeq0)$.

Review text

The author studies, near the criticality, a transient random walk \(\{W_{n}^{\varepsilon}:n\geq 0\}\) on a \(b\)-ary rooted tree (\(b\geq 1\) integer) in a ``diffusive regime. The range of the random walk is a subtree which corresponds to a unique random ordered tree \(\tau_{\varepsilon}\). The main result of the paper asserts that \(\tau_{\varepsilon}\) converges in distribution, as \(\varepsilon\to 0\), to some continuum random tree encoded by two independent Brownian motions with drift conditioned to stay positive and scaled in time. Actually the result is stated in the case of an \(\infty\)-ary tree \(U\). The technical point of the paper concerns the identification of the limiting tree by studying precisely the ``shrinking effect via explicit computations for a \(U\)-indexed Markov process.

Recommendations

• Convergence of simple random walks on random discrete trees to Brownian motion on the continuum random tree
• Scaling limit of the subdiffusive random walk on a Galton-Watson tree in random environment
• The range of tree-indexed random walk
• The range of tree-indexed random walk in low dimensions
• The continuum random tree. III

Cites work

• Arbres et processus de Galton-Watson. (Trees and Galton-Watson processes)
• Asymptotic fringe distributions for general families of random trees
• Biased random walks on Galton-Watson trees
• Branching processes in Lévy processes: The exploration process
• Conceptual proofs of L L criteria for mean behavior of branching processes
• Ergodic theory on Galton—Watson trees: speed of random walk and dimension of harmonic measure
• Functional central limit theorem for a random walk in a random environment
• scientific article; zbMATH DE number 3158353 (Why is no real title available?)
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 1859371 (Why is no real title available?)
• scientific article; zbMATH DE number 975608 (Why is no real title available?)
• Large deviations for random walks on Galton-Watson trees: Averaging and uncertainty
• Probabilistic and fractal aspects of Lévy trees
• Random walk on periodic trees
• Random Walks on Infinite Graphs and Groups
• Subdiffusive behavior of random walk on a random cluster
• The continuum random tree. III
• The range of random walk on trees and related trapping problem
• The rate of escape for anisotropic random walks in a tree
• Tree-valued Markov chains derived from Galton-Watson processes

Cited in

(8)

• The range of random walk on trees and related trapping problem
• Scaling limit of the invasion percolation cluster on a regular tree
• Scaling limits of tree-valued branching random walks
• Limit theorems for reinforced random walks on certain trees
• Limsup deviations on trees
• The continuum random tree is the scaling limit of unlabeled unrooted trees
• Markov chains on trees: almost lower and upper directed cases
• Convergence of simple random walks on random discrete trees to Brownian motion on the continuum random tree

This page was built for publication: Continuum tree limit for the range of random walks on regular trees

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