$\displaystyle\leq\mu_{i}^{3}+\alpha_{i}^{\lfloor{\mu_{i}}\rfloor}\mathbb{E}\left[{\mathcal{Y}_{i}^{3}}\right]\leq\mu_{i}^{3}+\mathbb{E}\left[{\mathcal{Y}_{i}^{3}}\right]\;.$

In the first inequality we have used that the geometric distribution is
memoryless. Now simple calculations give that
$\mathbb{E}\left[{\mathcal{Y}_{i}^{3}}\right]\leq 6\mu_{i}(1+\mu_{i})^{2}\leq
24\mu_{i}$, so we get that
$\mathbb{E}\left[{\left|{\mathcal{Y}_{i}-\mu_{i}}\right|^{3}}\right]\leq\mu_{i}^{3}+24\mu_{i}\leq
25\mu_{i}$.

Depending on $\mathbb{E}\left[{S_{d}}\right]$ we will prove different bounds
on $f_{d}$. Let $M>0$ be a large constant. We will prove that if
$\mathbb{E}\left[{S_{d}}\right]<C+M\sqrt{C}$ then $f_{d}\geq L$, if
$C+M\sqrt{C}\leq\mathbb{E}\left[{S_{d}}\right]<C+\tfrac{1}{4}C$ then
$f_{d}\geq
L\varepsilon\sqrt{C\log\left(\tfrac{1}{\varepsilon\sqrt{C}}\right)}$, and if
$C+\tfrac{1}{4}C\leq\mathbb{E}\left[{S_{d}}\right]$ then $f_{d}\geq
L\varepsilon C$. This will prove the result since
$\varepsilon\sqrt{C\log\left(\tfrac{1}{\varepsilon\sqrt{C}}\right)}\geq\varepsilon
C$ if and only if $C\geq\left(1/(\varepsilon\sqrt{C})\right)$, and since
$C\leq\gamma/\varepsilon^{2}$ for a small constant $\gamma$ then
$1\geq\min\left\\{\varepsilon\sqrt{C\log\left(\tfrac{1}{\varepsilon\sqrt{C}}\right)},\varepsilon
C\right\\}$.

If $\mathbb{E}\left[{S_{d}}\right]<C+M\sqrt{C}$ then we will show that
$f_{d}\geq L$. This will follow by a usage of the Berry-Esseen theorem.

######  Theorem 18 (Berry Esseen theorem).

Let $X_{1},\ldots,X_{d}$ be independent random variables with
$\mathbb{E}\left[{X_{i}}\right]=0$,
$\mathbb{E}\left[{X_{i}^{2}}\right]=\sigma_{i}^{2}>0$, and
$\mathbb{E}\left[{\left|{X_{i}}\right|^{3}}\right]=\rho_{i}<\infty$. Let
$F_{d}$ be the cumulative distribution function of $\sum_{i=1}^{d}X_{i}$, let
$\Phi$ be the cumulative distribution function of the standard normal
distribution, and let $\sigma^{2}=\sum_{i=1}^{d}\sigma^{2}$. Then,

$\displaystyle\sup_{x\in\mathbb{R}}\left|{F_{d}(x)-\Phi(x/\sigma)}\right|\leq
K_{1}\frac{\sum_{i=1}^{d}\rho_{i}}{\sigma^{3}}\;.$

where $K_{1}$ is a universal constant.

Since $\mathbb{E}\left[{S_{d}}\right]<C+M\sqrt{C}$ then
$C\geq\mathbb{E}\left[{S_{d}}\right]-M\sqrt{\mathbb{E}\left[{S_{d}}\right]}\leq\mathbb{E}\left[{S_{d}}\right]-M\sqrt{\sum_{i=1}^{d}\sigma_{i}^{2}}$
and we get that
$f_{d}=\Pr\left[S_{d}<C\right]\geq\Pr\left[S_{d}<\mathbb{E}\left[{S_{d}}\right]-M\sqrt{\sum_{i=1}^{d}\sigma_{i}^{2}}\right]$.
Now the Berry-Esseen theorem give us that,

$\displaystyle
f_{d}\geq\Pr\left[S_{d}<\mathbb{E}\left[{S_{d}}\right]-\sqrt{\sum_{i=1}^{d}\sigma_{i}^{2}}\right]\geq\Phi(-M)-K_{1}\frac{\sum_{i=1}^{d}\mathbb{E}\left[{\left|{\mathcal{Y}_{i}-\mu_{i}}\right|^{3}}\right]}{\left(\sum_{i=1}^{d}\sigma_{i}^{2}\right)^{3/2}}$

We know that
$\mathbb{E}\left[{\left|{\mathcal{Y}_{i}-\mu_{i}}\right|^{3}}\right]\leq
25\mu_{i}$ and that $\sigma_{i}^{2}\geq\mu_{i}$ for all $1\leq i\leq d$, so we
get that,

$\displaystyle
f_{d}\geq\Phi(-M)-25K_{1}\frac{\mathbb{E}\left[{S_{d}}\right]}{\mathbb{E}\left[{S_{d}}\right]^{3/2}}\geq\Phi(-M)-25K_{1}\sqrt{8L}\geq
L\;.$

Here we have used that $\mathbb{E}\left[{S_{d}}\right]\geq
C/2\geq\frac{1}{8L}$ and that $L$ is sufficiently small.

Now we consider the case where $\mathbb{E}\left[{S_{d}}\right]\geq
C+M\sqrt{C}$. We define $\beta_{d}=\mathbb{E}\left[{S_{d}}\right]-C$ and note
that $\beta_{d}\geq M\sqrt{C}$. We will need the following claim.

######  Claim 3.

For all $1\leq d\leq k$ and all integers $t\geq 1$ we have that,

$\frac{\Pr\left[S_{d}=t+1\right]}{\Pr\left[S_{d}=t\right]}\leq\frac{\Pr\left[S_{d}=t\right]}{\Pr\left[S_{d}=t-1\right]}\;.$

###### Proof.

We define the sets
$A_{t}=\left\\{(a_{1},\ldots,a_{d})\in\mathbb{N}_{0}^{d}\;\middle|\;\sum_{i=1}^{d}a_{i}=t\right\\}$
and get that

$\Pr\left[\sum_{i=1}^{d}\mathcal{Y}_{i}=t\right]=\sum_{(a_{1},\ldots,a_{d})\in
A_{t}}\prod_{i=1}^{d}\ \alpha_{i}^{a_{i}}(1-\alpha_{i})\;.$

We note that the result it is equivalent to showing that
$\Pr\left[X=t+1\right]\Pr\left[X=t-1\right]\leq\Pr\left[X=t\right]^{2}$ which
in turn is equivalent to

$\sum_{(a,b)\in A_{t+1}\times
A_{t-1}}\prod_{i=1}^{d}\alpha_{i}^{a_{i}+b_{i}}(1-\alpha_{i})^{2}\leq\sum_{(a,b)\in
A_{t}\times A_{t}}\prod_{i=1}^{d}\alpha_{i}^{a_{i}+b_{i}}(1-\alpha_{i})^{2}.$

To see that this latter inequality holds, let $s\in A_{2t}$ and define the map
$g_{s}:\mathbb{N}_{0}^{d}\to\mathbb{N}_{0}$ by $g_{s}(i)=|\\{(a,b)\in
A_{i}\times A_{2t-i}\mid a+b=s\\}|$. We note that $g_{s}(i)>0$ exactly when
$i\in\\{0,1,\dots,2t\\}$. The desired inequality is then equivalent to

$\sum_{s\in A_{2t}}g_{s}(t+1)\prod_{i=1}^{d}\alpha_{i}^{s_{i}}\leq\sum_{s\in
A_{2t}}g_{s}(t)\prod_{i=1}^{d}\alpha_{i}^{s_{i}}.$

We will show that $g_{s}$ is log-concave for each $s\in A_{2t}$. As $g_{s}$ is
clearly symmetric around $i=t$, it will in particular follow that
$g_{s}(t+1)\leq g_{s}(t)$ which then leads to the desired inequality. To show
that $g_{s}$ is log-concave, we note that it is a convolution of log-concave
functions. Indeed, fix $s$ and define for $1\leq j\leq d$, the map
$h_{j}:\mathbb{N}_{0}\to\mathbb{N}_{0}$ by $h_{j}(i)=1$ if $0\leq i\leq s_{j}$
and $h_{j}(i)=0$ otherwise. Then each $h_{j}$ is log-concave, and moreover,
$g_{s}$ is the convolution $g_{s}=h_{1}*\cdots*h_{k}$, i.e.,

$g_{s}(i)=\sum_{\begin{subarray}{c}a\in\mathbb{Z}^{k}\\\
a_{1}+\cdots+a_{d}=i\end{subarray}}\prod_{j=1}^{d}h_{j}(a_{j}).$

It is a standard fact that the convolution of log-concave functions is again
log-concave, and the desired inequality follows. ∎

Now let $\ell_{d}\in\mathbb{N}$ be the minimal integer satisfying that
$\Pr\left[S_{d}=C-1\right]/\Pr\left[S_{d}=C-1-\ell_{d}\right]\geq 2$. Now
combining 3 with the definition of $\ell_{d}$ we get that,

$\displaystyle\Pr\left[S_{d}<C\right]$
$\displaystyle=\sum_{t=1}^{C}\Pr\left[S_{d}=C-t\right]\geq\sum_{t=1}^{\ell_{d}}\Pr\left[S_{d}=C-t\right]\geq\frac{\ell_{d}}{2}\Pr\left[S_{d}=C-1\right]\;,$
$\displaystyle\Pr\left[S_{d}<C\right]$
$\displaystyle=\sum_{t=1}^{C}\Pr\left[S_{d}=C-t\right]\leq\sum_{r=0}^{\lceil{C/\ell_{d}}\rceil}\ell_{d}\Pr\left[S_{d}=C-1-r\ell_{d}\right]$
$\displaystyle\leq\ell_{d}\Pr\left[S_{d}=C-1\right]\sum_{r=0}^{\infty}2^{-r}=2\ell_{d}\Pr\left[S_{d}=C-1\right]\;,$
$\displaystyle\mathbb{E}\left[{(C-S_{d})[S_{d}<C]}\right]$
$\displaystyle=\sum_{t=1}^{C}t\Pr\left[S_{d}=C-t\right]\leq\sum_{r=0}^{\lceil{C/\ell_{d}}\rceil}\left(r\ell_{d}^{2}+\frac{\ell_{d}(\ell_{d}+1)}{2}\right)\Pr\left[S_{d}=C-1-r\ell_{d}\right]$
$\displaystyle\leq\sum_{r=0}^{\lceil{C/\ell_{d}}\rceil}\left(r\ell_{d}^{2}+\frac{\ell_{d}(\ell_{d}+1)}{2}\right)2^{-r}\Pr\left[S_{d}=C-1\right]\leq
4\ell_{d}^{2}\Pr\left[S_{d}=C-1\right]\;,$
$\displaystyle\mathbb{E}\left[{(C-S_{d})[S_{d}<C]}\right]$
$\displaystyle=\sum_{t=1}^{C}t\Pr\left[S_{d}=C-t\right]\geq\sum_{t=1}^{\ell_{d}}t\Pr\left[S_{d}=C-1-t\right]\geq\frac{\ell_{d}^{2}}{4}\Pr\left[S_{d}=C-1\right]\;.$

From this we get that
$\frac{\mathbb{E}\left[{(C-S_{d})[S_{d}<C]}\right]}{8\ell_{d}}\leq
f_{d}\leq\frac{8\mathbb{E}\left[{(C-S_{d})[S_{d}<C]}\right]}{\ell_{d}}$. Now
it is clear that
$\mathbb{E}\left[{(C-S_{d})[S_{d}<C]}\right]\geq\mathbb{E}\left[{(C-S_{k})[S_{k}<C]}\right]$
and we will argue that
$\mathbb{E}\left[{(C-S_{k})[S_{k}<C]}\right]\geq\tfrac{\varepsilon\mu}{2}\geq\tfrac{\varepsilon
C}{4}$. This will imply that $f_{d}\geq\tfrac{\varepsilon C}{32\ell_{d}}$.
Using Theorem 12 we get that $\Pr\left[S_{d}\geq
C-t\right]\geq\frac{\sum_{j\in[m]}\left[{X^{(j)}_{k}\leq
t}\right]}{m}-m^{-1/2+o(1)}$ for all $1\leq t\leq C$ with probability
$1-m^{-\gamma}$, and we know that
$\sum_{t=1}^{C}\frac{\sum_{j\in[m]}\left[{X^{(j)}_{k}\leq
t}\right]}{m}=\varepsilon C$, so fixing such event give us that,

$\displaystyle\mathbb{E}\left[{(C-S_{k})[S_{k}<C]}\right]$
$\displaystyle=\sum_{t=1}^{C}\Pr\left[S_{d}\geq C-t\right]$
$\displaystyle\geq\sum_{t=1}^{C}\left(\frac{\sum_{j\in[m]}\left[{X^{(j)}_{k}\leq
t}\right]}{m}-m^{-1/2+o(1)}\right)$ $\displaystyle=\varepsilon\mu-
Cm^{-1/2+o(1)}$ $\displaystyle\geq\tfrac{\varepsilon C}{2}-Cm^{-1/2+o(1)}$
$\displaystyle\geq\tfrac{\varepsilon C}{4}\;.$

Here we have used that $\varepsilon\leq 1$ and that $1/\varepsilon=m^{o(1)}$.

