Preferential attachment when stable

DOI10.1017/APR.2019.42MaRDI QIDQ5203976zbMATH OpenOpenAlexWikidataFDO

Authors Svante Janson, Subhabrata Sen, Joel Spencer

Publication date 9 December 2019

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.10653

zbMATH Keywords

large deviationsurn model

Mathematics Subject Classification ID

Combinatorial probability (60C05) Large deviations (60F10) Functional limit theorems; invariance principles (60F17)

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 $alph{a}^{th}$ power $(alpha>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=su{m}_{i=1}^{n}frac{S}_i^2{i}^2$, where $S_n:ngeq0$ 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.

Recommendations

• Generalizations of Polya's urn problem
• Limit distributions for large Pólya urns
• Fully analyzing an algebraic Pólya urn model
• Large deviations for generalized Polya urns with arbitrary urn function
• Some exactly solvable models of urn process theory

Cites work

• An approximation of partial sums of independent RV'-s, and the sample DF. I
• Conditional distributions and tightness
• Connectivity Transitions in Networks with Super-Linear Preferential Attachment
• Decomposition of mean-field Gibbs distributions into product measures
• Exponential random graphs behave like mixtures of stochastic block models
• Gaussian Hilbert Spaces
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 3474640 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 1857820 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• scientific article; zbMATH DE number 3073200 (Why is no real title available?)
• Nonlinear large deviations
• On the variational problem for upper tails in sparse random graphs
• Orthogonal decompositions and functional limit theorems for random graph statistics
• Proofs of the martingale FCLT
• Random walk: A modern introduction
• Reinforced random walk
• Stopping times and tightness
• Upper tails and independence polynomials in random graphs

Cited in

(1)

• Automata, Languages and Programming

This page was built for publication: Preferential attachment when stable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5203976)