Preferential attachment when stable

Svante Janson, Subhabrata Sen, Joel Spencer

Research output: Contribution to journalArticle

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 new balls. We derive precise asymptotics of the probability of this event by embedding the process in continuous time. Quite surprisingly, fine control of this probability may be leveraged to derive a lower-tail large deviation principle (LDP) for , where is a simple symmetric random walk started at zero. We provide an alternative proof of the LDP via coupling to Brownian motion, and subsequent derivation of the LDP for a continuous-time analog 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.

Original languageEnglish (US)
Pages (from-to)1067-1108
Number of pages42
JournalAdvances in Applied Probability
Volume51
Issue number4
DOIs
StatePublished - Dec 1 2019

    Fingerprint

Keywords

  • Urn model
  • large deviations

ASJC Scopus subject areas

  • Statistics and Probability
  • Applied Mathematics

Cite this