expected number of balls in k emptiest bins My problem is the following: throw (randomly, independently) $p$ balls in $n$ bins. What is the expected number of balls in the $k$ emptiest bins?
I have some results about the expected number of bins with $x$ balls (that would be $n {p \choose x} (\frac{1}{n})^x (1-\frac{1}{n})^{p-x}$) but I can't deduce what I want from that... 
Did I miss something obvious? Any pointers?
 A: This is only a very partial answer, and I would have considered putting it as a comment if I were a more reputable contributor, but I hope it's at least somewhat helpful.
Consider the simplest possible non-trivial case, $p=2$ and $k=1$ -- i.e., you're looking for the expected number of balls in the "lighter" of two bins.  It's easy to see this is related to asking for the expected distance to the origin of a random walk, which, if I remember correctly, is asymptotic to $\sqrt{2n/\pi}$.  So the expected number of balls in the smaller bin is asymptotic to $n/2 - \sqrt{n/2\pi}$.  
A: See 
http://www.cs.berkeley.edu/~jfc/cs174/lecs/lec5/lec5.pdf
A: It is a generalization of the birthday problem.
Here is a 1 line code in R who simulates the problem:
my_simulation<-function(N,nelems,to)mean(unlist(lapply(1:N,function(a){min(table(sample(1:to,nelems,T) ))})))
for instance my_simulation(1000,50,10) gives the answer where there are 50 balls and 10 bins (1000 simulations).
Hope that helps.
A: The most interesting/relevant thing i found was in the Newman-Shepp's generalization of the coupon collector problem, which seems to be the exact dual problem of the balls in the emptiest bin ( = "how many balls do you have to throw to ensure there are $x$ in every bin [and thus in the emptiest] ")
According to http://en.wikipedia.org/wiki/Coupon_collector%27s_problem#Extensions_and_generalizations
...the expected number is $ p = n\log n + (x-1)n\log\log n + O(n)$
So my guess for the emptiest bin would be to invert this formula (express $x$ in function of the rest) , and i have a bound on the number in k emptiest, quite good if $ k << n$ (well, the estimation being for $n \to \infty$, this seems okay :-) )
Maybe i should see the proofs of this to see if there are ideas that can be adapted & formalized. 
