Universal Exponent-Two Degree Laws in Range-Renewal Networks

Source abstract

Let an infinite sequence of independent and identically distributed random variables over a countable alphabet generate a graph by joining consecutive symbols and suppressing repeated edges. We determine the exact tail and local asymptotics of the limiting degree distributions of this range-renewal graph. If the ordered sampling probabilities satisfy $π_k\in\mathrm{RV}_{-1/γ}$ with $0<γ<1$, then the directed and undirected degree tails are asymptotic to $π_k^γ$ and $2^γπ_k^γ$, respectively, while the corresponding local masses are asymptotic to $π_k^γ/k$ and $2^γπ_k^γ/k$. Consequently, both limiting laws are regularly varying with index $-2$, independent of $γ$; forgetting edge orientation affects only the leading amplitude. The proof combines infinite-occupancy estimates for discovery times and residual unseen mass with a conditional geometric representation of inter-discovery gaps. Uniform integrability yields the tail asymptotics, whereas a geometric-smoothing argument obtains the local masses without differentiating a regularly varying tail. We also prove that deleting self-loops leaves the limiting laws unchanged. Finite-sample simulations for normalized Zipf frequencies illustrate the asymptotic result.