Expectation of Maximum Frequency

222 Views Asked by At

I saw this question in a blog but do not know how to solve it.

Question: There are K balls in a sack numbered 1 to K. Bob chooses a ball at random and notes down its number and then puts it back in sack. He does this process for N times. What is the expected value of the frequency of the most frequent element?

1

There are 1 best solutions below

0
On

This is not exactly a solution, but it's too long for a comment. Also, for reasons stated below, I think you are unlikely to get a closed form solution.

This problem is equivalent to finding the expected length of the longest chain in a hash table. As such, it appears the problem has been extensively studied, yet no one has found a closed form solution. The best result seems to be that if $N, K \to \infty$ in such a way that $N/K = \alpha$ with $\alpha$ constant, then the average maximum occupancy (i.e., the frequency of the most frequent element, in your formulation of the problem) is asymptotic to $\ln N / \ln \ln N$.

Reference: Section 9.4 in An Introduction to the Analysis of Algorithms, Second Edition by Robert Sedgewick and Philippe Flajolet. The original paper appears to be by G. H. Gonnet, "Expected length of the longest probe sequence in hash code searching," Journal of the ACM 28, 1981, 289-309.