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

Update: from esg's answer and a simple multiplicative Chernoff bound, I get that if $m \|A\|_k \geq \beta k$ and $\beta \geq 2$, then $\Pr[C_k \geq 1] \geq 1 - e^{-\beta k/8}$. Combining this with my fact above, rearranged, I get:

• If $m \leq \frac{\beta \cdot k}{\|A\|_k}$ for $\beta \leq \tfrac{1}{e}$, then $\Pr[\text{max load} \geq k] \leq e^{-k \ln(1/\beta)}$.
• If $m \geq \frac{\beta \cdot k}{\|A\|_k}$ for $\beta \geq 2$, then $\Pr[\text{max load} \geq k] \geq 1 - e^{-k (\beta/8)}$.