On martingale tail sums in affine two-color urn models with multiple drawings

DOI10.1017/JPR.2016.89zbMATH Open1397.60066arXiv1511.01618OpenAlexW2963872945MaRDI QIDQ4684841FDOQ4684841

Markus Kuba, Henning Sulzbach

Publication date: 26 September 2018

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

Abstract: In two recent works, Kuba and Mahmoud (arXiv:1503.090691 and arXiv:1509.09053) introduced the family of two-color affine balanced Polya urn schemes with multiple drawings. We show that, in large-index urns (urn index between $1/2$ and $1$) and triangular urns, the martingale tail sum for the number of balls of a given color admits both a Gaussian central limit theorem as well as a law of the iterated logarithm. The laws of the iterated logarithm are new even in the standard model when only one ball is drawn from the urn in each step (except for the classical Polya urn model). Finally, we prove that the martingale limits exhibit densities (bounded under suitable assumptions) and exponentially decaying tails. Applications are given in the context of node degrees in random linear recursive trees and random circuits.

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

zbMATH Keywords

law of the iterated logarithmurn modelmartingale central limit theoremlarge-index urntriangular urn

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Martingales with discrete parameter (60G42) Strong limit theorems (60F15) Combinatorial probability (60C05)

Cites Work

• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Maximum Degree of the Barabási–Albert Random Tree
• Concentration Inequalities and Martingale Inequalities: A Survey
• Title not available (Why is that?)
• Limit distributions for large Pólya urns
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures
• Embedding of Urn Schemes into Continuous Time Markov Branching Processes and Related Limit Theorems
• A generalized Pólya urn and limit laws for the number of outputs in a family of random circuits
• Degree asymptotics with rates for preferential attachment random graphs
• Analysis of a generalized Friedman's urn with multiple drawings
• Pólya-type urn models with multiple drawings
• Drawing multisets of balls from tenable balanced linear urns
• Characterization and enumeration of certain classes of tenable Pólya urns grown by drawing multisets of balls
• Polya Urn Models
• A new urn model
• A limit law for outputs in random recursive circuits
• Martingale functional central limit theorems for a generalized Pólya urn
• Analytic urns
• Gaussian approximation theorems for urn models and their applications
• An algebraic approach to Pólya processes
• Limit theorems for triangular urn schemes
• Moments of gamma type and the Brownian supremum process area
• On central limit and iterated logarithm supplements to the martingale convergence theorem
• Bernard Friedman's Urn
• Long and short paths in uniform random recursive dags
• The degree profile in some classes of random graphs that generalize recursive trees
• A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees
• On Generalized Pólya Urn Models
• On the depth of randomly generated circuits
• Smoothing equations for large Pólya urns
• Refined quicksort asymptotics
• Pólya Urns Via the Contraction Method
• The convergence of moments in the martingale central limit theorem
• On mixing sequences of random variables
• A note on the quicksort asymptotics

Cited In (9)

• Tree evolution processes for bucket increasing trees
• Azuma-Hoeffding bounds for a class of urn models
• Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions
• Multiple drawing multi-colour urns by stochastic approximation
• Periodic P\'olya urns and an application to Young tableaux
• The number of descendants in a random directed acyclic graph
• Unbalanced multi-drawing urn with random addition matrix
• Periodic Pólya urns, the density method and asymptotics of Young tableaux
• An urn model with random multiple drawing and random addition

This page was built for publication: On martingale tail sums in affine two-color urn models with multiple drawings

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