Preferential attachment when stable

DOI10.1017/APR.2019.42zbMATH Open1427.60049arXiv1805.10653OpenAlexW3105633382WikidataQ126798495 ScholiaQ126798495MaRDI QIDQ5203976FDOQ5203976

Authors: Svante Janson, Subhabrata Sen, Joel Spencer 

Publication date: 9 December 2019

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

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.

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

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

zbMATH Keywords

large deviationsurn model

Mathematics Subject Classification ID

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

Cites Work

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

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)