Question

Question:What is the expected number of bins that remain empty when \(m\)balls are distributed into \(n\) bins uniformly at random.

Short answer

Answer

The resultant answer is \(\frac{{{{(n - 1)}^m}}}{{{n^{m - 1}}}}\).

Step-by-step solution

Given data

The given data is \(m\) balls and \(n\)bins.

Find the probability of the first bin

Define \(n\) variables \({X_1},{X_2},{X_3}, \ldots \ldots ..,{X_n}\)

Where \({X_i} = 1\) if \({i^{{\rm{th }}}}\) bin is empty otherwise \({X_i} = 0\).

Number of empty bins .

Probability that the first bin is empty \( = {\left( {\frac{{n - 1}}{n}} \right)^m}\)

\(\begin{aligned}{}E\left( {{X_1}} \right) &= {\left( {\frac{{n - 1}}{n}} \right)^m} \times 1 + 0\\E\left( {{X_1}} \right) &= {\left( {\frac{{n - 1}}{n}} \right)^m}\end{aligned}\)

Similarly, \(E\left( {{X_2}} \right) = E\left( {{X_3}} \right) = E\left( {{X_4}} \right) = \ldots \ldots \ldots \ldots E\left( {{X_n}} \right) = {\left( {\frac{{n - 1}}{n}} \right)^m}\)

the expected number of bins that remain empty when \(m\) balls are distributed into \(n\) bins uniformly at random;

\(\begin{aligned}{}E\left( {{X_1} + } \right.\left. {{X_2} + \ldots \ldots + {X_n}} \right) &= E\left( {{X_1}} \right) + E\left( {{X_2}} \right) + \ldots \ldots + E\left( {{X_n}} \right)\\E\left( {{X_1} + } \right.\left. {{X_2} + \ldots \ldots + {X_n}} \right) &= n \times {\left( {\frac{{n - 1}}{n}} \right)^m}\\E\left( {{X_1} + } \right.\left. {{X_2} + \ldots \ldots + {X_n}} \right) &= \frac{{{{(n - 1)}^m}}}{{{n^{m - 1}}}}\end{aligned}\).