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.
Probability – Expected Number of Occupied Buckets with K Balls and N Buckets
combinatoricsprobability
Best 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.