3
$\begingroup$

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?

  • 0
    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.2011-05-02
  • 0
    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.2011-05-02
  • 0
    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.2011-05-02
  • 0
    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.2011-05-02

0 Answers 0