Now we just need to upper bound $\ell_{d}$. By 3 we get that
$\ell_{d}\leq\lceil{\frac{\log(2)}{\log\left(\tfrac{\Pr\left[S_{d}=C\right]}{\Pr\left[S_{d}=C-1\right]}\right)}}\rceil$
so we want to lower bound
$\frac{\Pr\left[S_{d}=C\right]}{\Pr\left[S_{d}=C-1\right]}$. To do this we
will define exponentially tilted variables $(V_{i})_{1\leq i\leq d}$. Let
$\lambda\in\mathbb{R}$ satisfying $\mathbb{E}[e^{\lambda S_{d}}]<\infty$ be a
parameter which will be determined later. We define $V_{i}$ by
$\Pr\left[V_{i}=t\right]=\frac{\Pr\left[\mathcal{Y}_{i}=t\right]e^{\lambda
t}}{\mathbb{E}\left[{e^{\lambda\mathcal{Y}_{i}}}\right]}$ for $1\leq i\leq d$.
Clearly, this is well-defined since
$\sum_{t=0}^{\infty}\Pr\left[\mathcal{Y}_{i}=t\right]e^{\lambda
t}=\mathbb{E}\left[{e^{\lambda\mathcal{Y}_{i}}}\right]$. As pointed out in
[AAKT21], each $V_{i}$ is also geometric random variables (with parameter
$\alpha_{i}e^{\lambda}$) and,

$\displaystyle\Pr\left[S_{d}=C-t\right]=\frac{\mathbb{E}\left[{e^{\lambda\sum_{i=1}^{d}\mathcal{Y}_{i}}}\right]}{e^{\lambda
C}}e^{\lambda t}\Pr\left[\sum_{i=1}^{d}V_{i}=C-t\right].$ (23)

for all integers $t$. Moreover, there is a unique $\lambda$ maximizing
$\lambda
C-\log\mathbb{E}\left[{e^{\lambda\sum_{i=1}^{d}\mathcal{Y}_{i}}}\right]$, and
with this choice of $\lambda$, it holds that
$\sum_{i=1}^{d}\mathbb{E}\left[{V_{i}}\right]=C$. It is easy to see that
$\lambda<0$ since $\beta>0$. We start by noticing that
$\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]\geq\sum_{i=1}^{d}\mathbb{E}\left[{V_{i}}\right]=C$,
and that
$\mathbb{E}\left[{\left|{V_{i}-\mathbb{E}\left[{V_{i}}\right]}\right|^{3}}\right]\leq
25\mathbb{E}\left[{V_{i}}\right]$ by the same reasoning that gave us that
$\mathbb{E}\left[{\left|{\mathcal{Y}_{i}-\mu_{i}}\right|^{3}}\right]\leq
25\mathbb{E}\left[{\mathcal{Y}_{i}}\right]$ since $V_{i}$ is geometrically
distributed with parameter $\alpha_{i}e^{\lambda}<\alpha_{i}$.

We will also need the following lemma by Aamand et al. [AAKT21]. We state a
simplified version of their lemma which covers our use case.

######  Lemma 19.

Let $X_{1},\ldots,X_{d}$ be independent geometric distributed random variables
with $\operatorname*{Var}\left[{X_{i}}\right]=\sigma_{i}^{2}>0$ and
$\mathbb{E}\left[{\left|{X_{i}-\mathbb{E}\left[{X_{i}}\right]}\right|^{3}}\right]=\rho_{i}<\infty$,
and let $\sigma^{2}=\sum_{i=1}^{d}\sigma_{i}^{2}$. Then for every $t$ where
$\mu+t\sigma$ is an integer,

$\displaystyle\left|{\Pr\left[X=\mu+t\sigma\right]-\frac{1}{\sqrt{2\pi}\sigma}e^{-t^{2}/2}}\right|\leq
K_{2}\left(\frac{\sum_{i=1}^{d}\rho_{i}}{\sigma^{3}}\right)^{2}\;.$

where $K_{2}$ is a universal constant.

We will also need the following claim. The proof is bit technical so we defer
the proof till the end of the section.

######  Claim 4.

If $\beta\geq C$ then,

$\displaystyle\frac{\Pr\left[S_{d}=C\right]}{\Pr\left[S_{d}=C-1\right]}\geq
e^{1/8}\;,$

and if $\beta<C$ then,

$\displaystyle\frac{\Pr\left[S_{d}=C\right]}{\Pr\left[S_{d}=C-1\right]}\geq
e^{\tfrac{1}{8}\beta/C}\;,$

and

$\displaystyle\frac{\Pr\left[S_{d}=C-1\right]}{\Pr\left[S_{d}=C-1-\tfrac{1}{2}\lceil{\tfrac{C}{\beta}}\rceil\right]}<2\;.$

If $\beta\geq\tfrac{1}{4}C$ then using 4 we get that
$\ell_{d}\leq\lceil{32\log(2)}\rceil$ which implies that
$f_{d}\geq\frac{\varepsilon C}{32\lceil{32\log(2)}\rceil}\geq L\varepsilon C$.
So now we just need to focus on the case where $\beta<\tfrac{1}{4}C$. We use 4
to get that $\ell_{d}\leq\lceil{8\log(2)\tfrac{C}{\beta}}\rceil\leq
7\tfrac{C}{\beta}$ which implies that $f_{d}\geq\frac{\varepsilon\beta}{224}$.

We now just need to lower bound $\beta$. From 4 we know that
$\ell_{d}>\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil\geq\tfrac{C}{4\beta}>1$,
so $\Pr\left[S_{d}=C\right]\leq\Pr\left[S_{d}=C-1\right]/2$ and we get that
$\mathbb{E}\left[{(C-S_{d})[S_{d}<C]}\right]\geq\frac{\ell_{d}^{2}}{8}\Pr\left[S_{d}=C\right]$.
We will argue that $\mathbb{E}\left[{(C-S_{d})[S_{d}<C]}\right]\leq
2\varepsilon C$. Using Theorem 12 we get that $\Pr\left[S_{d}\geq
C-t\right]\leq\frac{\sum_{j\in[m]}\left[{X^{(j)}_{k}\leq
t}\right]}{m}+m^{-1/2+o(1)}$ for all $1\leq t\leq C$ with probability
$1-m^{-\gamma}$, and we know that
$\sum_{t=1}^{C}\frac{\sum_{j\in[m]}\left[{X^{(j)}_{k}\leq
t}\right]}{m}=\varepsilon C$, so fixing such event give us that,

$\displaystyle\mathbb{E}\left[{(C-S_{k})[S_{k}<C]}\right]$
$\displaystyle=\sum_{t=1}^{C}\Pr\left[S_{d}\geq C-t\right]$
$\displaystyle\leq\sum_{t=1}^{C}\left(\frac{\sum_{j\in[m]}\left[{X^{(j)}_{k}\leq
t}\right]}{m}+m^{-1/2+o(1)}\right)$
$\displaystyle=\varepsilon\mu+Cm^{-1/2+o(1)}$ $\displaystyle\leq\varepsilon
C-Cm^{-1/2+o(1)}$ $\displaystyle\leq 2\varepsilon C\;.$

Here we have used that $1/\varepsilon=m^{o(1)}$. Combing it all we have that,

$\displaystyle\Pr\left[S_{d}=C\right]\leq 16\frac{\varepsilon
C}{\ell_{d}^{2}}\leq 256\frac{\varepsilon\beta^{2}}{C}\;.$

We will now prove that

$\displaystyle\Pr\left[X=C\right]\geq\frac{\exp\left(-\tfrac{\beta^{2}}{C}\right)}{4\sqrt{C}}\;.$
(24)

This will lead to the desired result. Indeed, combining with the bounds above,
we then obtain that

$\frac{\exp\left(-\tfrac{\beta^{2}}{C}\right)}{\sqrt{C}}\leq\frac{\varepsilon\beta^{2}}{1024C}\;,$

or $\Delta e^{\Delta}\geq\frac{1}{1024\varepsilon\sqrt{C}}$, where we have put
$\Delta=\beta^{2}/C$. Then
$\Delta\geq\tfrac{1}{1024}\log\left(\frac{1}{\varepsilon\sqrt{C}}\right)$, so
that
$\beta\geq\tfrac{1}{32}\sqrt{C\log\left(\frac{1}{\varepsilon\sqrt{C}}\right)}$,
and finally

$f_{d}=\Pr\left[S_{d}<C\right]\geq\tfrac{1}{32}\varepsilon\sqrt{C\log\left(\frac{1}{\varepsilon\sqrt{C}}\right)}\geq
L\varepsilon\sqrt{C\log\left(\frac{1}{\varepsilon\sqrt{C}}\right)}\;,$

as desired.

We thus turn to prove Eq. 24. By Eq. 23 we have that,

$\displaystyle\Pr\left[S_{d}=C\right]=\frac{\mathbb{E}\left[{e^{\lambda\sum_{i=1}^{d}\mathcal{Y}_{i}}}\right]}{e^{\lambda
C}}\Pr\left[\sum_{i\in[k]}V_{i}=C\right]\;.$ (25)

We start by focusing on bounding $\lambda
C-\log\mathbb{E}\left[{e^{\lambda\sum_{i=1}^{d}\mathcal{Y}_{i}}}\right]$.
First write
$\psi_{d}(p)=\log\mathbb{E}\left[{e^{p\sum_{i=1}^{d}\mathcal{Y}_{i}}}\right]$
and define the function $g_{d}(t)=\sup_{p}(pt-\psi_{d}(p))$ which is the
Fenchel-Legendre transform of $\psi_{d}(p)$. By our choice of $\lambda$,
$g_{d}(C)=\lambda
C-\log\mathbb{E}\left[{e^{\lambda\sum_{i=1}^{d}\mathcal{Y}_{i}}}\right]$. It
is easy to check that $g_{d}(C+\beta)=0$ and $g_{d}^{\prime}(C+\beta)=0$, and
a standard result on the Fenchel-Legendre transformations is that
$g_{d}^{\prime\prime}(t)=\frac{1}{\psi_{d}^{\prime\prime}(p_{d}(t))}$ where
$p_{d}(t)$ is the unique number such that
$g_{d}(t)=p_{d}(t)t-\psi_{d}(p_{d}(t))$. Now by Taylor’s expansion formula we
have that

$\displaystyle g_{d}(C)\leq\left(\sup_{C\leq t\leq
C+\beta}g_{d}^{\prime\prime}(t)\right)\frac{\beta^{2}}{2}=\left(\frac{1}{\inf_{C\leq
t\leq C+\beta}\psi_{d}^{\prime\prime}(p_{d}(t))}\right)\frac{\beta^{2}}{2}$
(26)

We have that
$\psi_{d}^{\prime}(p)=\sum_{i=1}^{d}\frac{\mathbb{E}\left[{\mathcal{Y}_{i}e^{pY_{i}}}\right]}{\mathbb{E}\left[{e^{p\mathcal{Y}_{i}}}\right]}$
and

$\displaystyle\psi_{d}^{\prime\prime}(p)=\sum_{i=1}^{d}\left(\frac{\mathbb{E}\left[{\mathcal{Y}_{i}^{2}e^{p\mathcal{Y}_{i}}}\right]}{\mathbb{E}\left[{e^{p\mathcal{Y}_{i}}}\right]}-\left(\frac{\mathbb{E}\left[{\mathcal{Y}_{i}e^{p\mathcal{Y}_{i}}}\right]}{\mathbb{E}\left[{e^{p\mathcal{Y}_{i}}}\right]}\right)^{2}\right)\geq\sum_{i=1}^{d}\frac{\mathbb{E}\left[{\mathcal{Y}_{i}e^{p\mathcal{Y}_{i}}}\right]}{\mathbb{E}\left[{e^{p\mathcal{Y}_{i}}}\right]}=\psi_{d}^{\prime}(p).$

Now, $p_{d}(t)\geq\lambda$ when $C\leq t\leq C+\beta$. This implies that
$\psi_{d}^{\prime\prime}(p(t))\geq\psi_{d}^{\prime}(\lambda)=C$ when $C\leq
t\leq C+\beta$. Combining this with Eq. 25 and Eq. 26 we get that

$\displaystyle\Pr\left[S_{d}=C\right]\geq
e^{-\tfrac{\beta^{2}}{2C}}\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]\geq
e^{-\tfrac{\beta^{2}}{C}}\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]\;.$ (27)

To complete the proof of Eq. 24, it thus suffices to show that
$\Pr\left[\sum_{i\in[k]}V_{i}=C\right]=\tfrac{1}{4\sqrt{C}}$. We use Lemma 19
to get that,

$\displaystyle\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]\geq\frac{1}{\sqrt{2\pi\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]}}-K_{2}\left(\frac{\sum_{i=1}^{d}\mathbb{E}\left[{\left|{V_{i}-\mathbb{E}\left[{V_{i}}\right]}\right|^{3}}\right]}{\left(\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]\right)^{3/2}}\right)^{2}$

Now we use that
$\mathbb{E}\left[{V_{i}}\right]\leq\operatorname*{Var}\left[{V_{i}}\right]\leq
2\mathbb{E}\left[{V_{i}}\right]$,
$\left|{V_{i}-\mathbb{E}\left[{V_{i}}\right]}\right|^{3}\leq
25\mathbb{E}\left[{V_{i}}\right]$, and
$\sum_{i=1}^{d}\mathbb{E}\left[{V_{i}}\right]=C$ to get that,

$\displaystyle\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]\geq\frac{1}{\sqrt{4\pi
C}}-25^{2}K_{2}\frac{1}{C^{2}}$

We know that $C\geq\tfrac{1}{4L}$ so if we choose $L$ sufficiently small we
get that,

$\displaystyle\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]\geq\frac{1}{4\sqrt{C}}\;.$

This leads to the desired bound.

We finish the section by proving 4.

###### Proof of 4.

We start by using Eq. 23 to get that,

$\displaystyle\frac{\Pr\left[S_{d}=C\right]}{\Pr\left[S_{d}=C-1\right]}=e^{-\lambda}\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}$

We want to argue that
$\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}\geq\max\left\\{e^{-1/8},e^{-\tfrac{1}{8}\beta/C}\right\\}$.
First we use Lemma 19 to get that,

