Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

My problem is the following : throw (randomly, independantly) 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 ( would be $n {p \choose x} (\frac{1}{n})^x (1-\frac{1}{n})^{p-x}$) but i cant deduce what i want from that...

Did i miss something obvious ?

Any pointer ?

share|improve this question
    
Would it not be better to ask this at math.stackexchange.com? –  András Bátkai Jul 11 '11 at 20:29
    
Not a research question, voting to close. –  Igor Rivin Jul 11 '11 at 20:37
7  
This does not seem like such an unreasonable question to me, though the answer should follow from the theory of order statistics. –  Richard Stanley Jul 11 '11 at 20:46
add comment

4 Answers

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}$.

share|improve this answer
add comment

See

http://www.cs.berkeley.edu/~jfc/cs174/lecs/lec5/lec5.pdf

share|improve this answer
2  
I'm sorry but i don't see how this helps me... I've "solved" the question of empty bins, and of "probability of the existence of bins with >1 balls" which is the birthday paradox. My question is really how to get from what you give me to the "number of balls in the k most empty bins" (not the number of empty bins) –  Marc Jul 11 '11 at 21:47
1  
It helps you because it tells you what the distribution of the ball numbers is. The number of balls you care about is just the left tail of the Prob. Distribution function. –  Igor Rivin Jul 11 '11 at 23:27
2  
The distribution of the number of balls in each bin doesn't directly tell you about the order statistics which depend on the joint distribution. –  Douglas Zare Jul 12 '11 at 1:02
    
What I had meant to say was that the problem is equivalent to knowing how many urns there are with $j$ balls, for $j = 0, 1, \dots,$ which is not the distribution of balls in each bin. –  Igor Rivin Jul 12 '11 at 1:31
    
I thought that too ( thats why i put it in the question), but the only thing i see now would be to 1 use stirling formula to get rid of the \choose (let F denote this expressionof #bins containing x balls ) ; 2 "solve" $\int_{-\infty}^y x F dx = k$ -> to find "until which number of balls/bin i have to count balls" ; and 3 "compute" $\int_{-\infty}^y F dx $. For further simplifications of the formula, it seems hat i would need more assumptions on my variables and i think i cannot do the ones i would need. That's why i ask if there is another method to come to the result "more directly" –  Marc Jul 12 '11 at 2:00
show 1 more comment

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.

share|improve this answer
    
you can change min for max (you'll have to do more code if it is other order) and you have the expected number of balls in the fullest bin. –  eulerian Jul 12 '11 at 2:42
add comment
up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.