another balls and bins question I've seen many variations of this problem but I can't find a good, thorough explanation on how to solve it. I'm not just looking for a solution, but a step-by-step explanation on how to derive the solution.
So the problem at hand is: 
You have m balls and n bins. Consider throwing each ball into a bin uniformly and at random. 


*

*What is the expected number of bins that are empty, in terms of m and n?

*What is the expected number of bins that contain exactly 1 ball, in terms of m and n?


How would I approach solving this problem?
Thanks!
 A: Let's work out the probability there are $k$ balls (out of $m$) in the first bin (out of $n$).  This is a simple binomial probability with $p=1/n$ and $1-p = (n-1)/n$ so the probability is ${m \choose k} \dfrac{(n-1)^{m-k}}{n^m}$.  
The expected number of times the first bin has $k$ balls is the same, so the expected number of bins with $k$ balls is $n$ times this, i.e. 
$${m \choose k} \dfrac{(n-1)^{m-k}}{n^{m-1}}$$  
A: You want to use what are called indicator variables.  To see how this works, let's take your first problem.  Let $Y$ be the number of bins that are empty.  You want $E[Y]$.  Now define the indicator variables $X_i$ so that $X_i$ is $1$ if bin $i$ is empty and $0$ otherwise.  Then we have
$$Y = X_1 + X_2 + \cdots + X_n.$$
By linearity of expectation, 
$$E[Y] = E[X_1] + E[X_2] + \cdots + E[X_n].$$
So now the problem reduces to calculating the $E[X_i]$ for each $i$.  But this is fairly easy, as $$E[X_i] = 1 P(X_i = 1) + 0 P(X_i = 0) = P(X_i = 1) = P(\text{bin $i$ is empty}) = \left(1 - \frac{1}{n}\right)^m,$$
where the last equality is because balls $1, 2, \ldots, m$ must all go in a bin other than $i$, each with probability $1 - \frac{1}{n}$.
Therefore, $$E[Y] = n \left(1 - \frac{1}{n}\right)^m.$$
Your second problem can be worked in a similar fashion.  Let $Y$ be the number of bins that have exactly $1$ ball.  Let $X_i$ be $1$ if bin $i$ has exactly one ball and $0$ otherwise.  Then all that's left is to figure out $E[X_i]$, which is the probability that a given bin has exactly $1$ ball, and go from there.  Since this is homework, I'll let you finish. 