$\displaystyle\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}\geq\frac{\tfrac{1}{\sqrt{2\pi\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]}}-K_{2}\left(\tfrac{\sum_{i=1}^{d}\mathbb{E}\left[{\left|{V_{i}-\mathbb{E}\left[{V_{i}}\right]}\right|^{3}}\right]}{\left(\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]\right)^{3/2}}\right)^{2}}{\tfrac{1}{\sqrt{2\pi\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]}}e^{-1/(2\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right])}+K_{2}\left(\tfrac{\sum_{i=1}^{d}\mathbb{E}\left[{\left|{V_{i}-\mathbb{E}\left[{V_{i}}\right]}\right|^{3}}\right]}{\left(\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]\right)^{3/2}}\right)^{2}}$

Now we use that
$\mathbb{E}\left[{V_{i}}\right]\leq\operatorname*{Var}\left[{V_{i}}\right]\leq
2\mathbb{E}\left[{V_{i}}\right]$,
$\left|{V_{i}-\mathbb{E}\left[{V_{i}}\right]}\right|^{3}\leq
25\mathbb{E}\left[{V_{i}}\right]$, and
$\sum_{i=1}^{d}\mathbb{E}\left[{V_{i}}\right]=C$ to get that,

$\displaystyle\frac{\tfrac{1}{\sqrt{2\pi\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]}}-K_{2}\left(\tfrac{\sum_{i=1}^{d}\mathbb{E}\left[{\left|{V_{i}-\mathbb{E}\left[{V_{i}}\right]}\right|^{3}}\right]}{\left(\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]\right)^{3/2}}\right)^{2}}{\tfrac{1}{\sqrt{2\pi\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]}}e^{-1/(2\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right])}+K_{2}\left(\tfrac{\sum_{i=1}^{d}\mathbb{E}\left[{\left|{V_{i}-\mathbb{E}\left[{V_{i}}\right]}\right|^{3}}\right]}{\left(\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]\right)^{3/2}}\right)^{2}}\geq\frac{1-25^{2}K_{2}\sqrt{8\pi\tfrac{1}{C}}}{e^{-1/(4C)}+25^{2}K_{2}\sqrt{8\pi\tfrac{1}{C}}}$

Using that $e^{-1/(4c)}\leq 1-\tfrac{1}{8c}$ we the get that,

$\displaystyle\frac{1-25^{2}K_{2}\sqrt{8\pi\tfrac{1}{C}}}{e^{-1/(4C)}+25^{2}K_{2}\sqrt{8\pi\tfrac{1}{C}}}\geq\frac{1-25^{2}K_{2}\sqrt{8\pi\tfrac{1}{C}}}{1-\tfrac{1}{8c}+25^{2}K_{2}\sqrt{8\pi\tfrac{1}{C}}}=1-\frac{2\cdot
25^{2}K_{2}\sqrt{8\pi\tfrac{1}{C}}-\tfrac{1}{8c}}{1-\tfrac{1}{8c}+25^{2}K_{2}\sqrt{8\pi\tfrac{1}{C}}}$

We now that $C\geq\tfrac{1}{4L}$ so choosing $L$ sufficiently small it holds
that

$\displaystyle\frac{2\cdot
25^{2}K_{2}\sqrt{8\pi\tfrac{1}{C}}-\tfrac{1}{8c}}{1-\tfrac{1}{8c}+25^{2}K_{2}\sqrt{8\pi\tfrac{1}{C}}}\leq\frac{2\cdot
25^{2}K_{2}\sqrt{8\pi}}{\sqrt{C}}$

This implies that,

$\displaystyle\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}\geq
1-\frac{2\cdot 25^{2}K_{2}\sqrt{8\pi}}{\sqrt{C}}$

Clearly, $1-\frac{2\cdot 25^{2}K_{2}\sqrt{8\pi}}{\sqrt{C}}\geq e^{-1/8}$ by
choosing $L$ small enough. We also note that,

$\displaystyle 1-\frac{2\cdot 25^{2}K_{2}\sqrt{8\pi}}{\sqrt{C}}\geq
e^{-\tfrac{4\cdot 25^{2}K_{2}\sqrt{8\pi}}{\sqrt{C}}}\geq
e^{-\tfrac{M}{8\sqrt{C}}}\geq e^{-\tfrac{\beta}{8C}}\;.$

By choosing $M$ large enough. The last inequality follows since $\beta\geq
M\sqrt{C}$.

We now have to bound $\lambda$. We define the function

$h(x)=\sum_{i=1}^{d}\alpha_{i}e^{x}(1-\alpha_{i}e^{x})^{-1}\;.$

We note that
$h(0)=\sum_{i=1}^{d}\mathbb{E}\left[{\mathcal{Y}_{i}}\right]=C+\beta$. We take
the derivative of $h$ twice and get that,

$\displaystyle h^{\prime}(x)$
$\displaystyle=\sum_{i=1}^{d}\alpha_{i}e^{x}(1-\alpha_{i}e^{x})^{-2}$
$\displaystyle h^{\prime\prime}(x)$
$\displaystyle=\sum_{i=1}^{d}ae^{x}(1+e^{x})(1-\alpha_{i}e^{x})^{-3}$

We note that $h^{\prime}(x)\geq 0$ and $h^{\prime\prime}(x)\geq 0$ for all $x$
so $h$ is a monotonically increasing convex function, and
$h^{\prime}(0)=\sum_{i=1}^{d}\operatorname*{Var}\left[{\mathcal{Y}_{i}}\right]\leq\sum_{i=1}^{d}2\mu_{i}=2(C+\beta)$.

If $\beta\geq C$ then again using that $h$ is convex we get that,

$\displaystyle h(-\tfrac{1}{4})$ $\displaystyle\geq
h(0)-\tfrac{1}{4}h^{\prime}(0)\geq C+\beta-2\tfrac{1}{4}(C+\beta)\geq C\;.$

Since $h$ is increasing then it implies that $\lambda\leq-\tfrac{1}{4}$ and we
get that,

$\displaystyle\frac{\Pr\left[S_{d}=C\right]}{\Pr\left[S_{d}=C-1\right]}=e^{-\lambda}\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}\geq\
e^{\tfrac{1}{4}}e^{-\tfrac{1}{8}}=e^{-\tfrac{1}{8}}\;.$

If $\beta<C$ then using that $h$ is convex we get that,

$\displaystyle h(-\tfrac{1}{4}\beta/C)$ $\displaystyle\geq
h(0)-\tfrac{1}{4}\beta/Ch^{\prime}(0)\geq
C+\beta-2\tfrac{1}{4}\beta/C(C+\beta)$
$\displaystyle=C+(1-2\tfrac{1}{4}-2\tfrac{1}{4}\beta/C)\beta\geq
C+(1-4\tfrac{1}{4})\beta\geq C\;.$

Since $h$ is increasing then it implies that $\lambda\leq-\tfrac{1}{4}\beta/C$
and we get that,

$\displaystyle\frac{\Pr\left[S_{d}=C\right]}{\Pr\left[S_{d}=C-1\right]}=e^{-\lambda}\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}\geq
e^{\tfrac{1}{4}\beta/C}e^{-\tfrac{1}{8}\beta/C}=e^{\tfrac{1}{8}\beta/C}\;.$

We now focus on the upper bound. We use Eq. 23 to get that,

$\displaystyle\frac{\Pr\left[S_{d}=C-1\right]}{\Pr\left[S_{d}=C-1-\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil\right]}=e^{-\lambda\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil}\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1-\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil\right]}$

We start by lower bounding $\lambda$. We first note that $h^{\prime}(x)\leq
h(x)$ for all $x$. Using that $h$ is convex we get that,

$\displaystyle C+\beta=h(0)\geq
h(-\beta/C)+\beta/Ch^{\prime}(-\beta/C)\geq\frac{C+\beta}{C}h(-\beta/C)\;.$

This implies that $h(-\beta/C)\leq C$ and $\lambda\geq-\beta/C$. Now we will
bound
$\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1-\lceil{\tfrac{C}{\beta}}\rceil\right]}$.
We will again use Lemma 19.

$\displaystyle\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1-\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil\right]}$
$\displaystyle\leq\frac{\tfrac{1}{\sqrt{2\pi\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]}}e^{-1/(2\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right])}+K_{2}\left(\tfrac{\sum_{i=1}^{d}\mathbb{E}\left[{\left|{V_{i}-\mathbb{E}\left[{V_{i}}\right]}\right|^{3}}\right]}{\left(\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]\right)^{3/2}}\right)^{2}}{\tfrac{1}{\sqrt{2\pi\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]}}e^{-(1+\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil)^{2}/(2\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right])}-K_{2}\left(\tfrac{\sum_{i=1}^{d}\mathbb{E}\left[{\left|{V_{i}-\mathbb{E}\left[{V_{i}}\right]}\right|^{3}}\right]}{\left(\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right]\right)^{3/2}}\right)^{2}}$
$\displaystyle\leq\frac{\tfrac{1}{\sqrt{2\pi
C}}e^{-1/(2\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right])}+25^{2}K_{2}\tfrac{1}{C}}{\tfrac{1}{\sqrt{2\pi
C}}e^{-(1+\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil)^{2}/(2\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right])}-25^{2}K_{2}\tfrac{1}{C}}$

Now we note that since $\beta\geq M\sqrt{C}$ then we get that
$(1+\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil)^{2}/(2\sum_{i=1}^{d}\operatorname*{Var}\left[{V_{i}}\right])\leq\tfrac{1}{12}$.
We then get that,

$\displaystyle\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1-\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil\right]}$
$\displaystyle\leq\frac{\tfrac{1}{\sqrt{2\pi
C}}+25^{2}K_{2}\tfrac{1}{C}}{\tfrac{1}{\sqrt{2\pi
C}}e^{-1/12}-25^{2}K_{2}\tfrac{1}{C}}\leq e^{1/6}$

The last inequality follows by $C\geq\tfrac{1}{4L}$ and choosing $L$ small
enough. We then get that,

$\displaystyle\frac{\Pr\left[S_{d}=C-1\right]}{\Pr\left[S_{d}=C-1-\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil\right]}$
$\displaystyle=e^{-\lambda\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil}\frac{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1\right]}{\Pr\left[\sum_{i=1}^{d}V_{i}=C-1-\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil\right]}$
$\displaystyle\leq
e^{\tfrac{\beta}{C}\tfrac{1}{4}\lceil{\tfrac{C}{\beta}}\rceil}e^{1/6}$
$\displaystyle\leq e^{1/2+1/6}$ $\displaystyle<2$

∎

##  6 The Number of Bins Visited During an Insertion

This section is dedicated to proving the part of Theorem 3 concerning
insertions, which we restate below.

######  Theorem 20.

Let $n,m\in\mathbb{N}$ and $0<\varepsilon<1$ with $1/\varepsilon=n^{o(1)}$.
Let $C=(1+\varepsilon)n/m$. Suppose we insert $n$ balls into $m$ bins, each of
capacity $C$, using consistent hashing with bounded loads and virtual bins
having $k$ levels where $k=c/\varepsilon^{2}$ for $c$ a sufficiently large
universal constant. The expected number of bins visited during an insertion of
a ball is $O(1/f)$.

In fact, the proof uses only that the total number of non-full bins is
$\Theta(f)$ with high probability, not the concrete value of $f$. Therefore
the complicated expression for $f$ will never occur in the proof of the
theorem. All we will occasionally use is the fact that the number of non-full
bins is $\Omega(\varepsilon)$, which follows trivially from a combinatorial
argument.

The section is structured as follows: We start by providing some preliminaries
for the proof of Theorem 20 in Section 6.1. In Section 6.2, we use the results
from Section 5 to provide a strengthening of Lemma 11. Finally, we provide the
proof of Theorem 20 in Section 6.3.

###  6.1 Preliminaries For the Analysis

We start by making the following definition which will be repeatedly be useful
in the analysis to follow.

######  Definition 2.

Consider any distribution of $n$ balls into $m$ bins. We say that a bin is
_close to full_ if it contains more than $(1+\varepsilon/2)n/m$ balls.
Otherwise, we say that it is _far from full_.

Suppose we distribute $n$ balls into $m$ bins each of capacity
$C=(1+\varepsilon)n/m$ using consistent hashing with bounded loads and virtual
bins. By Theorem 4, the number of non-full bins is $\Theta(fm)$ with high
probability when $k=O(1/\varepsilon^{2})$ is sufficiently large. We claim that
it also holds that the number of far from full bins is $\Theta(fm)$ with high
probability. To see this, suppose that after distributing the $n$ balls into
the $m$ bins of capacity $C=(1+\varepsilon)n/m$ each, we reduce the capacity
of each bin to $C_{0}=(1+\varepsilon/2)n/m$. This requires forwarding balls
from the now overflowing bins and this forwarding can only increase the number
of bins containing $(1+\varepsilon/2)n/m$ balls. By Theorem 4, and with
$\varepsilon_{0}=\varepsilon/2$, the number of non-full bins after the
relocating is $\Theta(f_{0}m)$, where

$f_{0}=\begin{cases}\varepsilon_{0}C_{0},&C_{0}\leq\log(1/\varepsilon_{0})\\\
\varepsilon_{0}\sqrt{C_{0}\log\left(\frac{1}{\varepsilon_{0}\sqrt{C}_{0}}\right)},&\log(1/\varepsilon_{0})<C_{0}\leq\frac{1}{2\varepsilon_{0}^{2}}\\\
1,&\frac{1}{2\varepsilon_{0}^{2}}\leq C_{0}.\end{cases}$

But clearly, $f_{0}=\Theta(f)$, so we conclude that the number of far from
full bins before modifying the system is $\Theta(fm)$ with high probability.

Summing up, we have the following corollary to Theorem 4.

######  Corollary 21.

In the setting of Theorem 20, the number of far from full bins is $\Theta(fm)$
with high probability, i.e., with probability $1-n^{-\gamma}$ for every
$\gamma$=O(1).

