Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to solve the following problem.

Let there be $n$ urns and let us have $k$ balls. Assume we put every ball into one of the urns with uniform probability. Denote by $X_i$ the random variable counting the number of balls in urn $i$. If $X = min\{X_1,\ldots,X_n\}$, what is $E[X]$?

As a more general question, one could ask: what is the expected value of the minimum of some equally distributed random variables?

I do not see any way of solving it besides using the definition of expected value which results in a nasty expression.

I believe there is some better technique for approaching this kinds of problems.

Anyone happens to know how?

share|improve this question
    
I would expect this particular question to be difficult. It may be easier in cases where the random variables are identically and independently distributed, using order statistics methods, but they are not independent here. –  Henry May 2 '11 at 0:02
    
So in the limit where $n$ is large (lots of urns) and $k = \alpha n$, the number of balls in urn $i$ will be approximately Poisson with mean $\alpha$. Furthermore if $n$ is large then the counts in the different boxes will be approximately independent. So you can probably get an approximate answer starting from this using order statistics methods, as Henry suggested. –  Michael Lugo May 2 '11 at 0:28
    
It seems that for $n=2$, $E\left[\min (X_i)\right]$ may be $k\left(1/2 - {{k-1} \choose {\lfloor k/2 \rfloor}} / 2^k \right)$. I would not expect this to get easier in general. –  Henry May 2 '11 at 0:31
    
Perhaps it does get easier. For $n=2$ and large $k$ it seems that $\dfrac{k}{2} - \sqrt{\dfrac{k}{2\pi}}$ is a reasonable approximation. In general, $\dfrac{k}{n}$ is clearly an upper bound, so perhaps there is a general approximation. –  Henry May 2 '11 at 0:51

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.