0
$\begingroup$

This is related to the question I have asked yesterday: Expected value of max/min of random variables.

Assume you have $n$ urns and $k$ balls. Each ball is placed uniformly at random in one of the urns. Let $X_i$ denote the number of balls in urn $i$ and let $X = \min\{X_1,\ldots,X_n\}$.

I am looking for a $k$ such that $ Pr[X < 2\log(n)] < \frac{2}{n}. $ Clearly

$ Pr[X < 2\log(n)] = Pr[\bigcup_{i=0}^n X_i < 2\log(n)] \leq n*Pr[X_1 < 2\log(n)]$

Here is where it stops for me. We have to find an upper bound for $Pr[X_1 < 2\log(n)]$ but as far as I am apt in applying Chernoff/Markov bounds, one can only get a lower bound for this kind of expression.

Am I missing something? Or is there perhaps another way to solve the problem?

2 Answers 2

1

Chernoff bound for lower deviations reads $P(Y\le y)\le a^yE(a^{-Y})$ for every $a\ge1$. Then, as is usual in these deviations bounds, one optimizes over $a\ge1$. If $Y$ is sufficiently integrable and $y, one knows there exists some $a>1$ such that $a^yE(a^{-Y})<1$, hence the upper bound is not trivial.

It can be more convenient to use the equivalent upper bound $P(Y\le y)\le \mathrm{e}^{ty}E(\mathrm{e}^{-tY})$ for every $t\ge0$.

In your case, any $k\le 2n\log n$ is hopeless and it seems every $k\ge6.3n\log n$ works. To see this, recall that, for $t\ge0$ and $X_1$ binomial $(k,1/n)$, $ E(\mathrm{e}^{-tX_1})=(1-(1-\mathrm{e}^{-t})/n)^k\le\exp(-(1-\mathrm{e}^{-t})k/n). $ Using this for $k=cn\log(n)$, one gets $ P(X_1\le2\log n)\le\exp(2t\log(n)-(1-\mathrm{e}^{-t})c\log(n)). $ This upper bound is less than $1/n^2$ as soon as $ 2t\log(n)-(1-\mathrm{e}^{-t})c\log(n)\le-2\log(n), $ that is, as soon as $c$ is such that there exists $t\ge0$ such that $ 2t-(1-\mathrm{e}^{-t})c+2\le0, $ that is, for every $c\ge c^*$, with $ c^*=2\,\inf_{t\ge0}\frac{1+t}{1-\mathrm{e}^{-t}}<6.2924. $ Note that the OP asked for an upper bound of $2/n$ and this gives an upper bound of $1/n$.

1

$X_1$ is a binomial random variable with parameters $k$ and $1/n$, so mean $\mu = k/n$. Chernoff should say $P(X_1/k < 1/n - \epsilon) \le e^{-D k}$ where $D = (1/n - \epsilon) \log(1 - \epsilon n) + (1 - 1/n + \epsilon) \log(1 + \epsilon n/(n-1))$.