Finally, recall Definition 1: The _run_ at a given level $i$ containing some
virtual bin $b$, is the maximal interval at level $i$ which contains $b$ and
satisfies that all bins lying in $I$ gets full at level $i$.

###  6.2 High Probability Bound on the Number of Bins Visited in an Insertion

This section will be dedicated to prove the following strengthening of Lemma
11.

######  Theorem 22.

Let $n,m\in\mathbb{N}$ and $0<\varepsilon<1$ with $1/\varepsilon=n^{o(1)}$.
Suppose we distribute $n$ balls into $m$ bins, each of capacity
$C=(1+\varepsilon)n/m$, using consistent hashing with bounded loads and
virtual bins and $k=c/\varepsilon^{2}$ levels for a sufficiently large
constant $c$. Let $b$ be a bin at level $i$ which may be chosen dependently on
the hashing of balls and bins to level $1,\dots,i-1$ and $I$ the run at level
$I$ containing $b$. Let $X$ denote the number of bins in $I$. For any $t\geq
1/f$,

$\Pr[X\geq t]=\exp(-\Omega(tf))+O(n^{-10})$

The same statement holds even if $b$ is given an extra start load of $\lambda
tf\lceil C\varepsilon/2\rceil$ ’artificial’ balls before the hashing of balls
and bins to level $i$, where $\lambda$ is a sufficiently small constant.

Note that it in particular follows that the number of bins visited at a given
level during an insertion is $O(\log(1/\delta)/f)$ with probability
$1-\delta$.

###### Proof.

Let $R$ denote the number of virtual bins in $I$. By Corollary 21, the number
of far from full bins after inserting balls at level $1,\dots,i-1$ is at least
$c_{0}fm$ with high probability, where $c_{0}>0$ is some universal constant.
Furthermore, by a standard Chernoff bound, the number of balls hashing to
level $i$ is at most $2n/k$ with high probability. Here we used the assumption
that $1/\varepsilon=n^{o(1)}$, so $n\gg k\log n$. Condition on those two
events and consider the following modified process at level $i$ where (1) $b$
and every bin which was close to full after inserting the balls at level
$1,\dots,i-1$ forwards every ball it receives at level $i$, i.e., has its
remaining capacity reduced to zero (2) each far from full bin stores at most
$\lceil C\varepsilon/2\rceil$ balls from level $i$ before it starts forwarding
balls at level $i$, i.e., has its remaining capacity reduced to $\lceil
C\varepsilon/2\rceil$. Let $I^{\prime}$ denote the run containing $b$ with
such modified capacities. Letting $R^{\prime}$ denote the number of virtual
bins lying in $I$ it then holds that $R\leq R^{\prime}$, so it suffices to
provide a high probability upper bound on $R^{\prime}$.

Let $s\in\mathbb{N}$ be given and let $A_{s}$ be the event that $s+1\leq
R^{\prime}\leq 2s+1$. Define $J_{1}^{-}$ and $J_{1}^{+}$ to be respectively
the intervals at level $i$ ending and starting at $b$ and having length
$s/(4m)$. Similarly, let $J_{2}^{-}$ and $J_{2}^{+}$ be respectively the
intervals at level $i$ ending and starting at $b$ and having length $4s/m$. We
observe that if $A_{s}$ occur then either of the following events must hold.

  * $B_{1}$:

$J_{2}^{-}$ or $J_{2}^{+}$ contains at most $3s$ virtual bins.

  * $B_{2}$:

$J_{1}^{-}$ or $J_{1}^{+}$ contains at least $s/2$ virtual bins

  * $B_{3}$:

$J_{1}^{-}$ or $J_{1}^{+}$ contains at most $c_{0}fs/8$ virtual bins which
were far from full from levels $1,\dots,i-1$

  * $B_{4}$:

$J_{2}^{-}\cup J_{2}^{+}$ contains at least $\lceil C\varepsilon/2\rceil\cdot
c_{0}fs/8$ balls.

Indeed, suppose that $A_{s}$ occur and that neither of $B_{1},B_{2},B_{3}$
occur. We show that then $B_{4}$ must occur. To see this observe that if
$B_{1}$ does not occur, then since $I^{\prime}$ consists of at most $2s+1$
bins, $I^{\prime}\subseteq J_{2}^{-}\cup J_{2}^{+}$. Since $B_{2}$ does not
occur, $I^{\prime}$ must further fully contain $J_{1}^{-}$ or $J_{1}^{+}$.
Since $B_{3}$ does not occur, $I^{\prime}$ must then contain at least
$c_{0}fs/8$ virtual bins which were far from full from levels $1,\dots,i-1$.
Finally any ball allocated to a bin of $I^{\prime}$ must also hash to
$I^{\prime}$. Since the at least $c_{0}fs/8$ far from full bins from level
$1,\dots,i-1$ which lie in $I^{\prime}$ each get full at level $i$ and has a
total capacity of $\lceil C\varepsilon/2\rceil\cdot c_{0}fs/8$, it follows
that at least $\lceil C\varepsilon/2\rceil\cdot c_{0}fs/8$ balls must hash to
$I^{\prime}\subseteq J_{2}^{-}\cup J_{2}^{+}$. This is exactly the event
$B_{4}$.

As in the proof of Lemma 11, we can use standard Chernoff bounds to conclude
that $\Pr[B_{1}]=\exp(-\Omega(s))$, $\Pr[B_{2}]=\exp(-\Omega(s))$ and
$\Pr[B_{3}]=\exp(-\Omega(fs))$. For $B_{4}$, we observe that the expected
number of balls, $\mu$, hashing to $J_{2}^{-}\cup J_{2}^{+}$ is upper bounded
by $2n/k\cdot 8s/m=O(Cs/k)$. As $f=\Omega(\varepsilon)$, we may assume that
$k\geq c^{\prime}/(\varepsilon f)$ for any constant $c^{\prime}$. Thus,
choosing $c^{\prime}$ sufficiently large, it follows that $\mu\leq
Cs\varepsilon fc_{0}/32$. Using another Chernoff bound, it follows
$\Pr[B_{4}]=\exp(-\Omega(fs))$. In conclusion, if $s\geq 1/f$, it holds that
$\Pr[A_{s}]=\exp(-\Omega(fs))$ and the desired result follows as in the proof
of Lemma 11.

Finally, it is easy to modify the constants in the above argument, so that it
carries through even when $b$ is given an extra start load of $\lambda
tf\lceil C\varepsilon/2\rceil$ balls for a sufficiently small constant
$\lambda$, and this gives the final statement of the Theorem. ∎

###  6.3 The Proof of Theorem 20

In this section, we provide the proof of Theorem 20. In order to do so, we
first require a technical lemma which for a given virtual bin, $b$, bounds the
number of balls that are either placed in $b$ or forwarded from $b$ at level
$i$. The technique used to prove this lemma will be used for the final proof
of Theorem 20, but in a more sophisticated way. As such, the lemma below
serves as a nice warm up to the proof of Theorem 20. We start out by choosing
$s^{*}=O(\log n/f)$ sufficiently large, such that Theorem 22 yields that for a
bin $b$ at level $i$, the length of the run containing $b$ at level $i$ (see
Definition 1) has length at most $s^{*}$ with probability $1-1/n^{10}$.

######  Lemma 23.

Let $\lambda=O(1)$ be any constant. Let $b$ be a virtual bin at level $i$ that
may depend on the distribution of balls into bins at level $1,\dots,i-1$. Let
$n_{i}$ denote the number of balls hashing to level $i$ and suppose that
$n/(2k)\leq n_{i}\leq 2n/k$ where $k=O(1/\varepsilon^{2})$ is sufficiently
large (depending on $\lambda$). Let $Z$ denote the number of the $n_{i}$ balls
hashing to level $i$ that either are placed in $b$ or are forwarded from $b$.
Define $\alpha=\lceil C\varepsilon/2\rceil$. For any $\ell\geq 1/5$ satisfying
that $\alpha\ell$ is an integer666The constant $5$ is arbitrary., it holds
that

$\Pr[Z\geq\alpha\ell]\leq e^{-\lambda\ell}+1/n^{10}.$

###### Proof.

We define $A_{\ell}$ to be the event that $Z\geq\alpha\ell$. When upper
bounding the probability of $A_{\ell}$ we may assume that every bin which was
close to full at level $i-1$ forwards all balls landing in it at level $i$. We
may further assume that any bin which was far from full at level $i-1$ stores
exactly $\alpha=\lceil C\varepsilon/2\rceil$ balls and then starts forwarding
balls. Let $Z^{\prime}$ denote the number of balls landing in $b$ or being
forwarded from $b$ at level $i$ in this modified process. Then clearly,
$Z^{\prime}\geq Z$ so $\Pr[Z\geq\alpha\ell]\leq\Pr[Z^{\prime}\geq\alpha\ell]$.

Figure 1: $s$ bins that are far from full and $\alpha s+\alpha\ell$ balls. The
bins are represented as boxes and the balls as disks.

Next note that if $Z^{\prime}\geq\alpha\ell$, then there must an integer
$s\geq 0$ and an interval of the $i$’th level ending in $b$ which contains
exactly $s$ virtual bins which are far from full and exactly $\alpha
s+\alpha\ell$ balls. See Figure 1. Indeed, of the $\ell$ balls landing or
being forwarded from $b$ consider the one hashing furthest behind $b$ at level
$i$, call it $x$. Let $s$ be the the number of far from full bins hashing
between $x$ and $b$ at level $i$. Aside from the $\alpha\ell$ balls landing in
$b$ or being forwarded from $b$, there must hash enough balls between $x$ and
$s$ to put $\alpha$ balls in each of the far from full bins between $x$ and
$b$, and thus the interval between $x$ and $b$ contains exactly $s$ far from
full bins and $\alpha s+\alpha\ell$ balls. We denote the event that there
exists such an interval by $A_{\ell,s}$ noting that we may then upper bound
$\Pr[A_{\ell}]\leq\sum_{s=0}^{s^{*}}\Pr[A_{\ell,s}]+1/n^{10}$. Here we used
that the run containing $b$ has length at most $s^{*}$ with probability at
least $1-1/n^{2}$. We proceed to upper bound $\Pr[A_{\ell,s}]$ for each $0\leq
s\leq s^{*}$.

Figure 2: We generate the number of balls hashing directly between $b_{i}$ and
$b_{i+1}$ sequentially. In each step the number of such balls is dominated by
a geometric distribution with parameter $q$.

So fix $s\geq 0$. We generate the sequence of the $s+1$ far from full bins
$b=b_{0},b_{1},\dots,b_{s+1}$ leading up to $b$ and the balls hashing between
them in a backwards order. Starting at $b_{0}$ we go backwards along the
cyclic order. At some point we reach a bin, $b_{1}$ and we let $X_{0}$ be the
number of balls met along the way in the between $b_{0}$ and $b_{1}$. We
continue this was, going backwards until we have met $s+1$ bins
$b_{1},\dots,b_{s+1}$ and for each $1\leq i\leq s$ we let $X_{i}$ be the
number of balls met in the cyclic order between $b_{i}$ and $b_{i+1}$. See
Figure 2 for an illustration of the process. Let $f$ denote the fraction of
bins which were far from full from level $1,\dots,i-1$. As we saw after
Definition 2, $f\geq\varepsilon/3$. Now when going backwards from $b_{i}$
until we get to $b_{i+1}$, the probability of meeting a ball in each step is
upper bounded by $\frac{n_{i}}{n_{i}+mf-s}\leq\frac{n_{i}}{n_{i}+mf-s^{*}}:=q$
regardless of the values of $X_{0},\dots,X_{i-1}$. Letting
$X_{0}^{\prime},\dots,X_{s}^{\prime}$ be independent geometric variables with
parameter $1-q$, $X=\sum_{i=0}^{s}X_{i}$, and
$X^{\prime}=\sum_{i=0}^{s}X_{i}^{\prime}$ it follows tht for any $t>0$,
$\Pr[X\geq t]\leq\Pr[X^{\prime}\geq t]$.

If $A_{\ell,s}$ holds, then $X\geq s\alpha+\ell\alpha$, so we may upper bound

$\Pr[A_{\ell,s}]\leq\Pr[X^{\prime}\geq s\alpha+\ell\alpha].$

The expected value of $X_{i}^{\prime}$ is

$\mathbb{E}[X_{i}^{\prime}]=\frac{q}{1-q}=\frac{n_{i}}{mf-s^{*}}=O\left(\frac{n}{kmf}\right)=O\left(\frac{\alpha}{kf\varepsilon}\right)\leq\frac{\alpha}{\lambda_{0}}.$

Here $\lambda_{0}=O(1)$ is a sufficiently large constant which we will choose
later. Here we again used the assumption that $1/\varepsilon=m^{o(1)}$ and
moreover that $k=O(1/\varepsilon^{2})$ is sufficiently large. It follows that
$\mathbb{E}[X^{\prime}]=\frac{(s+1)\alpha}{\lambda_{0}}$. Note in particular
that we can ensure that
$\mathbb{E}[X^{\prime}]\leq\frac{s\alpha+\ell\alpha}{2}$, so that

$\Pr[X^{\prime}\geq
s\alpha+\ell\alpha]\leq\Pr\left[X^{\prime}\geq\mathbb{E}[X^{\prime}]+\frac{s\alpha+\ell\alpha}{2}\right].$

We apply Theorem 10 to bound this quantity. If we are in the case, where we
are to use the second bound of Eq. 10, we obtain that

$\Pr\left[X^{\prime}\geq\mathbb{E}[X^{\prime}]+\frac{s\alpha+\ell\alpha}{2}\right]\leq\left(1-\frac{1}{1+2\alpha/\lambda_{0}}\right)^{\frac{s\alpha+\ell\alpha}{4}},$

It is easy to check that
$\left(1-\tfrac{1}{1+2\alpha/\lambda_{0}}\right)^{\alpha}$ can be made smaller
than any sufficiently small constant, just by choosing $\lambda_{0}$
sufficiently large. Thus it follows that

