How many random questions are necessary to identify \(n\) distinct objects?

DOI10.1016/0097-3165(90)90072-5zbMath0738.05007OpenAlexW2023964119MaRDI QIDQ1813292

Herman Rubin, Boris G. Pittel

Publication date: 25 June 1992

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(90)90072-5

zbMATH Keywords

digital search tree

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Asymptotic enumeration (05A16)

Related Items (7)

On the distribution for the duration of a randomized leader election algorithm ⋮ A note on the probabilistic analysis of patricia trees ⋮ Profiles of PATRICIA tries ⋮ Analysis of random LC tries ⋮ How to count quickly and accurately: A unified analysis of probabilistic counting and other related problems ⋮ Asymmetric Rényi Problem ⋮ Laws of large numbers and tail inequalities for random tries and PATRICIA trees

Cites Work

• Unnamed Item
• Unnamed Item
• A probabilistic analysis of the height of tries and of the complexity of triesort
• Asymptotical growth of a class of random trees
• A diffusion limit for a class of randomly-growing binary trees
• Paths in a random digital tree: limiting distributions
• Analysis of Extendible Hashing

This page was built for publication: How many random questions are necessary to identify \(n\) distinct objects?