Bounding the max-loaded bin using${m \choose k} \|A\|_k^k$

Question

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

Answer 1

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