$\displaystyle\Pr[X^{\prime}\geq s\alpha+\ell\alpha]\leq
e^{-\lambda_{1}(s+\ell)},$ (28)

where we can make $\lambda_{1}=O(1)$ sufficiently large. However, we may have
to use the first bound of Eq. 10 and we investigate now which bound we obtain
in this case. Relating back to Theorem 10, we define
$\mu_{0}=\mathbb{E}[X_{i}^{\prime}]\leq\alpha/\lambda_{0}$,
$A=\left(1+\tfrac{1}{2\mu_{0}}\right)\log\left(1+\tfrac{1}{2\mu_{0}}\right)$
and $t=\frac{1}{4\sigma^{2}}\frac{s\alpha+\ell\alpha}{2}$. We further define
$\sigma^{2}=\operatorname*{Var}[X^{\prime}]=(s+1)\operatorname*{Var}[X_{i}^{\prime}]=(s+1)\mu_{0}(1+\mu_{0})$.
If $\mu_{0}\geq 1$, then $A\leq 1/\mu_{0}$ and
$\sigma^{2}\leq(s+1)2\mu_{0}^{2}$, so that

$A\sigma^{2}\leq
2(s+1)\mu_{0}\leq\frac{2(s+1)\alpha}{\lambda_{0}}<\frac{s\alpha+\ell\alpha}{8}=t\sigma^{2},$

by choosing $\lambda_{0}$ large enough. Thus, in this case we obtain the bound
in Eq. 28. If on the other hand $\mu_{0}<1$, then

$t\geq\frac{s\alpha+\ell\alpha}{16(s+1)\mu_{0}}\geq\frac{\lambda_{0}(s+\ell)}{16(s+1)}\geq\lambda_{2}$

for a sufficiently large constant $\lambda_{2}$. Then also $W_{0}(t)$ can be
made larger than any given constant, so we obtain that the bound of Eq. 28
holds in general.

We now sum over $s$ to obtain that

$\Pr[A_{\ell}]\leq 1/n^{10}+\sum_{s=0}^{s^{*}}\Pr[A_{\ell,s}]\leq
1/n^{10}+\sum_{s=0}^{s^{*}}e^{-\lambda_{1}(s+\ell)}\leq
1/n^{10}+e^{-\lambda\ell},$

where again $\lambda$ can be made sufficiently large. This completes the
proof. ∎

With this lemma in hand we are ready to proceed with the proof of Theorem 20.
To guide the reader, we will start by providing a high level idea of how to
obtain the result as follows. First of all, it will be helpful to recall in
details how an insertion of a ball is handled using consistent hashing with
bounded loads and virtual bins. When inserting a ball, $x$, we uniformly hash
$x$ to a random point at a random level. Suppose that the hash value of $x$,
$h(x)$, lies in the $i$’th level $i$ for some $i$. Starting at $h(x)$ we walk
along level $i$ until we arrive at a virtual bin. If the virtual bin is filled
to its capacity with balls hashing to level $1,\dots,i$, we forward a ball
from that bin at level $i$ (it could be $x$ but it could also be another ball
that hashed to level $i$ of lower priority than $x$). We repeat the step,
continuing to walk along level $i$ until we meet a new virtual bin. The first
time we meet a virtual bin, $b$, which was not filled to its capacity with
balls hashing to level $1,\dots,i$, we insert the forwarded ball and find the
smallest level $j>i$ such that the virtual bin of $b$ at level $j$ received a
ball at level $j$. If no such level exists, the insertion is completed.
Otherwise $b$ has an overflow of one ball at level $j$, and we continue the
insertion walking along level $j$ starting at $b$. Theorem 20 claims that the
expected number of bins visited during this entire process is upper bounded by
$O(1/f)$.

The idea of in our proof of Theorem 20 is to split the bins visited during the
insertion of $x$ into  _epochs_. An epoch starts by visiting $\lceil
1/f\rceil$ virtual bins of the insertion (unless of course the insertion is
completed before that many bins has been seen). The last of these $\lceil
1/f\rceil$ virtual bins lies at some level $i$ and we finish the epoch by
completing the forwarding of balls needed at level $i$. At this point, we are
either done with the insertion or we need to forward a ball from some virtual
bin at some level $j>i$. The next epochs are similar; having finished epoch
$a-1$, in epoch $a$, we visit $\lceil 1/f\rceil$ virtual bins. At this point,
we will be at some level $\ell$ if we are not already done with the insertion.
We then finish the part of the insertion which takes place at level $\ell$.
Importantly, at the beginning of each epoch, we have just arrived at a virtual
bin at a completely fresh level.

The proof shows that during the first $\lceil 1/f\rceil$ steps of an epoch,
the probability of finishing the insertion in each step is $1-\Omega(f)$. The
intuition for this, is that when we reach a bin $b$ at some level, $i$, the
probability that $b$ is far from full from other levels than $i$ can be showed
to be $\Omega(f)$. Since the number of levels $k=O(1/\varepsilon^{2})$ is
large, the contribution from level $i$ to $b$ only fills $b$ with probability
$1-\Omega(1)$. Thus, the probability of not finishing the insertion during the
first $\lceil 1/f\rceil$ steps of an epoch is $(1-\Omega(f))^{\lceil
1/f\rceil}=e^{-\Omega(1)}=1-\Omega(1)$. Now conditioning on not finishing the
insertion during the first $\lceil 1/f\rceil$ steps of an epoch, we can still
show that the expected number of bins visited during the rest of the epoch is
$O(1/f)$. Letting $\mathcal{E}$ denote the event of finishing the insertion
during the first $\lceil 1/f\rceil$ of an epoch and $T$, the total number of
bins visited during the insertion, we have on a very high level that

$\displaystyle\mathbb{E}[T]\leq\Pr[\mathcal{E}]\lceil
1/f\rceil+\Pr[\mathcal{E}^{c}](O(1/f)+\mathbb{E}[T])=O(1/f)+\Pr[\mathcal{E}^{c}]\mathbb{E}[T]=O(1/f)+p\mathbb{E}[T],$
(29)

where $p=1-\Omega(1)$. Solving this equation, we find that
$\mathbb{E}[T]=O(1/f)$. Here it should be noted that the recursive formula
(29) is a bit too simplified. In our analysis, the $\mathbb{E}[T]$ on the left
hand side and on the right hand side of (29) will not exactly be the same. The
point is that after finishing epoch $a$, and being ready to start epoch $a+1$
at a new level $j$, we will know a bit more about the hashing of balls to
level $1,\dots,j-1$ than we did before the beginning of epoch $a$. However,
using Lemma 22, we know that it is only a relatively small fraction of the
system that we have any information about, and so we can argue that the
expectation does not change much.

With this intuition in mind, our next goal is to obtain Theorem 20.

###### Proof of Theorem 20.

As described above, we partition the insertion into _epochs_ where an epoch
consists of the following two steps.

  1. 1.

We go through $\lceil 1/f\rceil$ bins of the insertion ending in a bin at some
level $\ell$.

  2. 2.

We continue the insertion at level $\ell$ until we arrive at some bin $b$
which does not get full at level $\ell$.

After step $2.$ we will have to continue the insertion on some level $j>i$ (if
$b$ gets full at that level). Note that the insertion will complete during an
epoch if along the way, we meet a bin which does not get full on either of
levels $1,\dots,k$. We will prove the following more technical claim which
implies Theorem 20.

######  Claim 5.

Let $D>0$ be any constant and $0\leq t\leq D\log n$. Condition on the event
that the insertion has been through $t$ epochs so far. Let $\mathcal{E}$
denote the event that we finish the insertion at one of the first $\lceil
1/f\rceil$ bins met during step 1. of epoch $t+1$. Further define $R$ to be
the random variable which counts the number of bins visited during step 2. of
epoch $t+1$ (if the insertion completes before we get to step 2. we put
$R=0$). Then

$\displaystyle\Pr[\mathcal{E}]\geq c,$ (30)

for some universal constant $c>0$ (which does not depend on $D$), and

$\displaystyle\mathbb{E}[R\mid\mathcal{E}^{c}]=O(1/f).$ (31)

Before proving the claim, we argue how the desired result follows. First of
all, choosing $D=2/c$, it follows from (30) that the probability of not
finishing the insertion during the first $D\log n$ epochs is upper bounded by

$(1-c)^{D\log n}\leq\exp(-2\log n)\leq n^{-2}.$

Conditioned on this extremely low probability event, the expected time for the
insertion is crudely and trivially upper bounded by $mk$, but $mkn^{-2}\ll 1$,
so this has no influence on the expected number of bins visited during the
insertion, as we will now formalize. For $1\leq i\leq D\log n$, we let $X_{i}$
denote the expected number of bins visited during the insertion starting from
epoch $i$. If the insertion finishes before epoch $i$, we let $X_{i}=0$. Let
further $\mathcal{E}_{i}$ denote the probability of finishing the insertion
during step 1. of epoch $i$. Finally, let $R_{i}$ denote the number of bins
visited during step 2. of epoch $i$. Then, for any $0\leq i\leq D\log n$, it
holds that

$\mathbb{E}[X_{i}]\leq\Pr[\mathcal{E}_{i}]\cdot\lceil
1/f\rceil+\Pr[\mathcal{E}_{i}^{c}](\mathbb{E}[R_{i}\mid\mathcal{E}_{i}^{c}]+\mathbb{E}[X_{i+1}]).$

By the claim, $\Pr[\mathcal{E}_{i}^{c}]\leq 1-c$ and
$\mathbb{E}[R_{i}\mid\mathcal{E}_{i}^{c}]=O(1/f)$, so we obtain that

$\mathbb{E}[X_{i}]\leq O(1/f)+(1-c)\mathbb{E}[X_{i+1}].$

Solving this recursion, we obtain that

$\mathbb{E}[X_{0}]=O(1/f)+(1-c)^{i}\mathbb{E}[X_{i+1}],$

so putting $i=D\log n$, we obtain that
$\mathbb{E}[X_{0}]=O(1/f)+n^{-2}\cdot\mathbb{E}[X_{C\log n+1}]=O(1/f)$. But
$\mathbb{E}[X_{0}]$ is exactly the expected number of bins visited during an
insertion. It thus suffices to prove the claim which is the main technical
challenge of the proof.

###### Proof of Claim 5.

We split the proof into the proofs of equations (30) and (31).

### Proof of Equation (30)

It suffices to show that for each of the $\lceil 1/f\rceil$ bins visited
during step 1. of the epoch, the probability of ending the insertion at that
bin is $\Omega(f)$. More formally, we let $\mathcal{A}_{i}$ denote the event
that the $i$’th of these bins, $1\leq i\leq\lceil 1/f\rceil$ is still full,
i.e., that we do not end the insertion at the $i$’th bin, and show that
$\Pr\left[\mathcal{A}_{i}\right]\leq(1-\Omega(f))^{i}+im^{-1/2+o(1)}$. The
probability of not completing the insertion during step 1. of the epoch is
then upper bounded by $(1-\Omega(f))^{\lceil 1/f\rceil}+\lceil{1/f}\rceil
m^{-1/2+o(1)}\leq(1-\Omega(f))^{\lceil 1/f\rceil}+o(1)\leq e^{-\Omega(1)}:=c$
which is the desired result. Here we used that $1/f\leq
O(1/\varepsilon)=m^{o(1)}$.

We will condition on $\mathcal{A}_{i-1}$ so start by making the conditioning
more precise by describing exactly how the bins met before the $i$’th bin of
the epoch at the given level received enough ball to make them full. We then
bound the probability of $\mathcal{A}_{i}$ conditioned on this history. So fix
$i$ with $1\leq i\leq\lceil 1/f\rceil$. The conditioning on
$\mathcal{A}_{i-1}$ means that we have already seen $i-1$ full bins during the
epoch. Suppose that the $i$’th bin, call it $b$, is at some level $\ell$. We
then in particular know that the number of bins we have already visited at
level $\ell$ is at most $i-1\leq 1/f$. Let $a\geq 0$ denote the number of bins
already visited on level $\ell$. Going backwards from $b:=b_{a}$, we denote
these bins $b_{a-1},\dots,b_{0}$. Thus $b_{0}$ was the first bin ever visited
at level $\ell$. Note that possibly $b_{a}=b_{0}$. The conditioning
$\mathcal{A}_{i-1}$ especially implies that after level $\ell$, all bins
$b_{0},\dots,b_{a-1}$ got filled. We now describe how these bins got filled at
level $\ell$ as follows (see also Figure 3 for an illustration of the
process). Starting with $j=0$, if the remaining capacity of $b_{0}$ after
levels $1,\dots,\ell-1$ is $C_{0}$, we go backwards until at some point we
have met a set of bins of total remaining capacity $C^{*}$ and exactly
$C^{*}+C_{0}$ balls for some $C^{*}$. After this sequence, we insert a
question mark ?. This sequence of bins and balls describes how $b_{0}$
received its $C_{0}$ balls, and the ? indicates a yet unknown history. We next
go backwards from $b_{1}$ which has remaining capacity $C_{1}$, say. If we
arrive at $b_{0}$ before having seen $C_{1}$ balls get we simply skip past the
history of how $b_{0}$ got fills and continue the process after the ?. If we
obtain the description of how $b_{1}$ got filled at level $\ell$ before
reaching $b_{0}$, there might still be more balls hashing between $b_{0}$ and
$b_{1}$ (but no bins). In this case we insert a question mark, ?, after the
sequence of balls leading up to $b_{1}$. More generally, for $j=1,\dots,a-1$,
we go backwards from $b_{j}$ generating a sequence of balls. Whenever we reach
a bin, we go back to the nearest ? and start generating balls at that point
until we find a new bin or are done with describing the filling of $b_{j}$ —
In the later case we insert a new ?. The ? before bin $b_{0}$ has a special
status. If we ever reach it, and we still require $C_{j}$ balls to be filled,
we go backwards until we have found a set of bins of total remaining capacity
$C^{*}$ and exactly $C^{*}+C_{0}$ balls for some $C^{*}$. It should be
remarked that there is nothing probabilistic going on here. We have simply
explained a way to find the positions of a set of balls and bins which certify
how bins $b_{0},\dots,b_{a-1}$ got filled at level $\ell$. See Figure 3 for an
example of how this description of how bins $b_{0},\dots,b_{a-1}$ got filled
at level $\ell$ can look.

