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.
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
Let $X_i=1$ if the $i$-th bucket ends up with least $1$ ball, and let $X_i=0$ otherwise. Then
Let $Y$ be the number of buckets with at least $1$ ball.
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.