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 it holds, 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$.


  [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