Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.