Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Jul 6, 2011

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.

1 comment:

  1. not able to find a closed form or simple expression.

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

    ReplyDelete