Figure 3: The filling of bins $b_{0},\dots,b_{3}$ at level $\ell$. The bins
are represented as boxes an the numbers within them describes their remaining
capacity at level $\ell$. The balls are represented as disks and the question
marks ? in circles.

We let $\mathcal{O}$ denote the event that bin $b$ receives more than $\lceil
C\varepsilon/2\rceil$ bins from level $\ell$. We also let $\mathcal{N}$ denote
the event that $b$ receives at least $\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)$ balls from the levels different than $\ell$. We then
get that,

$\displaystyle\Pr\left[\mathcal{A}_{i}\right]\leq\Pr\left[\mathcal{A}_{i-1}\wedge\left(\mathcal{O}\vee\mathcal{N}\right)\right]\leq\Pr\left[\mathcal{A}_{i-1}\right]\Pr\left[{\mathcal{O}}\,\middle|\,{\mathcal{A}_{i-1}}\right]+\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge\mathcal{N}\right]\;.$

We will next show that
$\Pr\left[{\mathcal{O}}\,\middle|\,{\mathcal{A}_{i-1}}\right]=p$, where
$p=1-\Omega(1)$, and

$\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge\mathcal{N}\right]\leq\Pr\left[\mathcal{A}_{i-1}\right]\Pr\left[{\mathcal{O}^{c}}\,\middle|\,{\mathcal{A}_{i-1}}\right](1-c_{0}f)+m^{-1/2+o(1)}$

where $c_{0}=\Omega(1)$ is a universal constant. This will then imply that,

$\displaystyle\Pr\left[\mathcal{A}_{i}\right]\leq\Pr\left[\mathcal{A}_{i-1}\right](1-(1-p)c_{0}f)+m^{-1/2+o(1)}\leq(1-(1-p)c_{0}f)^{i}+im^{-1/2+o(1)}\;.$

We again split the proof into two parts.

##### Bounding $\Pr\left[{\mathcal{O}}\,\middle|\,{\mathcal{A}_{i-1}}\right]$:

In the following we will omit the conditioning of $\mathcal{A}_{i-1}$ from the
notation to avoid clutter. We have described how bins $b_{0},\dots,b_{a-1}$
got filled at level $\ell$. This included a tail of balls behind each bin as
well as some positions marked with ?. Let $s+1$ be the number of such ?-marks
including the mark behind bin $b_{0}$. (See Figure 3). Then $s\leq a$. Let
$X_{0}$ denote the number of balls being forwarded to $b_{a}$ from the
backmost ? before $b_{0}$ and let $X_{1},\dots,X_{s}$, denote the number of
balls forwarded to $b_{a}$ from the remaining positions marked with a ?. The
number of balls, $n_{\ell}$ , hashing to level $\ell$ lies between $n/(2k)$
and $2n/k$ with probability $1-O(n^{-10})$ by a standard Chernoff bound.
Moreover, the total number of bins lying in the history described so far is
$s^{*}=O(\frac{\log n}{f})$ with probability $1-O(n^{-10})$, by Lemma 22
including those bins landing before $b_{0}$ in the description. Now
conditioning on this history, for each $1\leq j\leq s$

$\mathbb{E}[X_{j}]\leq\frac{n_{k}}{m-s^{*}}=O(C/k).$

It follows that

$\mathbb{E}\left[\sum_{j=1}^{s}X_{j}\right]=O(sC/k)=O(C/(fk))=O(C/(\varepsilon
k)).$

If, we choose $k=O(1/\varepsilon^{2})$ sufficiently large, it in particular
follows that $\mathbb{E}\left[\sum_{j=1}^{s}X_{j}\right]\leq\lceil
C\varepsilon/2\rceil/20$. Thus, by Markov’s inequality,

$\displaystyle\Pr\left[\sum_{j=1}^{s}X_{j}\geq\lceil
C\varepsilon/2\rceil/2\right]\leq 1/10.$ (32)

Next, we show that $\Pr[X^{*}\geq\lceil C\varepsilon/2\rceil/2]\leq 1/10$.
From this it will follow that, $\Pr[\mathcal{O}]\leq 1/5$ which is what we
need. For bounding this probability, we may use Lemma 23. To get into the
setting of that lemma, we may simply contract the interval of the cyclic order
from the most backwards ? to $b_{a}$ and remove all unresolved ? in between
except for the most backwards one. That the other places marked with ? now
cannot receive any balls only increases the probability that $X^{*}\geq t$ for
any $t$. Now we are exactly in the setting of Lemma 23, which we apply with
$\ell=1/2$ to conclude that if $k=O(1/\varepsilon^{2})$ is sufficiently large,
then

$\Pr[X^{*}\geq\lceil C\varepsilon/2\rceil/2]\leq 1/10.$

The reader may note that as an alternative to the reduction above (contracting
the so far described history of how the bins $b_{0},\dots,b_{a-1}$ received
their balls), we may simply reprove Lemma 23 in this a tiny bit more
complicated setting. The arguments would remain exactly the same.

In conclusion, we have now argued that
$\Pr\left[{\mathcal{O}}\,\middle|\,{\mathcal{A}_{i-1}}\right]\leq 1/5$.

##### Bounding
$\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge\mathcal{N}\right]$:

We start by defining notation which we used in Section 5.1. Let $Y_{i}$ be the
number of balls which land in bin $b$ or which are forwarded by bin $b$ on
level $i$. We define $Y_{<\ell}=\sum_{i<\ell}Y_{i}$ and
$Y_{>\ell}=\sum_{i>\ell}Y_{i}$. With this notation we get that

$\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge\mathcal{N}\right]=\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}+Y_{>\ell}\geq\frac{n}{m}(1+\lceil C\varepsilon/2\rceil)\right]$

We let let $\mathcal{L}_{\ell}$ be the sigma-algebra generated by the random
choices on the first $\ell$ levels, and $A_{d}$ will be the event as defined
in Section 5.1.

We recall the simpler system from Section 5.1 which we will compare to. Let
$\mathcal{Y}_{i}$ be the number of balls which land in bin $b$ or which are
forwarded by bin $b$ on level $i$ in the simpler system. We similarly define
$\mathcal{Y}_{<\ell}=\sum_{i<\ell}\mathcal{Y}_{i}$ and
$\mathcal{Y}_{>\ell}=\sum_{i>\ell}\mathcal{Y}_{i}$.

We will prove that,

$\displaystyle\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}+Y_{>\ell}\geq\frac{n}{m}(1+\lceil C\varepsilon/2\rceil)\right]$ (33)
$\displaystyle\qquad\qquad\qquad\leq\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\right]\Pr\left[\mathcal{Y}_{<\ell}+\mathcal{Y}_{>\ell}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]+m^{-1/2+o(1)}$ (34)

This will imply the result since

$\displaystyle\Pr\left[\mathcal{Y}_{<\ell}+\mathcal{Y}_{>\ell}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]\leq\Pr\left[\sum_{i=1}^{k}\mathcal{Y}_{i}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]$

Now using Theorem 12 we get that
$\Pr\left[\sum_{i=1}^{k}\mathcal{Y}_{i}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]\leq\Pr\left[\sum_{i=1}^{k}Y_{i}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]+m^{-1/2+o(1)}$, and the discussion at the start
of Section 6.1 give us that
$\Pr\left[\sum_{i=1}^{k}Y_{i}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]\leq 1-c_{0}f$. Thus we just need to prove Eq. 33.

We start by noticing that,

$\displaystyle\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<}+Y_{>\ell}\geq\frac{n}{m}(1+\lceil C\varepsilon/2\rceil)\right]$
$\displaystyle\qquad\qquad=\sum_{s=0}^{\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)-1}\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}=s\wedge
Y_{>\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]$
$\displaystyle\qquad\qquad\qquad\qquad+\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}\geq\frac{n}{m}(1+\lceil C\varepsilon/2\rceil)\right]$

We fix $0\leq s\leq\frac{n}{m}(1+\lceil C\varepsilon/2\rceil)-1$ and get that,

$\displaystyle\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}=s\wedge
Y_{>\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]$
$\displaystyle\qquad\qquad\qquad=\mathbb{E}\left[{\left[{\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}=s}\right]\Pr\left[{Y_{>\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s}\,\middle|\,{\mathcal{L}_{l}}\right]}\right]$

Now we use Lemma 17 and get that
$\Pr\left[{Y_{>\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s}\,\middle|\,{\mathcal{L}_{l}}\right]\leq\Pr\left[\mathcal{Y}_{>\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]+k\left[{A_{\ell}^{c}}\right]+(1+2k)m^{-1/2+o(1)}$.
Using this we get that,

$\displaystyle\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}+Y_{>\ell}\geq\frac{n}{m}(1+\lceil C\varepsilon/2\rceil)\right]$
$\displaystyle\qquad\qquad\leq\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}+\mathcal{Y}_{>\ell}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]$
$\displaystyle\qquad\qquad\qquad+\sum_{s=0}^{\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)-1}\mathbb{E}\left[{\left[{\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}=s}\right]\left(k\left[{A_{\ell}^{c}}\right]+(1+2k)m^{-1/2+o(1)}\right)}\right]$

Now we note that,

$\displaystyle\sum_{s=0}^{\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)-1}\mathbb{E}\left[{\left[{\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}=s}\right]\left(k\left[{A_{\ell}^{c}}\right]+(1+2k)m^{-1/2+o(1)}\right)}\right]$
$\displaystyle\leq k\Pr\left[A_{\ell}^{c}\right]+(1+2k)m^{-1/2+o(1)}$
$\displaystyle\leq km^{-\gamma}+(1+2k)m^{-1/2+o(1)}$ $\displaystyle\leq
m^{-1/2+o(1)}$

The second last inequality uses Theorem 12 and last uses that $k=m^{o(1)}$.

We also want to also exchange $Y_{<\ell}$ with $\mathcal{Y}_{<\ell}$ and we
will do this in similar fashion.

$\displaystyle\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}+\mathcal{Y}_{>\ell}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]$
$\displaystyle\qquad\qquad\qquad=\sum_{s=0}^{\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)-1}\Pr\left[\mathcal{Y}_{>\ell}=s\right]\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge\mathcal{Y}_{>\ell}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]$

Again we fix $s$ and get that,

$\displaystyle\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]$
$\displaystyle=\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\right]\Pr\left[{Y_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s}\,\middle|\,{\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}}\right]$
$\displaystyle\leq\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\right]\Pr\left[{Y_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s}\,\middle|\,{\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
A_{\ell-1}}\right]$ $\displaystyle\qquad\qquad+\Pr\left[A_{\ell-1}^{c}\right]$

By Theorem 12 we know that $\Pr\left[A_{\ell-1}^{c}\right]\leq m^{-\gamma}$.
Now similarly to $Y_{<\ell}$ we define $Y_{<\ell}^{(j)}$ to be the number of
balls which lands in $j$ or which are forwarded by bin $j$ on levels before
level $\ell$. We know that $b$ is chosen uniformly from the set
$[m]\setminus\left\\{b_{0},\ldots,b_{a-1}\right\\}$ so if we fix the first
$\ell-1$ then the probability that
$Y_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s$ is equal to

$\displaystyle\frac{\sum_{j\in[m]\setminus\left\\{b_{0},\ldots,b_{a-1}\right\\}}\left[{Y_{<\ell}^{(j)}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s}\right]}{m-a}$

Since we condition on $A_{\ell-1}$ then we have that,

$\displaystyle\left|{\frac{\sum_{j\in[m]}\left[{Y_{<\ell}^{(j)}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s}\right]}{m}-\Pr\left[\mathcal{Y}_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]}\right|\leq
m^{-1/2+o(1)}$

This implies that,

$\displaystyle\left|{\frac{\sum_{j\in[m]\setminus\left\\{b_{0},\ldots,b_{a-1}\right\\}}\left[{Y_{<\ell}^{(j)}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s}\right]}{m-a}-\Pr\left[\mathcal{Y}_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]}\right|\leq\frac{m}{m-a}m^{-1/2+o(1)}+\frac{a}{m-a}$

Now we use Lemma 11 to get that $a\leq O(\log(m)/\varepsilon)=m^{o(1)}$ with
probability $1-m^{-\gamma}$. Here we use that $1/\varepsilon=m^{o(1)}$.
Combining this we get that,

$\displaystyle\Pr\left[{Y_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s}\,\middle|\,{\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
A_{\ell-1}}\right]$
$\displaystyle\qquad\qquad\leq\Pr\left[\mathcal{Y}_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]+\frac{m}{m-m^{o(1)}}m^{-1/2+o(1)}+\frac{m^{o(1)}}{m-m^{o(1)}}+m^{-\gamma}$
$\displaystyle\qquad\qquad\leq\Pr\left[\mathcal{Y}_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]+m^{-1/2+o(1)}$

We then get that,

$\displaystyle\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]$
$\displaystyle=\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\right]\Pr\left[{Y_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s}\,\middle|\,{\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}}\right]$
$\displaystyle\leq\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\right]\left(\Pr\left[\mathcal{Y}_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]+m^{-1/2+o(1)}\right)$
$\displaystyle\qquad\qquad+m^{-\gamma}$
$\displaystyle\leq\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\right]\Pr\left[\mathcal{Y}_{<\ell}\geq\frac{n}{m}(1+\lceil{C\varepsilon/2}\rceil)-s\right]+m^{-1/2+o(1)}$

Using this we get that,

