Occupancy urn models in the analysis of algorithms

DOI10.1016/S0378-3758(01)00156-2zbMath0994.60006WikidataQ126981807 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 algorithms; urn model; random allocations

Mathematics Subject Classification ID

68W40: Analysis of algorithms

60F05: Central limit and other weak theorems

05A15: Exact enumeration problems, generating functions

60C05: Combinatorial probability

68R99: Discrete mathematics in relation to computer science

Related Items

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

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