Random Walk on age-preferential random growth processes
Abstract
This paper studies a class of \textbf{exponentially age-preferential random growth graphs} G(m,β): at each time n a new vertex vn is added, and m edges are drawn to existing vertices independently, with the probability that a target vk is chosen proportional to eβk (β>0), so that the graph's growth strongly favors ``young'' vertices. We systematically investigate two fundamental probabilistic problems of this model and supply the proof details: (1)~\textbf{Recurrence}: when β>0, the simple random walk on G is recurrent with probability $1$ (Theorem~\ref{thm:rec}); (2)~\textbf{Infinite collisions}: for every β>0, two independent simple random walks on G meet infinitely often with probability $1$ (Theorem~\ref{thm:icp}). The core of the proof is the following: by the Borel--Cantelli lemma combined with the \textbf{memoryless property} of exponential weights, G is almost surely ``sausage-like'' --- there exist infinitely many bottlenecks consisting of exactly m parallel edges; the cascade of bottlenecks makes the effective resistance diverge, yielding recurrence; the renewal process {Tk} constructed at the bottleneck times has i.i.d.\ stationary increments with finite moments of every order for the first-passage times, and combined with a moderate-deviation estimate we verify Peres' Green-function criterion for infinite collisions.
Related
- Cutoff for Simple Random Walk on Preferential Attachment Graphs
- An explicit lower bound for the growth exponent of three-dimensional loop-erased random walk
- Exponential functionals of two random walks and stationary measures of discrete growth processes
- On the critical branching random walk I: branching capacity and visiting probability
- Characterization and scaling limit of three-dimensional loop-erased random walk and random-walk loop-catchers
BibTeX
@misc{tang2026random,
title = {{Random Walk on age-preferential random growth processes}},
author = {Jia-shan Tang and Feng Wang and Xian-Yuan Wu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02329},
eprint = {2611.02329},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02329},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Random Walk on age-preferential random growth processes
AU - Jia-shan Tang
AU - Feng Wang
AU - Xian-Yuan Wu
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02329
UR - https://arxiv.org/abs/2611.02329
AB - This paper studies a class of \textbf{exponentially age-preferential random growth graphs} G(m,β): at each time n a new vertex v_n is added, and m edges are drawn to existing vertices independently, with the probability that a target v_k is chosen proportional to e^βk (β>0), so that the graph's growth strongly favors ``young'' vertices. We systematically investigate two fundamental probabilistic problems of this model and supply the proof details: (1)~\textbf{Recurrence}: when β>0, the simple random walk on G is recurrent with probability $1$ (Theorem~\ref{thm:rec}); (2)~\textbf{Infinite collisions}: for every β>0, two independent simple random walks on G meet infinitely often with probability $1$ (Theorem~\ref{thm:icp}). The core of the proof is the following: by the Borel--Cantelli lemma combined with the \textbf{memoryless property} of exponential weights, G is almost surely ``sausage-like'' --- there exist infinitely many bottlenecks consisting of exactly m parallel edges; the cascade of bottlenecks makes the effective resistance diverge, yielding recurrence; the renewal process {T_k} constructed at the bottleneck times has i.i.d.\ stationary increments with finite moments of every order for the first-passage times, and combined with a moderate-deviation estimate we verify Peres' Green-function criterion for infinite collisions.
ER -