Cutoff for Simple Random Walk on Preferential Attachment Graphs
math.PR
Submitted: 2026-10-31
Updated: 2026-10-31
License: http://creativecommons.org/licenses/by/4.0/
The gist: We consider simple random walk on the sequential affine preferential attachment graphs with fixed parameters m at least2 and δ at least0.
Terminology
Abstract
We consider simple random walk on the sequential affine preferential attachment graphs with fixed parameters m at least2 and δ at least0. We prove the walk has total-variation cutoff, and for every fixed epsilon in(0,1), [t mix(n)(epsilon) = n over νd +O P! (sqrt n),] where ν>0 is the walk speed and d>0 is the entropy per level of harmonic measure on the Pólya--point tree, the local weak limit of the graph. Thus cutoff occurs at the entropic time. Entropic cutoff was previously established for a range of random graph models including configuration models under mild degree assumptions and on Erdős--Rényi random graphs for typical starting points. We extend the harmonic-measure approach to preferential attachment, accounting for its age-dependent structure and hubs of polynomial degree. The local weak limit, the Pólya--point tree, provides a more tractable setting for analyzing the walk. The proof combines regeneration estimates on the local limit tree, a quantitative graph--tree coupling on the mixing-time scale, and control of hub excursions. We show that shortly before the cutoff time its distribution is close in total variation distance to a measure with small L infinity distance from stationarity. When m at least2, the spectral gap is bounded away from zero with high probability which completes the upper-bound coupling argument.
Sources
- Percolation on preferential attachment models
- Logarithmic typical distances in preferential attachment models
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves