Occupancy urn models in the analysis of algorithms

DOI10.1016/S0378-3758(01)00156-2zbMath0994.60006OpenAlexW2011545707WikidataQ126981807 ScholiaQ126981807MaRDI QIDQ1347968

Daniéle Gardy

Publication date: 15 May 2002

Published in: Journal of Statistical Planning and Inference (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0378-3758(01)00156-2

zbMATH Keywords

analysis of algorithmsurn modelrandom allocations

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Central limit and other weak theorems (60F05) Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05) Discrete mathematics in relation to computer science (68R99)

Related Items (3)

A sprouting tree model for random boolean functions ⋮ Asymptotic regimes for the occupancy scheme of multiplicative cascades ⋮ A phase transition for the heights of a fragmentation tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rotations in fringe-balanced binary trees
• Dynamic analysis of some relational databases parameters
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• On convergence rates in the central limit theorems for combinatorial structures
• A bivariate asymptotic expansion of coefficients of powers of generating functions
• Join sizes, urn models and normal limiting distributions
• Central and local limit theorems applied to asymptotic enumeration. II: Multivariate generating functions
• A unified presentation of some urn models
• An urn model from learning theory
• Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains
• Statistical profile estimation in database systems
• Normal Limiting Distributions for Projection and Semijoin Sizes
• Analysis and performance of inverted data base structures
• Approximating block accesses in database organizations
• On some generalized farlie-gumbel-morgenstern distributions-II regression, correlation and further generalizations
• A unified approach to limit theorems for urn models
• Trie size in a dynamic list structure

This page was built for publication: Occupancy urn models in the analysis of algorithms