Random Walk on age-preferential random growth processes

This paper studies a class of exponentially age-preferential random growth graphs $G(m,β)$: at each time n a new vertex vₙ is added, and m edges are drawn to existing vertices independently, with the probability that a target vₖ 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)~Recurrence: when $β>0$, the simple random walk on G is recurrent with probability $1$ (Theorem~{thm:rec}); (2)~Infinite collisions: for every $β>0$, two independent simple random walks on G meet infinitely often with probability $1$ (Theorem~{thm:icp}). The core of the proof is the following: by the Borel--Cantelli lemma combined with the 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 ₖ\ 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.