Expected number of empty bins

Question

You route 10 orders, each independently to one of 10 queues chosen uniformly at random. What is the expected number of queues that receive no order?

Accepted Answer

Let X be the number of empty queues. For queue k, define Ik = 1 if queue k receives no order. Then X = \sum{k=1}^{10} Ik. A given order misses queue k with probability 	frac{9}{10}, and all 10 orders miss it independently, so E[Ik] = P(	ext{queue } k 	ext{ empty}) = \left(\frac{9}{10}ight)^{10}. By linearity of expectation, E[X] = 10 \cdot \left(\frac{9}{10}ight)^{10} = 10 \cdot 0.3487 \approx 3.49. So about 3.5 of the 10 queues stay empty on average, even though there are exactly as many orders as queues. In general, throwing m balls into n bins leaves n(1 - 1/n)^m empty on average, w…

Expected number of empty bins

Your answer

More Probability questions