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

#### Solutions Collecting From Web of "Given K balls and N buckets what is the expected number of occupied buckets"

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.