Universal Exponent-Two Degree Laws in Range-Renewal Networks
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∈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.
Related
- Once-reinforced random walk on ℤd has range exponent at least d/(d+1)
- A degree-linear upper bound for the Pólya exponent of forms with fixed arity
- Redundancy and Renewal of Servers in Opened Queuing Networks
- Forecasting of infectious disease epidemics in sexual networks using attenuated renewal processes
- Universal Dimension Formula for Planar Cr Splines at Degree 3r+1
BibTeX
@misc{xie2026universal,
title = {{Universal Exponent-Two Degree Laws in Range-Renewal Networks}},
author = {Jiansheng Xie and Yechi Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05290},
eprint = {2609.05290},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05290},
}
RIS
TY - UNPB
TI - Universal Exponent-Two Degree Laws in Range-Renewal Networks
AU - Jiansheng Xie
AU - Yechi Zhou
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05290
UR - https://arxiv.org/abs/2609.05290
AB - 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∈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.
ER -