Preferential Attachment When Stable

2018/05/27 by Janson, Svante, Sen, Subhabrata, Spencer, Joel
#60C05 #60F10 #60F17 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1805.10653

Abstract

We study an urn process with two urns, initialized with a ball each. Balls are added sequentially, the urn being chosen independently with probability proportional to the α^th power (α>1) of the existing number of balls. We study the (rare) event that the urn compositions are balanced after the addition of 2n-2 new balls. We derive precise asymptotics of the probability of this event by embedding the process in continuous time. Quite surprisingly, a fine control on this probability may be leveraged to derive a lower tail Large Deviation Principle (LDP) for L = ∑_i=1ⁿ (S_i²)/(i²), where \S_n : n ≥ 0\ is a simple symmetric random walk started at zero. We provide an alternate proof of the LDP via coupling to Brownian motion, and subsequent derivation of the LDP for a continuous time analogue of L. Finally, we turn our attention back to the urn process conditioned to be balanced, and provide a functional limit law describing the trajectory of the urn process.

Related

• Urn models with two types of strategies
• Large deviations for Generalized Polya Urns with arbitrary urn function
• Functional limit theorems for Pólya urns with growing initial compositions
• Analysis of Large Urn Models with Local Mean-Field Interactions
• Functional central limit theorems for occupancies and missing mass\n process in infinite urn models