# Given K balls and N buckets what is the expected number of occupied buckets

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.

-
If 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. – Henning Makholm Feb 28 '12 at 15:14

## 1 Answer

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.

-
Thanks André, that was very clear and simple. I was taking the long path trying to do it with combinatorics. – Raul Feb 28 '12 at 15:42
@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. – André Nicolas Feb 28 '12 at 15:48