Putting m balls to n boxes (may empty)

Question

Suppose m balls randomly and independently put into n boxes. A box can hold more than 1 ball. Then what is the expected number of empty boxes? What is the expected number of balls that in a box with at lease one other ball?

For the first question, I don't understand why $P(X_i) = (\frac {n-1}{n})^m$ (this is the solution), where $X_i$ denotes event in which the $i^{th}$ box is empty. I think $P(X_i) = \frac {n-1}{n}$, since one ball has $n$ boxes to put in except the $i^{th}$. So where is the power of $m$ comes from?

I don't even have a clue how to solve the second question.

Answer 1

As JMoravitz has already commented, the probability $\frac{n-1}n$ of a single ball not being placed in a particular box is taken to the $m$-th power because we need the probability of all $m$ balls not being placed in that particular box, and by the multiplication principle we need to multiply the $m$ individual probabilities.

For the second question, for a particular ball the probability that none of the other $m-1$ balls are placed in its box is $\left(\frac{n-1}n\right)^{m-1}$, so the expected number of balls in a box with at least one other ball is

$$ m\left(1-\left(\frac{n-1}n\right)^{m-1}\right)\;. $$

Answer 2

We will verify the result by @joriki by direct enumeration which is not as simple but can perhaps serve as a computational exercise. This serves as a motivation to introduce modified Stirling numbers which make it possible to compute the variance as well as the expectation.

We have from first principles that the expectation is given by (choose the empty boxes first and then the ones that contain one ball only)

$$n^{-m} \sum_{k=0}^n {n\choose k} \sum_{q=0}^{n-k} {n-k\choose q} {m\choose q} q! {m-q\brace n-k-q}_{\ge 2} (n-k-q)! (m-q).$$

where the modified species of set partitions is given by $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 2}(\mathcal{Z}))$$

which gives the generating function $$\exp(u(\exp(z)-z-1))$$

and hence $${m-q\brace n-k-q}_{\ge 2} = (m-q)! [z^{m-q}] \frac{(\exp(z)-z-1)^{n-k-q}}{(n-k-q)!}.$$

Substitute this into the sum to get

$$n^{-m} m! \sum_{k=0}^n {n\choose k} \sum_{q=0}^{\min(n-k,m)} {n-k\choose q} (m-q) [z^{m-q}] (\exp(z)-z-1)^{n-k-q}.$$

We split this into two pieces, getting for the first piece

$$n^{-m} m! m \sum_{k=0}^n {n\choose k} \sum_{q=0}^{\min(n-k,m)} {n-k\choose q} [z^{m-q}] (\exp(z)-z-1)^{n-k-q}.$$

Now for the coefficient we put $$[z^{m-q}] (\exp(z)-z-1)^{n-k-q} \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m-q+1}} (\exp(z)-z-1)^{n-k-q} \; dz$$

and observe that this is zero when $q\gt m$ so we may set the upper limit of the inner sum to $n-k,$ getting for the inner sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \sum_{q=0}^{n-k} {n-k\choose q} z^q (\exp(z)-z-1)^{n-k-q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (\exp(z)-1)^{n-k} \; dz.$$

This yields for the outer sum $$n^{-m} m! m\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \sum_{k=0}^n {n\choose k} (\exp(z)-1)^{n-k} \; dz \\ = n^{-m} m! m\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \exp(nz) \; dz = n^{-m} m! m \frac{n^m}{m!} = m.$$

This can also be obtained by inspection because when we move $m$ to the front what remains is a classification according to the number of empty boxes, boxes with one ball, and boxes with more than one ball, and these are all the probabilities, so they must sum to one.

We continue with the second piece which is

$$- n^{-m} m! \sum_{k=0}^n {n\choose k} \sum_{q=0}^{\min(n-k,m)} q {n-k\choose q} [z^{m-q}] (\exp(z)-z-1)^{n-k-q}.$$

This time we get for the inner sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \sum_{q=1}^{n-k} {n-k\choose q} q z^q (\exp(z)-z-1)^{n-k-q} \; dz \\ = (n-k) \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \sum_{q=1}^{n-k} {n-k-1\choose q-1} z^q (\exp(z)-z-1)^{n-k-q} \; dz \\ = (n-k) \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \sum_{q=0}^{n-k-1} {n-k-1\choose q} z^{q+1} (\exp(z)-z-1)^{n-k-1-q} \; dz \\ = (n-k) \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m}} (\exp(z)-1)^{n-k-1} \; dz.$$

This yields for the outer sum of the second piece

$$- n^{-m} m! \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m}} \sum_{k=0}^n {n\choose k} (n-k) (\exp(z)-1)^{n-k-1} \; dz \\ = - n^{-m} m! n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m}} \sum_{k=0}^{n-1} {n-1\choose k} (\exp(z)-1)^{n-k-1} \; dz \\ = - n^{-m} m! n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m}} \exp((n-1)z) \; dz = - n^{-m} m! n \frac{(n-1)^{m-1}}{(m-1)!} \\ = - n^{-(m-1)} m (n-1)^{m-1}.$$

Collecting the two pieces we finally obtain

$$m - n^{-(m-1)} m (n-1)^{m-1} \\ = m \left(1 - \left(\frac{n-1}{n}\right)^{m-1}\right).$$

These data were verified with the following Maple program.

B :=
proc(n, m)
    option remember;
    local d, mset, ind, res;

    res := 0;

    for ind from n^m to 2*n^m-1 do
        d := convert(ind, base, n);
        d := [seq(d[v], v=1..m)];

        mset := convert(d, `multiset`);
        mset := select(p->p[2] >= 2, mset);

        res := res +
        add(p[2], p in mset);
    od;

    res;
end;

A similar yet somewhat simpler calculation can be found at this MSE link.