6
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Would it not be better to ask this at math.stackexchange.com? $\endgroup$
    – András Bátkai
    Commented Jul 11, 2011 at 20:29
  • 1
    $\begingroup$ Not a research question, voting to close. $\endgroup$
    – Igor Rivin
    Commented Jul 11, 2011 at 20:37
  • 8
    $\begingroup$ This does not seem like such an unreasonable question to me, though the answer should follow from the theory of order statistics. $\endgroup$
    – Richard Stanley
    Commented Jul 11, 2011 at 20:46

4 Answers 4

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

See

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

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ 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) $\endgroup$
    – Mc-
    Commented Jul 11, 2011 at 21:47
  • 2
    $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Commented Jul 11, 2011 at 23:27
  • 3
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Jul 12, 2011 at 1:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Commented Jul 12, 2011 at 1:31
  • 1
    $\begingroup$ 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" $\endgroup$
    – Mc-
    Commented Jul 12, 2011 at 2:00
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – eulerian
    Commented Jul 12, 2011 at 2:42
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .