**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.

not able to find a closed form or simple expression.

ReplyDeletebut could form a polynomial,in summation form, which would generate the answer.

total number of elements in sample space = k^n.

now recall that total number of permutations of n balls under condition that a1 balls are of color 1,..ai balls are of color i, is n!/[a1! a2!...ak!]

so,total number of elements in sample space with max. frequency <= r is equal to coefficient of x^n in f(r)

where f(r)= n!(1+x+x^2/2!+...x^r/r!)^k.

So, total number of elements in sample space with max. frequency = r is equal to coefficient of x^n in f(r)-f(r-1).

so, required expected value is coefficient of x^n in

(1/k^n) * sigma ,r=1 to n, r * [f(r)-f(r-1].

the above polynomial after re-arrangement can be wrtten as

(1/k^n)[ n f(n)- sigma, r= 1 to n, f(r-1) ]

where f(r)= n! * (1+x+x^2/2!+...x^r/r!)^k.