What is the expected number of bins that remain empty when m balls are distributed into n bins uniformly at random?

Question

Answer: (n − 1)^m /n^m−1

Answer 1

Let P(X_i) be the probability that bin i is empty. So, 

P(X_i) = [(n-1)/n]^m

E(X_i) = 1 *  [(n-1)/n]^m

Now, we require the expectation of ∑ X_i which is equal to the summation of their individual expectation as per linearity of expectation. 

So, expected number of empty bins = ∑ E(X_i)

= n E(X_i) (as summation is from 1 to n)

= n  [(n-1)/n]^m

http://www.cse.iitd.ac.in/~mohanty/col106/Resources/linearity_expectation.pdf

Comments

@arjun sir..here why multiplied with 1?should'nt it b 'i'?

"E(X_i) = 1 *  [(n-1)/n]^m