The Probability to Hit Every Bin with a Linear Number of Balls

2024/03/01 by Walzer, Stefan
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2403.00736

Abstract

Assume that 2n balls are thrown independently and uniformly at random into n bins. We consider the unlikely event E that every bin receives at least one ball, showing that Pr[E] = Θ(bⁿ) where b ≈ 0.836. Note that, due to correlations, b is not simply the probability that any single bin receives at least one ball. More generally, we consider the event that throwing αn balls into n bins results in at least d balls in each bin.

Related

• On the Average Maximal Number of Balls in a Bin Resulting from Throwing r Balls into n Bins T times
• A Short Note on the Average Maximal Number of Balls in a Bin
• Balls and Bins -- Simple Concentration Bounds
• Expected number of uniformly distributed balls in a most loaded bin using placement with simple linear functions
• Avoiding defeat in a balls-in-bins process with feedback