An asymptotically optimal algorithm for generating bin cardinalities

DOI10.1016/J.MATCOM.2024.08.034MaRDI QIDQ6992705zbMATH OpenFDO

Authors Luc Devroye

Publication date 25 April 2025

Published in Mathematics and Computers in Simulation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.MATCOM.2024.08.034

zbMATH Keywords

balls-into-binsexpected time analysishashingrandom allocationsrandom variate generationsimulation

Mathematics Subject Classification ID

Combinatorial probability (60C05) Random number generation in numerical analysis (65C10)

Cites work

• A generalization of multiple choice balls-into-bins: tight bounds
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A rejection technique for sampling from T -concave distributions
• A simple algorithm for generating random variates with a log-concave density
• A simple generator for discrete log-concave distributions
• A universal generator for discrete log-concave distributions
• Algorithms and Computation
• Balanced Allocations
• Balanced allocations with the choice of noise
• Balanced allocations: caching and packing, twinning and thinning
• Balanced Allocations: The Heavily Loaded Case
• Concentration inequalities. A nonasymptotic theory of independence
• Efficient PRAM simulation on a distributed memory machine
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Fast generation of order statistics
• Generating Sorted Lists of Random Numbers
• Generating the maximum of independent identically distributed random variables
• Hashing, load balancing and multiple choice
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 4051016 (Why is no real title available?)
• scientific article; zbMATH DE number 4086850 (Why is no real title available?)
• scientific article; zbMATH DE number 3548141 (Why is no real title available?)
• scientific article; zbMATH DE number 3586221 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 1058056 (Why is no real title available?)
• scientific article; zbMATH DE number 2002843 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• scientific article; zbMATH DE number 7829335 (Why is no real title available?)
• On the analysis of randomized load balancing schemes
• Parallel randomized load balancing
• Polya Urn Models
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Sampling from binomial and Poisson distributions: a method with bounded computation times
• Sampling from the Poisson distribution on a computer
• The computer generation of multinomial random variates
• The computer generation of Poisson random variables
• The Computer Generation of Poisson Random Variables
• The power of thinning in balanced allocation
• The ratio of uniforms approach for generating discrete random variates

Cited in

(1)

• Fast simulations of the multi-album collector

This page was built for publication: An asymptotically optimal algorithm for generating bin cardinalities

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