5
$\begingroup$

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)}$.
$\endgroup$
5
  • $\begingroup$ I had given an answer (roughly 2 years ago) in your blog about this, did you see that? $\endgroup$
    – esg
    May 17, 2021 at 18:29
  • $\begingroup$ @esg, can you give a link to your answer? $\endgroup$
    – kodlu
    May 17, 2021 at 22:29
  • 1
    $\begingroup$ @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! $\endgroup$
    – usul
    May 18, 2021 at 0:40
  • $\begingroup$ @kodlu: it was only a short comment, not a full answer. $\endgroup$
    – esg
    May 18, 2021 at 19:09
  • 2
    $\begingroup$ 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). $\endgroup$
    – esg
    May 18, 2021 at 19:14

1 Answer 1

3
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ Awesome, thank you very much! I will need to read up on my generatingfunctionology to follow, looking forward to it. $\endgroup$
    – usul
    May 20, 2021 at 4:22
  • 1
    $\begingroup$ Please let me know if anything is unclear or too succinct. I tried to be verbose, but of course it always depends. $\endgroup$
    – esg
    May 20, 2021 at 18:39
  • 1
    $\begingroup$ Thanks for the comments as well! Quick question: in your first line, I think the inequality should be reversed? $\endgroup$
    – usul
    May 22, 2021 at 20:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – usul
    May 22, 2021 at 20:51
  • $\begingroup$ (1) Quick question: yes, thanks, corrected (2) I will write you an email (tomorrow, I hope) $\endgroup$
    – esg
    May 23, 2021 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.