$\displaystyle\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\wedge
Y_{<\ell}+\mathcal{Y}_{>\ell}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]$
$\displaystyle\qquad\qquad\leq\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\right]\Pr\left[\mathcal{Y}_{<\ell}+\mathcal{Y}_{>\ell}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]$
$\displaystyle\qquad\qquad\qquad+\sum_{s=0}^{\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)-1}\Pr\left[\mathcal{Y}_{>\ell}=s\right]m^{-1/2+o(1)}$
$\displaystyle\qquad\qquad\leq\Pr\left[\mathcal{A}_{i-1}\wedge\mathcal{O}^{c}\right]\Pr\left[\mathcal{Y}_{<\ell}+\mathcal{Y}_{>\ell}\geq\frac{n}{m}(1+\lceil
C\varepsilon/2\rceil)\right]+m^{-1/2+o(1)}$

This finishes the proof Eq. 33.

This concludes the proof that equation (30) of the claim holds.

### Proof of Equation (31)

We restate what we have to prove, namely that

$\mathbb{E}[R\mid\mathcal{E}^{c}]=O(1/f),$

Where $R$ is the number of bins visited during step 2. of epoch $t+1$ and
$\mathcal{E}^{c}$ is the event that we did not finish the insertion during
step 1. of epoch $t+1$. Let $b_{0},\dots,b_{a}$ denote the bins that we have
visited so far at the level where we are currently at, call it $\ell$. All
bins $b_{0},\dots,b_{a}$ got filled from levels $1,\dots,\ell$, and as in the
proof of equation (30) of the claim, we may again describe the history of how
the bins $b_{0},\dots,b_{a}$ got filled to their capacity at level $\ell$. See
Figure 4 for an example of such a history.

Figure 4: An example of how the conditioning on $\mathcal{E}^{c}$ might look.
Except for the ? coming before $b_{0}$, the circled ?’s, are parts of the
cyclic order which has not yet been fixed, but which are known to consist
solely of balls. The circled ? appearing before $b_{0}$, which is the yet
unknown history of how many balls $b_{0}$ are to further forward, has a
special role. Indeed, this history does not have to consist solely of balls
but can consist of a run of balls and bins such that all of the bins in the
run gets filled at this level.

Let $s\geq 1/f$. We wish to argue that the conditional probability

$\displaystyle\Pr[R\geq
s\mid\mathcal{E}^{c}]=O(\exp(-\Omega(sf)))+O(n^{-10}).$ (35)

Ignoring the unimportant $O(n^{-10})$ term, it will follow that

$\mathbb{E}[R\mid\mathcal{E}^{c}]\leq 1/f+\sum_{i=0}^{\infty}\Pr[2^{i}/f\leq
R\leq
2^{i+1}/f]2^{i+1}/f=1/f+O\left(\frac{1}{f}\sum_{i=0}^{\infty}\exp(-\Omega(2^{i}))2^{i}\right)=O(1/f).$

and including the $O(n^{-10})$ term in the computation could only increase the
bound with an additive $n^{-8}$, say, as we can here use the trivial bound on
the length of a run of $mk$. Thus, this yields the desired result. For the
bound on $\Pr[s\leq R\leq 2s\mid\mathcal{E}^{c}]$, it clearly suffices to
assume that $s\geq c/f$ where $c=O(1)$ is a sufficiently large constant.

We start by noting that with probability $1-O(n^{-10})$, the number of balls
hashing to level $\ell$ is at most $2n/k$ which we assume to be the case in
what follows. Let $q$ denote the number of places marked with ? between
$b_{0}$ and $b_{a}$ and let $X_{1},\dots,X_{q}$ denote the number of balls
landing at these positions. Then $q\leq a\leq 1/f$. Let $\alpha=\lceil
C\varepsilon/2\rceil$. Let $A$ denote the event that
$X_{1}+\dots+X_{q}\geq\lambda sf\alpha$, where $\lambda=\Omega(1)$ is a
sufficiently small constant to be chosen later. We start by providing an upper
bound on $\Pr[A]$. For this, we let $X=\sum_{i=1}^{q}X_{i}$ and note, like in
the proof of Lemma 23, that for each $i$, $X_{i}$ is dominated by a geometric
variable with parameter $q$ where $q=\frac{n_{\ell}}{m+n_{\ell}}$. Here
$n_{\ell}=2n/k$ is the upper bound on the number of ball hashing to level
$\ell$. Furthermore, this claim holds even conditioning on the values of
$(X_{j})_{j<i}$. Let $s^{\prime}=s\lambda$. Letting $Y_{1},\dots,Y_{1/f}$ be
independent such geometric variables and $Y=\sum_{i=1}^{1/f}Y_{i}$, we can
thus upper bound

$\Pr[A]\leq\Pr[Y\geq s^{\prime}f\alpha].$

Note that

$\mathbb{E}[Y_{i}]\leq\frac{n_{\ell}}{m}\leq\frac{2C}{k}\leq\frac{4\alpha}{\varepsilon
k}$

for $1\leq i\leq 1/f$, so that $\mathbb{E}[Y]\leq\frac{4\alpha}{\varepsilon
fk}\leq\alpha$, were the last inequality follows by assuming that
$k=O(1/\varepsilon^{2})$ is sufficiently large. We may also assume that
$s^{\prime}f$ is larger than a sufficiently large constant, as described
above, so we can upper bound

$\Pr[A]\leq\Pr[Y\geq\mathbb{E}[Y]+s^{\prime}f\alpha/2].$

By applying the bound Eq. 10 of Theorem 10 similarly to how we did in the
proof of Lemma 23 it follows after some calculations that

$\Pr[A]=\exp(-\Omega(sf)).$

Now condition on $A^{c}$ and let us focus on upper bounding $\Pr[R\geq
s\mid\mathcal{E}^{c}\cap A^{c}]$. For this, we apply (22). To get into the
setting of that theorem, we contract the part of the history revealed so far
between the back-most ?-mark before $b_{0}$ and up til and including $b_{a}$
into a single _unified_ bin. By the conditioning on $A^{c}$, this unified bin
comes with an extra start load of at most $\lambda sf\alpha$ balls, where we
can choose $\lambda=\Omega(1)$ to be any sufficiently small constant. Thus,
with the conditioning, we are exactly in the setting to apply Theorem 22, and
we may thus bound

$\Pr[R\geq s\mid\mathcal{E}^{c}\cap A^{c}]=\exp(-\Omega(sf)).$

It follows that

$\Pr[R\geq s\mid\mathcal{E}^{c}]\leq\Pr[A]+\Pr[R\geq s\mid\mathcal{E}^{c}\cap
A^{c}]=\exp(-\Omega(sf)),$

which is the desired. This completes the proof of 5. ∎ As explained before the
proof of 5, this completes the proof of our theorem. ∎

##  7 Insertions of Bins and Deletions of Balls and Bins

In this section, we prove the statements of Theorems 2 and 3 concerning the
deletions of balls and insertions and deletions of bins. Combined with the
results of Sections 2, 6 and 8, this proves the two theorems in full.

##### Deletions of Balls.

By the history independence, a deletion of a ball is symmetric to an
insertion. The bins visited when deleting a ball $x$ are the same as the bins
visited if $x$ had not been in the system and was inserted. Thus, we can upper
bound the expected number of bins visited when deleting a ball by
$O(1/\varepsilon)$ for Theorem 2 and $O(1/f)$ for Theorem 3. This also upper
bounds the number of balls moved in a deletions.

##### Deletions of Bins.

A deletion of a super bin is the same as reinserting the balls lying in that
super bin. We claimed that that the expected cost of deleting a super bin is
$O(C/f)$ in Theorem 3. At first, this may seem completely obvious, since the
cost of inserting a single ball is $O(1/f)$. However, this cost is for
inserting a ball which is selected independently of the random choices of the
hash function. Now, we are looking at the balls placed in a given super bin
$b$, and those are highly dependent on the hash function. However, we do know
that the expected average cost of all balls in the system is $O(1/f)$.
Moreover, all bins are symmetric, so the bin $b$ behaves like a random bin
amongst those in the system. Thanks to our load balancing, the balls are
almost uniformly spread between the bins, so a random ball from a random bin
is almost a uniformly random ball, so a random ball from $b$ has expected cost
$O(1/f)$. There are at most $C$ balls in $b$ them, so the total expected cost
is $O(C/f)$. A similar argument applies in the case of Theorem 2.

##### Insertions of Bins

Again, by the history independence an insertion of a bin is symmetric to its
deletion. The balls that are moved when inserting a bin are thus the same as
if that bin was in the system but was deleted. Thus we can use the result for
deletions of bins to conclude the bound of $O(C/f)$ on the number of balls
moved when inserting a bin. A similar argument applies in the case of Theorem
2.

##  8 Faster Searches Using the Level-Induced Priorities

In this section we make the calculation demonstrating that giving the balls
random priorities, we obtain the better bounds on the number of bins visited
during an insertion as claimed in Theorems 2 and 3. This is not a new idea but
is in fact an old trick [AK74, Knu73]. What we need to do is verify that
applying it, with the particular formula for $f$ in Eq. 4, we obtain the
stated search times. In fact, what we require for the analysis is only the
fact that if two balls hash to different levels, the ball hashing to the lower
level has the highest priority of the two. Within a given level, the
priorities can be arbitrary. This is important for the practical version of
our scheme described in Section 1.3.2 where the priorities are not uniformly
random and independent of the hashing of balls, but where the hashing of the
balls in fact determines the priorities, with higher hash values implying
lower priorities. We start by arguing about the expected number of bins
visited during a search as stated in Theorem 2.

##### Number of Bins Visited During a Search: Theorem 2.

We encourage the reader to recall the setting described in the theorem. Define
$X$ to be the number of bins visited during the search for some ball $x$.
Importantly, if $x$ hashes to level $i$, then all virtual bins visited during
the search of $x$ also lie on level $i$. For $i\in[k]$, we let $A_{i}$ denote
the event that $x$ hashes to level $i$, so that $\Pr[A_{i}]=p_{i}$. By a
standard Chernoff bound, the number of balls hashing to the first $i$ levels
is $np_{\leq i}\pm m^{1/2+o(1)}=np_{\leq i}(1\pm m^{-1/2+o(1)})$, with
probability $1-O(n^{-10})$, say. Here we used that $1/\varepsilon=m^{o(1)}$.
Condition on this event and define $n_{<i}$ to be the number of balls hashing
to the first $i$ levels. Finally letting $\varepsilon_{i}$ be such that that
$(1+\varepsilon_{i})n_{\leq i}/m=C$, we obtain from the part of Theorem 2
concerning insertions (which was proved in Section 2) that
$\mathbb{E}[X_{i}\mid A_{i}]=O\left(1/\varepsilon_{i}\right)$. Moreover,
$\Pr[A_{i}]\leq 2^{-i+1}$ for each $i$. It finally follows from the Chernoff
bound above that $\varepsilon_{i}\geq 1/2^{i}$, and so

$\mathbb{E}[X]=\sum_{i\in[k]}\mathbb{E}[X\mid A_{i}]\Pr[A_{i}]=O(k)=O(\log
1/\varepsilon)$

as desired.

##### Number of Bins Visited During a Search: Theorem 3.

We now perform a similar calculation to the one above, in the more complicated
setting of Theorem 3. Let us for simplicity assume that the number of balls
hashing to each level is exactly $n/k$. It is trivial to later remove this
assumption. We also assume for simplicity that $k\geq 1/\varepsilon^{2}$ is a
power of $2$, $k=2^{a}$ for some $a$. Let
$\ell=\lceil\log(1/\varepsilon)\rceil$ noting that $\ell\leq a$. We partition
$[k]=I_{0}\cup\cdots I_{\ell}$, where
$I_{i}=[2^{a}-2^{a-i-1}]\setminus[2^{a}-2^{a-i}]$ for $0\leq i\leq\ell-1$ and
$I_{\ell}=[2^{a}]\setminus[2^{a}-2^{a-\ell}]$. Let $A_{i}$ be the event that
the given ball to be searched $x$ hashes to some level in $I_{i}$, so that
$\Pr[A_{i}]=2^{-i+1}$ for $0\leq i\leq\ell-1$ and $\Pr[A_{\ell}]=2^{-\ell}$.
For $0\leq i\leq\ell$ we define $n_{\leq i}$ to be the number of balls hashing
to some level in $I_{0}\cup\cdots\cup I_{i}$. Finally, let $\varepsilon_{i}$
be such that $(1+\varepsilon_{i})n_{\leq i}/m=C$ and note that
$\Pr[A_{i}]=\Theta(\varepsilon_{i})$.

We partition $[\ell+1]$ into three sets, $[\ell+1]=J_{1}\cup J_{2}\cup J_{3}$
where

$J_{1}=\\{i\in[\ell+1]:C\leq\log 1/\varepsilon_{i}\\},\quad
I_{2}=\\{i\in[\ell+1]:\log
1/\varepsilon_{i}<C\leq\frac{1}{2\varepsilon_{i}^{2}}\\},\quad\text{and}\quad
I_{3}=\\{i\in[\ell+1]:\frac{1}{2\varepsilon_{i}^{2}}<C\\}.$

It then follows from the part of Theorem 3 dealing with insertions (proved in
Section 6) that

$\mathbb{E}[X]=O\left(\sum_{i\in
I_{1}}\frac{\Pr[A_{i}]}{\varepsilon_{i}C}+\sum_{i\in
I_{2}}\frac{\Pr[A_{i}]}{\varepsilon_{i}\sqrt{C\log\left(\tfrac{1}{\varepsilon_{i}\sqrt{C}}\right)}}+\sum_{i\in
I_{3}}\Pr[A_{i}]\right)=O\left(1+\frac{|I_{1}|}{C}+\sum_{i\in
I_{2}}\frac{1}{\sqrt{C\log\left(\tfrac{1}{\varepsilon_{i}\sqrt{C}}\right)}}\right)$

