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](https://mathoverflow.net/a/323756/29697) 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](http://www.dblab.ntua.gr/%7Egtsat/collection/scheduling/Balls%20into%20Bins%20A%20Simple%20and%20Tight%20Anal.pdf) 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](https://math.stackexchange.com/questions/1352338/proof-for-the-upper-bound-and-lower-bound-for-binomial-coefficients) 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)}$.



Bounding the max-loaded bin using${m \choose k} \|A\|_k^k$
The following inequality holds:


$$\mathbb{P}(C\_k(m)\geq 1)\geq \mathbb{P}(\mathrm{Bin}(m, \lVert A\rVert\_k)\geq k)$$


where here and in the sequel $\mathrm{Bin}(n,p)$ denotes a binomially distributed random variable with parameter $n$ and $p$.


(I now change notation so I can use my old notes. In the sequel $r\geq 2$ is the "collision degree" (your $k$), $m$ is the number of bins (your $n$), $n$ is the time variable (number of balls, your $m$))


**Situation**:  

given are $m\geq 2$, a probability distribution $p\_1,\ldots,p\_m$ and an i.i.d. sequence $X\_1, X\_2,\ldots$ with $\mathbb{P}(X\_1=i)=p\_i$.


Let for $n\geq 1, 1\leq i \leq m\;\;$ $B\_i(n):=\sum\_{j=1}^n 1\_{\{X\_j=i\}}$ the number of occurrences of $i$ at "time" n, and let


$$T\_r:=\inf\{n\geq 1\,|\,\exists\,i\in\{1,\ldots m\}\,:\,B\_i(n)\geq r\}$$
the first time an element is observed $r$ times.


We are interested in upper bounds for $\mathbb{P}(T\_r>n)$ ( since
$\{T\_r\leq n\}=\{C\_r(n)\geq 1\}$ in your notation).


We use generating functions. Let $q\_r(t):=\sum\_{j=0}^{r-1} \frac{t^j}{j!}$ denote the $r$-th partial sum of the exponential series.
The joint distribution of $(B\_1(n),\ldots,B\_m(n))$ is the multinomial distribution with parameters $n$ and $p\_1,\ldots,p\_m$.
Since $$\{T\_r>n\}=\{B\_1(n)\leq r-1,\ldots, B\_m(n)\leq r-1\}$$
we have
$$\mathbb{P}(T\_r>n)=n!\,[t^n]\prod\_{i=1}^m q\_r(p\_it)\;.$$


Note also that $$\mathbb{P}(\mathrm{Bin}(n,p)\leq r-1)=n!\,[t^n] q\_r(pt)\,e^{(1-p)t}$$


We first recall a well known way to rewrite binomial probabilities.


**Reminder:**
Let $0<p<1$ and $q=1-p$. Then
$$\mathbb{P}(\mathrm{Bin}(n,p)\leq k)=q^{n-k}\sum\_{j=0}^k {n+j -k-1 \choose j} p^j$$


We first treat the case of two bins.


**Lemma** Let $p\_1,p\_2>0, p\_1+p\_2=1$ and $\lVert p\rVert\_r:=(p\_1^r+p\_2^r)^{1/r}$. Then
$$n![t^n] q\_r(p\_1t)q\_r(p\_2t)\leq n! [t^n] q\_r(\lVert p\rVert\_r, t)\,e^{(1-\lVert p\rVert\_r)t}=\mathbb{P}(\mathrm{Bin}(n,\lVert p\rVert\_r)\leq r-1)$$


**Proof:**
Denote the coefficients on the left hand side resp. right hand side by $a\_n$ resp. $b\_n$.
Clearly $a\_n=b\_n=1$ for $n\leq r-1$, and $a\_n=0<b\_n$ for $n>2r-2$. Let $n=r-1+j, 1\leq j \leq r-1$,
then on the left hand side
\begin{align\*} a\_{r-1+j} &=\sum\_{{k\leq r-1, i\leq r-1}\atop{ k+i=r-1+j}} \frac{(r-1+j)!}{k!j!} p\_1^kp\_2^i\\
 &=\mathbb{P}(j\leq \mathrm{Bin}(r-1+j,p\_1)\leq r-1)\\
 &=1 -\mathbb{P}(\mathrm{Bin}(r-1+j,p\_1)\leq j-1)-\mathbb{P}(\mathrm{Bin}(r-1+j,p\_1)\geq r)\\
 &=1 -\mathbb{P}(\mathrm{Bin}(r-1+j,p\_1)\leq j-1)-\mathbb{P}(\mathrm{Bin}(r-1+j,p\_2)\leq j-1)\\
 &=1 -\sum\_{k=0}^{j-1} {r+k-1 \choose k} (p\_1^rp\_2^k+p\_2^rp\_1^k)\end{align\*}


On the right hand side we have
\begin{align\*} b\_{r-1+j} &= \mathbb{P}(\mathrm{Bin}(r-1+j,\lVert p\rVert\_r)\leq r-1)\\
 &= 1-\mathbb{P}(\mathrm{Bin}(r-1+j,\lVert p\rVert\_r)\geq r)\\
 &= 1-\mathbb{P}(\mathrm{Bin}(r-1+j,1-\lVert p\rVert\_r)\leq j-1)\\
 &= 1 -{\lVert p\rVert\_r}^r \sum\_{k=0}^{j-1} {r+k-1 \choose k} (1-\lVert p\rVert\_r)^k\end{align\*}
where the reminder was used for the final equality. But $1-\lVert p\rVert\_r\le \min\{p\_1,p\_2\}$ (since $\lVert p\rVert\_r\ge \max\{p\_1,p\_2\}$) and thus for $k\ge 0$
$$(1-\lVert p\rVert\_r)^k {\lVert p\rVert\_r}^r\leq p\_1^kp\_2^r+p\_2^kp\_1^r$$
and the claim follows.
**End of proof**


Now to the general case:


**Theorem** Let
$\lVert p\rVert\_r:=\left(p\_1^r + \ldots + p\_m^r\right)^{1/r}$
. Denote by $T\_r:=T\_r(p\_1,\ldots,p\_m)$
the time of the first occurrence of the first $r$-collision in $\{1,\ldots,m\}$. Then
$$\mathbb{P}(T\_r>n)\leq \mathbb{P}(\mathrm{Bin}(n,\lVert p\rVert\_r)\leq r-1)$$
**Proof**:
From the lemma above we get that for any $p\_1,p\_2>0$ and $k\geq 0$
$$[t^k] q\_r(p\_1 t)q\_r(p\_2 t)\leq [t^k] q\_r(\lVert(p\_1,p\_2)\rVert\_r t)\,e^{(p\_1+p\_2-\lVert(p\_1,p\_2)\rVert\_r)t}$$


Hence
\begin{align\*}
[t^n] q\_r(p\_1 t)q\_r(p\_2 t)q\_3(p\_3 t)&= \sum\_{k=0}^n [t^{n-k}] q\_r(p\_3t)\, [t^k] q\_r(p\_1 t)q\_r(p\_2 t)\\
&\le \sum\_{k=0}^n [t^{n-k}] q\_r(p\_3 t)\, [t^k] q\_r(\lVert(p\_1,p\_2)\rVert\_r t)\,e^{(p\_1+p\_2-\lVert(p\_1,p\_2)\rVert\_r)t}\\
&=[t^n] q\_r(p\_3 t)q\_r(\lVert(p\_1,p\_2)\rVert\_r t)\,e^{(p\_1+p\_2-\lVert(p\_1,p\_2)\rVert\_r)t}\\
&= \sum\_{k=0}^n [t^{k}] q\_r(p\_3 t) q\_r(\lVert(p\_1,p\_2)\rVert\_r t)\,[t^{n-k}]e^{(p\_1+p\_2-\lVert(p\_1,p\_2)\rVert\_r)t}\\
&\leq \sum\_{k=0}^n [t^{k}] q\_r(\lVert (p\_1,p\_2,p\_3)\rVert\_r t) e^{(p\_3+\lVert(p\_1,p\_2)\rVert\_r -\lVert (p\_1,p\_2,p\_3)\rVert\_r) t}\,[t^{n-k}]e^{(p\_1+p\_2-\lVert(p\_1,p\_2)\rVert\_r)t}\\
&= [t^n] q\_r(\lVert (p\_1,p\_2,p\_3)\rVert\_r t) e^{(p\_1+p\_2+p\_3-\lVert (p\_1,p\_2,p\_3)\rVert\_r)t}
\end{align\*}
and induction gives that
$$[t^n] \prod\_{i=1}^m q\_r(p\_i,t) \leq [t^n] q\_r(\lVert p\rVert\_r,t) e^{(p\_1+\ldots+p\_m-\lVert p\rVert\_r)t}$$
Thus  

\begin{align\*}
\mathbb{P}(T\_r>n)&= n! [t^n] \prod\_{i=1}^m q\_r(p\_i,t) 
 \leq n! [t^n] q\_r(\lVert p\rVert\_r,t) e^{(1-\lVert p\rVert\_r)\,t}
 =\mathbb{P}(\mathrm{Bin}(n,\lVert p\rVert\_r)\leq r-1)
\end{align\*}
**End of proof**


**Remarks**:


(1) a completely different proof for the case $r=2$ was given in <https://eprint.iacr.org/2005/318> (Theorem 3).


(2) using $\mathbb{E}(X)=\sum\_{n=0}^\infty \mathbb{P}(X>n)$ (for the expectation of a random variable with values in the nonnegative integers) and the inequality above
gives
$$\mathbb{E}(T\_r)\leq \frac{r}{\lVert p\rVert\_r}$$


(3) always $\mathbb{P}(\mathrm{Bin}(n,p)<r)\geq (1-p^r)^{n \choose r}$. The proved inequality is thus weaker than your conjecture above.


ADDED:


(4) The conjectured inequality
$$\mathbb{P}(T\_r>n)\leq (1-\lVert p\rVert\_r^r)^{n \choose r}$$ is false. It can be violated if the $p\_i$ are not uniformly small. Consider e.g. the case $p\_1=\frac{1}{2}$, $p\_1=\ldots=p\_m=\frac{1}{2(m-1)}$ and $r=2, n=3$.
For $m\longrightarrow \infty$
\begin{align\*}
\mathbb{P}(T\_2>3)&\longrightarrow \mathbb{P}(\mathrm{Bin}(3,\frac{1}{2})\leq 1)=\frac{1}{2} \mbox{ and } \lVert p\rVert\_2\longrightarrow \frac{1}{2}, \\(1- \lVert p\rVert\_2^2)^3 &\longrightarrow \frac{27}{32}
\end{align\*}
Thus the inequality is violated for all sufficiently large $m$.


