Question: I have a typical $m$ balls in $n$ bins question, where I'm trying to find the expected number of balls in each bin.
Each ball is independently placed into one of the n bins, so there is a $\frac1n$ chance for each bin.
My Guess: I believe that the expected value should be something like $\frac mn$, but I'm not sure how to prove it.
I started by using an indicator random variable $X_i$ = the event in which the $i$-th ball is in a bin.
$X_i = 1$ with probability $\frac 1n$ OR $0$ with probability $1-\frac 1n$.
E(number of balls in each bin) = $E(X_1)+E(X_2)+ … + E(X_m) = m\cdot E(X_i) = \frac mn$
But I think that the proof doesn't seem correct, can anyone explain where I went wrong (if I did go wrong)?
Thanks!
Best Answer
By way of enrichment here is a proof using generating functions that is closely related to Stirling numbers. We have for balls-in-bins with the sets going into the bins having the number of elements marked the bivariate species
$$\mathfrak{S}_{=n}(\mathcal{U}^0 \mathfrak{P}_{=0}(\mathcal{Z}) + \mathcal{U}^1 \mathfrak{P}_{=1}(\mathcal{Z}) + \mathcal{U}^2 \mathfrak{P}_{=2}(\mathcal{Z}) + \mathcal{U}^3 \mathfrak{P}_{=3}(\mathcal{Z}) + \cdots).$$
This yields the bivariate generating function
$$G(z, u) = \exp(uz)^n.$$
The desired expectation is a grand average and is given by
$$\frac{1}{n\times n^m} \times m! [z^m] \left. \frac{d}{du} G(z, u) \right|_{u=1}.$$
This is
$$\frac{1}{n\times n^m} \times m! [z^m] \left. \exp(nuz) \times nz \right|_{u=1} = \frac{1}{n\times n^m} \times m! [z^m] \exp(nz) \times nz \\ = \frac{1}{n^m} \times m! [z^{m-1}] \exp(nz) = \frac{1}{n^m} \times m! \frac{n^{m-1}}{(m-1)!}.$$
This simplifies to
$$\bbox[5px,border:2px solid #00A000]{\frac{m}{n}}$$
as claimed. This is of course the only answer that makes any sense here.