Throw $m$ balls into $n$ bins independently, each ball selecting a bin from the distribution $A \in \Delta_n$. This question is about **lower-bounding the max-loaded bin**.

**Background.** In [this MO answer][1] I wrote about an upper bound based on collisions. Let $Z_k$ be all subsets of $k$ distinct balls. For $S \in Z_k$, let $1_S$ be the indicator that all balls in $S$ land in the same bin. Then $\mathbb{E} [1_S] = \sum_{i=1}^n A_i^k = \|A\|_k^k$. Let $C_k = \sum_{S \in Z_k} 1_S$, the number of $k$-way collisions. Then by Markov's inequality,
  $$ \Pr[ \text{max-loaded bin }  \geq k] = \Pr[ C_k \geq 1] \leq \mathbb{E}[C_k] = {m \choose k} \|A\|_k^k . $$

For example, in the classic case of $m=n$ and uniform $A$, where $\|A\|_k^k = n^{1-k}$, we can use Stirling to get a bound closely approaching $\frac{n}{k^k}$, as expected. And this bound can be very tight: if we throw half as many balls (cut $m$ in half), the probability decreases by a factor of about $2^k$.

**Question.**
> Is there a lower-bound on the max-loaded bin that matches this upper bound, in a sense? Or, what is the tightest non-asymptotic lower bound you know for this setting?

**Motivation.** First, notice that if we pretended each collision $1_S$ were independent, we would obtain
 $$ \Pr[ \text{max-loaded bin} < k ] = \Pr[ C_k = 0] = \Pr[1_S = 0 ~ (\forall S \in Z_k)] \leq \left(1 - \|A\|_k^k\right)^{m \choose k} \leq \exp\left(- {m \choose k} \|A\|_k^k\right) . $$

That would be such a cool result, matching the upper bound so neatly. Unfortunately, the collisions are positively associated, not negatively: $\Pr[1_S = 1 \mid 1_{S'} = 1] \geq \Pr[1_S = 1]$. So I don't know of techniques to prove this. (Yet simulations suggest something not too far away could hold, at least for $A$ uniform...)

**What else I've tried.** Well, if $X_i$ is the number of balls in bin $i$, then the $X_i$ are negatively associated, so I think we can get a bound by pretending the $X_i$ are independent Binomials, but it doesn't match. The standard approach would be to bound the variance of $C_k$ and use Chebyshev. I was able to get an only-somewhat-horrible expression for $\text{Var}(C_k)$, but I had trouble pushing it through to get a tight bound here. It might work. Finally, I'll mention that [Raab and Steger][2] is only asymptotic, whereas I'm hoping with this approach to get a concrete bound for any given $m,n,k$.

----

Edit: esg once gave me this hint, but I was unable to prove it:

> one can show that
$\mathbb{P}\big(C_k(m)\geq 1\big)\geq \mathbb{P}(\mathrm{Binom}\big(m,\lVert A\rVert_k\big)\geq k)$
where $\mathrm{Binom}\big(m,p)$ denotes a r.v. with has a Binomial distribution
with parameters $m$ and $p$ 

----

Some more details: We [know][3] that ${m \choose k} = \left(\frac{\Theta(m)}{k}\right)^k$, so the upper bound above looks like $\left(\frac{\Theta(m) \|A\|_k}{k}\right)^k$. So what really matters is the ratio $\frac{m \|A\|_k}{k}$, and we get an exponential-in-$k$ bonus.

My most optimistic hope is that the same expression provides a lower bound, where perhaps the constant factor of $m$ just decreases. From some simulations, I'm not sure this is true. We could instead hope to use $\left(\frac{\Theta(m) \|A\|_k}{k}\right)^{c}$, which it sounds like esg's approach can do at least for constant $c$. From simulations, I'm confident this dependence is true at least for the uniform distribution and $c=k/2$.


  [1]: https://mathoverflow.net/a/323756/29697
  [2]: http://www.dblab.ntua.gr/~gtsat/collection/scheduling/Balls%20into%20Bins%20A%20Simple%20and%20Tight%20Anal.pdf
  [3]: https://math.stackexchange.com/questions/1352338/proof-for-the-upper-bound-and-lower-bound-for-binomial-coefficients