Given K balls and N buckets how do you calculate the expected number of buckets with at least 1 ball. Each ball is put in a bucket chosen at random with a uniform probability distribution. Assume also K $\leq$ N.
Given K balls and N buckets what is the expected number of occupied buckets
-
0If you're speaking about expected numbers, you must be thinking about something that happens randomly according to some particular probability distribution. Please specify what it is that happens reandomly, and what the probability distribution is. – 2012-02-28
2 Answers
I will assume that we are throwing balls sequentially towards the buckets, with at any stage each bucket equally likely to receive a ball, and independence between throws. Then the probability that bucket $i$ has no balls in it after $K$ balls have been thrown is equal to $\left(\frac{N-1}{N}\right)^K.$
Let $X_i=1$ if the $i$-th bucket ends up with least $1$ ball, and let $X_i=0$ otherwise. Then $P(X_i=1)=1- \left(\frac{N-1}{N}\right)^K.$
Let $Y$ be the number of buckets with at least $1$ ball. Then $Y=\sum_{i=1}^N X_i.$ Now use the linearity of expectation. We can easily compute $E(X_i)$.
Remark: The $X_i$ are not independent, but that makes no difference to the calculation. That's the beauty of the formula $E(a_1X_1+a_2X_2+\cdots +a_NX_N)=a_1E(X_1)+a_2E(X_2)+\cdots +a_nE(X_N).$ We do not need to know the distribution of the random variable $\sum a_iX_i$ to find its expectation.
-
0@Raul: The idea that was used is very powerful, and has a number of nice generalizations. The combinatorics is in this case messy, and even after we arrive at expressions for the probabilities, for the expectation we have a long sum whose closed form evaluation is not obvious. – 2012-02-28