We have the trivial bound $|I_{1}|\leq\ell+1=O(\log 1/\varepsilon)$. Moreover,
for $i\in I_{2}$, it holds that

$e^{-C}\leq\varepsilon_{i}\leq\sqrt{\frac{1}{2C}},$

and since $\varepsilon_{i}=\Theta(2^{-i})$, it follows that

$\sum_{i\in
I_{2}}\frac{1}{\sqrt{C\log\left(\tfrac{1}{\varepsilon_{i}\sqrt{C}}\right)}}=O\left(\frac{1}{\sqrt{C}}\sum_{i=1}^{O(C)}\frac{1}{\sqrt{i}}\right)=O(1).$

In conclusion,

$\mathbb{E}[X]=O\left(1+\frac{\log 1/\varepsilon}{C}\right),$

and splitting into the cases, $C\leq\log 1/\varepsilon$ and $C<\log
1/\varepsilon$, we obtain the desired result.

##  9 The Practical Implementation.

In this section we sketch why our results continue to holds when using the
practical implementation described in Section 1.3.2 even when the hashing is
implemented using the practical mixed tabulation scheme from [DKRT15]. Let us
call the implementation from Section 1.3.2 the _practical implementation_.

We first discuss the practical implementation with fully random hashing. For
this, recall the definition of a run (Definition 1). Using a similar
argumentation to the one used in the proof of Lemma 11, it is easy to show
that in this implementation, for any constant $\gamma=O(1)$, the maximal
number of bins in a run is $O((\log n)/\varepsilon)$ with probability
$1-n^{-\gamma}$. Denote this high probability event $\mathcal{E}$. The number
of balls lying in a run consisting of $\ell$ bins is trivially upper bounded
by $C(\ell+1)$, so if $\mathcal{E}$ occurs, the maximal number of balls
hashing to a fixed run is $O(C(\log n)/\varepsilon)$. It follows that the
number of balls that are forwarded past any given point is $O(C(\log
n)/\varepsilon)$. In particular for any level $i$, the number of balls that
are forwarded from level $i$ to level $i+1$ is $O(C(\log n)/\varepsilon)$ and
the total number of such balls over all levels is $O(kC(\log
n)/\varepsilon)=m^{o(1)}$. One can now modify our inductive proof of Theorem 4
to check that its statement remains valid even with the influence of these
extra balls. Recall that in Theorem 4, $X_{i,j}$ denoted the number of bins
with at most $j$ balls after the hashing of balls to levels $0,\dots,i-1$.
Intuitively, in the inductive step, these $m^{o(1)}$ extra balls can only
affect $m^{o(1)}$ bins which does not affect the high probability bound
stating that $|X_{i,j}-\mu_{i,j}|\leq m^{1/2+o(1)}$. To exclude the bad event
$\mathcal{E}^{c}$, we simply use a union bound and that $\mathcal{E}$ happened
with very high probability. Once we have a version of Theorem 4 which holds in
the practical implementation, we can repeat the proof of Theorem 20, again
using union bounds for the event that the insertion interacts with the run of
size $m^{o(1)}$ entering the given level from below.

Let us now discuss the implementation with mixed tabulation. A mixed
tabulation hash function $h$ is defined using two of the simple tabulation
hash functions from [PT12], $h_{1}:\Sigma^{c}\to\Sigma^{d}$ and
$h_{2}:\Sigma^{c+d}\to R$. Here $\Sigma$ is some character alphabet with
$\Sigma^{c}=[u]$ and $c,d=O(1)$ are constants. Then for a key $x$,
$h(x)=h_{2}(x,h_{1}(x))$. An important property of mixed tabulation, proved in
[DKRT15], is the following: Suppose $X$ is a set of keys, $p_{1},\dots,p_{b}$
are output bit positions and $v_{1},\dots,v_{b}$ are desired bit values. Let
$Y$ be the set of keys $x\in X$ for which the $p_{i}$’th output bit
$h(x)_{p_{i}}=v_{i}$ for all $i$. If
$\mathbb{E}[|Y|]\leq|\Sigma|/(1+\Omega(1))$, then the remaining output bits of
the hash values in $Y$ are completely independent with probability
$1-O(|\Sigma|^{1-\lfloor{d/2}\rfloor})$. Another important property is that
mixed tabulation obeys the same concentration bounds as simple tabulation on
the number of balls landing in an interval [PT12].

For the implementation with mixed tabulation, we use $k$ independent mixed
tabulation functions, $h_{1},\dots,h_{k}$, to distribute the virtual bins, and
a single mixed tabulation function $h^{*}$ for the balls (independent of
$h_{1},\dots,h_{k}$). We moreover assume that $|\Sigma|=u^{1/c}=n^{\Omega(1)}$
which can be achieved using a standard universe reduction. To obtain our
results using mixed tabulation, the idea is essentially the same as above.
Again, we first need to prove an analogue of Theorem 4, and we would do this
using induction on the level, bounding $|X_{i,j}-\mu_{i,j}|$ with high
probability for each level $i$. To do this, we partition level $i$ into dyadic
intervals where we expect at most $|\Sigma|/2$ balls or bins to hash. Then we
can use the concentration bound from [PT12] (which also holds for mixed
tabulation) to obtain concentration on the number of bins of a given capacity
from the previous levels hashing to each interval. Moreover, we can use the
result of [DKRT15] to conclude that restricted to such an interval the hashing
of balls and bins is fully random. Again, we can prove a version of Lemma 11
with mixed tabulation (by using that mixed tabulation provides concentration
bounds) and conclude that the total number of balls that are forwarded from
one interval to another is $O(C(\log
n)/\varepsilon)=m^{o(1)}=|\Sigma|^{o(1)}$. Essentially, the good distribution
of the $X_{i-1,j}$ ensures that we also obtain a good distribution of the
number of bins with each capacity in each of the intervals of level $i$ (using
that the influence of the $|\Sigma|^{o(1)}$ balls passing between intervals
can only affect $|\Sigma|^{o(1)}$ bins), and this gives a good distribution of
the $X_{i,j}$. For this, it is important to be aware that there are now more
intervals, essentially $n/|\Sigma|$, but since $|\Sigma|=n^{\Omega(1)}$, we
still obtain that the total number of balls that are forwarded from one
interval to another is $n^{1-\Omega(1)}$. The high probability bound we obtain
on $|X_{i,j}-\mu_{i,j}|$ then instead takes the form
$|X_{i,j}-\mu_{i,j}|=n^{1-\Omega(1)}$, but this still suffices for our
purposes. Finally, we may prove a mixed tabulation version of Theorem 20,
again using the fully random hashing within each interval and using union
bounds to bound away the probability that we interact with the
$|\Sigma|^{o(1)}$ balls that are forwarded between intervals. As such, showing
that our results hold using mixed tabulation uses essentially the same ideas
as is needed to show that the implementation in Section 1.3.2 does, but with a
finer partitioning into intervals.

##  10 Modifying the Analysis for Dynamically Changing Capacities

In this last short section, we describe how our analysis can still be carried
through even with the dynamically changing capacities described in Section
1.7. In the preceding sections, we assumed that the capacities of the bins
were all equal to some integer $C$. However, in the setting of Section 1.7 we
are interested in the case where the _total_ capacity is $Cm$, with $m_{1}$
bins of capacity $\lfloor{C}\rfloor$ and $m_{2}$ bins of capacity
$\lceil{C}\rceil$. Thus $C$ is no longer assumed to be integral. This
corresponds to all bins having the same capacity $\lceil{C}\rceil$, but where
we include an extra $-1$’th level, where $m_{1}$ bins each receive a single
artificial ball.

To analyse this new setting one can first observe that the proofs in Section 6
carry through without significant changes. Thus it is mainly in regards to the
bounds on the fraction of non-full bins in Section 5 that there is something
to discuss. Recall, that we showed in Section 5.1 that the contribution of
balls from the levels to a given random bin essentially behaves like a sum of
geometric variables. With the terminology introduced in [AAKT21], geometric
variables are strongly monotone, and we could then apply the bound of that
paper to estimate the point probabilities of this sum. Now Bernoulli variables
are also strongly monotone, and so the bound in [AAKT21] can also be applied
when some of the variables in the sum are Bernoulli. Now with the $-1$’th
level described above, the number of balls landing in a random bin at the new
lowest level is Bernoulli. Then the contribution to a random bin is
essentially a sum of geometric variables and a single Bernoulli variable, and
since the bound in [AAKT21] holds for such a sum, we can still use it for
estimating the point probabilities of the number of balls in a bin. The
remaining parts of the proof carries through almost unchanged.

## Acknowledgement

The authors wish to thank Noga Alon and Nick Wormald for helpful discussions.
With Noga Alon, we studied sums of integer variables [AAKT21], including
bounds needed for the analysis of this paper. In unpublished work on a the
random graph $d$-process, Nick Wormald and Andrzej Ruciński also used the idea
of analyzing balls in capacitated bins by throwing an appropriately larger
number of balls into uncapacitated bins. They did not present an estimate on
the number of non-full bins, as needed for this paper.

Research supported by grant 16582, Basic Algorithms Research Copenhagen
(BARC), from the VILLUM Foundation.

## References

  * [AAKT21] Anders Aamand, Noga Alon, Jakob Bæk Tejs Knudsen, and Mikkel Thorup.  On sums of monotone random integer variables, 2021.
  * [AK74] Ole Amble and Donald E. Knuth.  Ordered hash tables.  Comput. J., 17(2):135–142, 1974.
  * [Azu67] Kazuoki Azuma.  Weighted sums of certain dependent random variables.  Tohoku Mathematical Journal, 19(3):357–367, 1967.
  * [BG07] G. E. Blelloch and D. Golovin.  Strongly history-independent hashing with applications.  In Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS), pages 272–282, 2007.
  * [BSS00] André Brinkmann, Kay Salzwedel, and Christian Scheideler.  Efficient, distributed data placement strategies for storage area networks.  In Proceedings of the Twelfth annual ACM Symposium on Parallel Algorithms and Architectures, SPAA, pages 119–128, 2000.
  * [CDKR02] Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, and Antony IT Rowstron.  Scribe: A large-scale and decentralized application-level multicast infrastructure.  Selected Areas in Communications, IEEE Journal on, 20(8):1489–1499, 2002.
  * [DKRT15] Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, and Mikkel Thorup.  Hashing for statistics over k-partitions.  In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, pages 1292–1310, 2015.
  * [GF04] David A. Grossman and Ophir Frieder.  Information Retrieval - Algorithms and Heuristics, Second Edition, volume 15 of The Kluwer International Series on Information Retrieval.  Kluwer, 2004.
  * [GH05] George Giakkoupis and Vassos Hadzilacos.  A scheme for load balancing in heterogenous distributed hash tables.  In Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC, pages 302–311, 2005.
  * [GM14] Spencer Greenberg and Mehryar Mohri.  Tight lower bound on the probability of a binomial exceeding its expectation.  Statistics & Probability Letters, 86:91–98, 2014.
  * [KLL+97] David R. Karger, Eric Lehman, Frank Thomson Leighton, Rina Panigrahy, Matthew S. Levine, and Daniel Lewin.  Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web.  In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, STOC, pages 654–663, 1997.
  * [KM05] Krishnaram Kenthapadi and Gurmeet Singh Manku.  Decentralized algorithms using both local and random probes for P2P load balancing.  In SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 135–144, 2005.
  * [Knu73] Donald E. Knuth.  The Art of Computer Programming, Volume III: Sorting and Searching.  Addison-Wesley, 1973.
  * [KR06] David R. Karger and Matthias Ruhl.  Simple efficient load-balancing algorithms for peer-to-peer systems.  Theory Comput. Syst., 39(6):787–804, 2006.  Announced at SPAA’05.
  * [Lar88] Per-Åke Larson.  Dynamic hash tables.  Commun. ACM, 31(4):446–457, 1988.
  * [Man04] Gurmeet Singh Manku.  Balanced binary trees for ID management and load balance in distributed hash tables.  In Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC, pages 197–205, 2004.
  * [MTZ18] Vahab S. Mirrokni, Mikkel Thorup, and Morteza Zadimoghaddam.  Consistent hashing with bounded loads.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 587–604. SIAM, 2018\.
  * [MZ17] Vahab Mirrokni and Morteza Zadimoghaddam.  Consistent hashing with bounded loads.  Google Research Blog, April 3, 2017.  https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html.
  * [ÖV11] M. Tamer Özsu and Patrick Valduriez.  Principles of Distributed Database Systems, Third Edition.  Springer, 2011.
  * [PT12] Mihai Pǎtraşcu and Mikkel Thorup.  The power of simple tabulation-based hashing.  Journal of the ACM, 59(3):Article 14, 2012.  See also STOC’11.
  * [RD01] Antony Rowstron and Peter Druschel.  Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems.  In Middleware 2001, pages 329–350. Springer, 2001.
  * [RFH+01] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker.  A scalable content-addressable network, volume 31.  ACM, 2001.
  * [Rod16] Andrew Rodland.  Improving load balancing with a new consistent-hashing algorithm.  Vimeo Engineering Blog, December 19, 2016.  https://medium.com/vimeo-engineering-blog/improving-load-balancing-with-a-new-consistent-hashing-algorithm-9f1bd75709ed.
  * [SMK+01] Ion Stoica, Robert Morris, David Karger, M Frans Kaashoek, and Hari Balakrishnan.  Chord: A scalable peer-to-peer lookup service for internet applications.  ACM SIGCOMM Computer Communication Review, 31(4):149–160, 2001\.
  * [SML+03] Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan.  Chord: a scalable peer-to-peer lookup protocol for internet applications.  IEEE/ACM Trans. Netw., 11(1):17–32, 2003.
  * [TR98] David Thaler and Chinya V. Ravishankar.  Using name-based mappings to increase hit rates.  IEEE/ACM Trans. Netw., 6(1):1–14, 1998.