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

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)}$$.
– esg
May 17, 2021 at 18:29
• @esg Oh yes, thanks, I tried to prove it but was not able to. I pasted your comment in above. A proof sketch would be much appreciated!
– usul
May 18, 2021 at 0:40
• @kodlu: it was only a short comment, not a full answer.
– esg
May 18, 2021 at 19:09
• I will try to post a full answer in the next few days. In the meanwhile you may be interested in the proof for the case $k=2$ given in eprint.iacr.org/2005/318 (Theorem 3).
– esg
May 18, 2021 at 19:14

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 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 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). The proved inequality is thus weaker than your conjecture above.

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

• Awesome, thank you very much! I will need to read up on my generatingfunctionology to follow, looking forward to it.
– usul
May 20, 2021 at 4:22
• Please let me know if anything is unclear or too succinct. I tried to be verbose, but of course it always depends.
– esg
May 20, 2021 at 18:39
• Thanks for the comments as well! Quick question: in your first line, I think the inequality should be reversed?
– usul
May 22, 2021 at 20:21
• Also, any reference where this argument is published or used? I think we can use it to get a pretty complete picture, see the edited end of my question. Would be happy to help you write this up and put it on arxiv if you are interested. I would benefit from having something to cite.
– usul
May 22, 2021 at 20:51
• (1) Quick question: yes, thanks, corrected (2) I will write you an email (tomorrow, I hope)
– esg
May 23, 2021 at 13:51