Expectation of Max Frequency
Source: Sent to me by Nikhil Garg (CSE Senior Undergrad, IITD) - who got this from Rudradev Basak Problem: There are K balls in a sack numbered 1 to K. Bob chooses a ball at random notes down its number and 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 ? Best of Luck! I do not have the solution. So, tell me if you get one. Thanks. Solution: Highlight the part between the * symbols for the answer. * There is no known closed form, but the expectation is exactly computable, and its asymptotics are understood. Exact formula. If M is the maximum frequency, E[M] = sum_{r=0}^{N-1} P(M > r), and P(M Values computed exactly from the formula and confirmed by simulation: K=5,N=10: 3.756; K=10,N=10: 2.749; K=10,N=20: 4.410; K=10,N=50: 8.690; K=20,N=20: 3.231; K=100,N=100: 4.233. Asymptotics (Gonnet 1981; Raab and Steger 1998, 'Balls into bins - a simple and tight analysis'). In the balanced regime ...