# Bounding probability where Markov/Chernoff bounds seem to fail

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

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

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<E(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$.