# Balanced Allocations with Incomplete Information:
The Power of Two Queries

Dimitrios Los<EMAIL_ADDRESS>Thomas Sauerwald
<EMAIL_ADDRESS>The author was supported by the ERC grant
“Dynamic March”. Part of this work was done while visiting Hasso-Plattner
Institute, Potsdam, Germany.

###### Abstract

We consider the allocation of $m$ balls into $n$ bins with incomplete
information. In the classical Two-Choice process a ball first queries the load
of two randomly chosen bins and is then placed in the least loaded bin. In our
setting, each ball also samples two random bins but can only estimate a bin’s
load by sending binary queries of the form “Is the load at least the median?”
or “Is the load at least $100$?”.

For the lightly loaded case $m=\mathcal{O}(n)$, Feldheim and Gurel-Gurevich
(2021) showed that with one query it is possible to achieve a maximum load of
$\mathcal{O}(\sqrt{\log n/\log\log n})$, and they also pose the question
whether a maximum load of $m/n+\mathcal{O}(\sqrt{\log n/\log\log n})$ is
possible for any $m=\Omega(n)$. In this work, we resolve this open problem by
proving a lower bound of $m/n+\Omega(\sqrt{\log n})$ for a fixed
$m=\Theta(n\sqrt{\log n})$, and a lower bound of $m/n+\Omega(\log n/\log\log
n)$ for some $m$ depending on the used strategy.

We complement this negative result by proving a positive result for multiple
queries. In particular, we show that with only two binary queries per chosen
bin, there is an oblivious strategy which ensures a maximum load of
$m/n+\mathcal{O}(\sqrt{\log n})$ for any $m\geqslant 1$. Further, for any
number of $k=\mathcal{O}(\log\log n)$ binary queries, the upper bound on the
maximum load improves to $m/n+\mathcal{O}(k(\log n)^{1/k})$ for any
$m\geqslant 1$.

This result for $k$ queries has several interesting consequences: $(i)$ it
implies new bounds for the $(1+\beta)$-process introduced by Peres, Talwar and
Wieder (2015), $(ii)$ it leads to new bounds for the graphical balanced
allocation process on dense expander graphs, and $(iii)$ it recovers and
generalizes the bound of $m/n+\mathcal{O}(\log\log n)$ on the maximum load
achieved by the Two-Choice process, including the heavily loaded case
$m=\Omega(n)$ which was derived in previous works by Berenbrink, Czumaj,
Steger and Vöcking (2006) as well as Talwar and Wieder (2014).

One novel aspect of our proofs is the use of multiple super-exponential
potential functions, which might be of use in future work.

###### Contents

  1. 1 Introduction
  2. 2 Notation, Definitions and Preliminaries
  3. 3 Basic Relations between Allocation Processes
  4. 4 Lower Bounds for One Quantile and One Threshold
    1. 4.1 Preliminaries for Lower Bounds
    2. 4.2 Lower Bound for a Range of Values (Theorem 4.1)
    3. 4.3 Lower Bound for Fixed $m=\Theta(n\sqrt{\log n})$ (4.2)
  5. 5 Upper Bounds for One Quantile
    1. 5.1 Tools for Theorem 5.3
    2. 5.2 Completing the proof of Theorem 5.3
  6. 6 Upper Bounds for More Than One Quantile
    1. 6.1 Upper Bounds on the Original Quantile Process and Consequences
    2. 6.2 Relaxed Quantile Process and Outline of the Inductive Step
    3. 6.3 Proof Outline of Lemma 6.7.
    4. 6.4 Auxiliary Definitions and Claims for the proof of Lemma 6.7
      1. 6.4.1 Analysis of the Drop of the Potentials $\Phi_{j}$ and $\Psi_{j}$
      2. 6.4.2 Auxiliary Probabilistic Lemmas on the Potential Functions
      3. 6.4.3 Deterministic Relations between the Potential Functions
    5. 6.5 Completing the Proof of Key Lemma (6.7)
    6. 6.6 Proof of Main Theorem (6.1) using 6.7
  7. 7 Applications of the Relaxed Quantile Process
    1. 7.1 $(1+\beta)$-Process for large $\beta$
    2. 7.2 Graphical Balanced Allocation
  8. 8 Conclusions
  9. 9 Experimental Results
  10. A Probabilistic Tools
    1. A.1 Concentration Inequalities
    2. A.2 Majorization Tools
    3. A.3 Facts about the One-Choice Process

##  1 Introduction

We study balls-and-bins processes where the goal is to allocate $m$ balls
(jobs) sequentially into $n$ bins (servers). The balls-and-bins framework
a.k.a. balanced allocations [6] is a very popular and simple framework for
various resource allocation and storage problems such as load balancing,
scheduling or hashing (see surveys [30, 39] for more details). In most of
these settings, the goal is to find a simple allocation strategy that results
in an as balanced allocation as possible.

It is a classical result that if each ball is placed in a random bin chosen
independently and uniformly (called One-Choice), then the maximum load is
$\Theta(\log n/\log\log n)$ w.h.p. 111In general, with high probability refers
to probability of at least $1-n^{-c}$ for some constant $c>0$. for $m=n$, and
$m/n+\Theta(\sqrt{(m/n)\log n})$ w.h.p. for $m\gg n$. Azar et al. [6] (and
implicitly Karp et al. [24]) proved that if each ball is placed in the lesser
loaded of two randomly chosen bins, then the maximum load drops to
$\log_{2}\log n+\mathcal{O}(1)$ w.h.p., if $m=n$. This dramatic improvement of
Two-Choice is widely known as “power of two choices”, and similar ideas have
been applied to other problems including routing, hashing and randomized
rounding [30].

While for $m=n$ a wide range of different proof techniques have been employed,
the heavily loaded case $m\gg n$ turns out to be much more challenging. In a
seminal paper [10], Berenbrink et al. proved a maximum load of
$m/n+\log_{2}\log n+\mathcal{O}(1)$ w.h.p. using a sophisticated Markov chain
analysis. A simpler and more self-contained proof was recently found by Talwar
and Wieder [37], giving a slightly weaker upper bound of $m/n+\log_{2}\log
n+\mathcal{O}(\log\log\log n)$ for the maximum load and at the cost of a
larger error probability.

In light of the dramatic improvement of Two-Choice (or $d$-Choice) over One-
Choice, it is important to understand the robustness of these processes. For
example, in a concurrent environment, information about the load of a bin
might quickly become outdated or communication with bins might be restricted.
Also, acquiring always $d\geqslant 2$ uncorrelated choices might be costly in
practice. Motivated by this, Peres et al. [32] introduced the
$(1+\beta)$-process, in which two choices are available with probability
$\beta$, and otherwise only one. Thus, the $(1+\beta)$-process interpolates
nicely between Two-Choice and One-Choice, and surprisingly, a bound on the gap
between maximum and average load of $\mathcal{O}(\log n/\beta)$ w.h.p. was
shown, which also holds in the heavily loaded case where $m=\Omega(n)$. The
$(1+\beta)$-process has been also connected to other processes, including
population protocols [3], balls-and-bins with weights [36, 37] and, most
notably, graphical balanced allocation [25, 32, 4, 7]. In this graphical
model, bins correspond to vertices of a graph, and for each ball we sample an
edge uniformly at random and place the ball in the lesser loaded bin of the
two endpoints. Also the results and analysis techniques of the
$(1+\beta)$-process have found important connections to population protocols
[3] and balls-and-bins with weights [36, 37].

Our Model. In this work, we will investigate the following model. At each
step, a ball is allowed to sample two random bins chosen independently and
uniformly, however, the load comparison between the two bins will be performed
under incomplete information. This may capture scenarios in which it is costly
to communicate or maintain the exact load of a bin.

Specifically, we assume that each ball is allowed to send up to $k$ binary
queries to each of the two bins, inquiring about their current load. These
queries can either be about the absolute load (i.e., is the load at least
$100$?), which we call threshold processes, or about the relative load (i.e.,
is the load at least the median?), which we call quantile processes.

We will distinguish between oblivious and adaptive allocation strategies. For
an adaptive strategy, the queries may depend on the current load configuration
(i.e., the full history of the process), whereas in the oblivious setting,
queries may depend only on the current time-step.

Our Results. For the case of $k=1$ query, Feldheim and Gurel-Gurevich [18]
proved a bound of $\mathcal{O}(\sqrt{\log n/\log\log n})$ on the gap (between
the maximum and average load) in the lightly loaded case $m=\mathcal{O}(n)$.
In the same work, the authors suggest that the same bound might be also true
in the heavily loaded case [18, Problem 1.3]. In this work, we disprove this
by showing a lower bound of $\Omega(\sqrt{\log n})$ on the gap for
$m=\Theta(n\sqrt{\log n})$ (4.2). We also prove a lower bound of $\Omega(\log
n/\log\log n)$ on the gap, which holds for at least $\Omega(n\log n/\log\log
n)$ of the time-steps in $[1,n\log^{2}n]$ (4.6). These two lower bounds hold
even for the more general class of adaptive strategies. The basic idea behind
all these lower bounds is that, as $m\gg n$, one query is not enough to
prevent the process from emulating the One-Choice process on a small scale.

It is natural to ask whether we can get an improved performance by allowing
more, say two queries per bin. We prove that this is indeed the case,
establishing a “power of two-queries” result. Specifically, we show in 6.1
that for any $k=\mathcal{O}(\log\log n)$, there is an allocation process with
$k$ uniform quantiles (i.e., queries only depend on $n$, but not on the time
$t$) that achieves for any $m\geqslant 1$:

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)=\mathcal{O}\Big{(}k\cdot(\log
n)^{1/k}\Big{)}\,\right]\geqslant 1-n^{-3}.$

Comparing this for $k=2$ to the lower bounds for $k=1$, we indeed observe a
“power of two-queries” effect. For $k=\Theta(\log\log n)$, the gap even
becomes $\mathcal{O}(\log\log n)$, which matches the Two-Choice result up to a
multiplicative constant [10, 37]. Hence, for large values of $k$, the process
approximates Two-Choice, whereas for $k=1$ it resembles the
$(1+\beta)$-process. Indeed, the same upper bound of $\mathcal{O}(\log n)$
follows from the analysis of the $(1+\beta)$-process (5.2).

We also prove new upper bounds on the gap of the $(1+\beta)$ process with
$\beta$ close to $1$ by relating it to a relaxed quantile process (7.1). We
show that these in turn imply new upper bounds on the graphical balanced
allocation on dense expander graphs, making progress towards Open Question 2
in [32] (7.2).

Applications and Implications on other Models. A direct implementation of the
$k$-quantile protocol in practice requires to maintain some _global_
information about the load configuration (that is, the exact, or at least, the
approximate, values of the quantiles). If this can be achieved, then the
results of $k$-quantile for $k\geqslant 2$ demonstrate that a sub-logarithmic
gap is possible – even with very limited _local_ information about the
individual bin loads.

In addition, our study of the $k$-quantile process also leads to new results
for some previously studied allocation processes. We demonstrate that a
$(1+\beta)$-process for $\beta$ close to $1$ is majorized by a (relaxed
version of the) $k$-quantile process. For any $\beta=1-o(1)$, this leads to a
sub-logarithmic bound on the gap, and if $\beta=1-1/\operatorname{poly}(n)$,
we recover the $\mathcal{O}(\log\log n)$ gap from the Two-Choice process.
Secondly, we use a similar majorization argument to analyze graphical balanced
allocation, which has been studied in several works on different graphs [32,
25, 4, 7]. Specifically, we prove for dense and strong expander graphs
(including random $d$-regular graphs for $d=\operatorname{poly}(n)$) a gap of
$\mathcal{O}(\log\log n)$. To the best of our knowledge, these are the first
sub-logarithmic gap bounds in the heavily loaded case for the
$(1+\beta)$-process and graphical balanced allocation (apart from $\beta=1$ or
the graph being a clique, both equivalent to Two-Choice).

Further Related Work. Our model for $k=1$ is equivalent to the $d$-Thinning
process for $d=2$, where for each ball, a random bin is “suggested” and based
on the bin’s load, the ball is either allocated there or it is allocated to a
second bin chosen uniformly and independently. Generalizing the results of
[18] for $d=2$, Feldheim and Li [20] also analyzed an extension of
$2$-Thinning, called $d$-Thinning. For $m=\mathcal{O}(n)$, they proved tight
lower and upper bounds, resulting into an achievable gap of
$(d+o(1))\cdot\left(d\log n/\log\log n\right)^{1/d}$. Iwama and Kawachi [22]
analyzed a special case of the threshold process for $m=n$ and for $k$
equally-spaced thresholds, proving a gap of
$(k+\mathcal{O}(1))\sqrt[k+1]{(k+1)\frac{\log{n}}{\log\left((k+1)\log{n}\right)}}.$
Mitzenmacher [29, Section 5] coined the term weak threshold process for the
two threshold process in a queuing setting, where a customer chooses two
queues uniformly at random and enters the first one iff it is shorter than
$T$. This and previous work [15, 23, 40] analyze the case of a fixed threshold
for queues and they do not directly imply results for the heavily loaded case.

In another related work, Alon et al. [5] established for the case
$m=\Theta(n)$ a trade-off between the number of bits used for the
representation of the load and the number of $d$ bin choices. This is a more
restricted case of having a fixed number of non-adaptive queries. For $d=2$,
Benjamini and Makarychev [8] obtained tight results for the gap, using a
process very similar to the threshold process, but considering the case
$m=\Theta(n)$ only.

Czumaj and Stemann [14] investigated general allocation processes, in which
the decision whether to take a second (or further) sample depends on the load
of the lightest sampled bin. They obtained strong and tight guarantees, but
they assume the full information model and also $m=\mathcal{O}(n)$ (see [11]
for some results for $m\geqslant n$). Other processes with inaccurate (or
outdated) information about the load of a bin have been studied in an
asynchronous environment [2] or a batch-based allocation [9]. However, the
obtained bounds on the gap are only $\mathcal{O}(\log n)$. Other protocols
that study the communication between balls and bins in more detail are [27,
26, 17, 35], but they assume that a ball can sample more than two bins.

After an earlier version of this paper went online, Feldheim, Gurel-Gurevich
and Li [19] extended the lower bounds for $2$-Thinning when
$m=\mathcal{O}(n\log^{2}n)$ and also provided an adaptive thinning process
that matches the $\Omega(\log n/\log\log n)$ lower bound proved in this paper.
Also, Los, Sauerwald and Sylvester [28] proved that $\textsc{Threshold}(m/n)$
achieves w.h.p. a $\Theta(\log n)$ gap.

Organization. This paper is organized as follows. In Section 2, we introduce
our model more formally in addition to some notation used in the analysis. In
Section 4, we present our lower bounds on processes with one query. In Section
5, we present the upper bound for the quantile process with one query. In
Section 6, we present a generalized upper bound for $k\geqslant 2$ queries.
Section 7 contains our applications to $(1+\beta)$-process and graphical
balanced allocations. We close in Section 8 by summarizing our main results
and pointing to some open problems. We also briefly present some experimental
results in Section 9. In Section 3, we formally relate the new quantile (and
threshold) processes to each other and to other processes studied before (see
Fig. 2 for an overview).

##  2 Notation, Definitions and Preliminaries

We sequentially allocate $m$ balls (jobs) into $n$ bins (servers). The load
vector at step $t$ is $x^{(t)}=(x_{1}^{(t)},x_{2}^{(t)},\ldots,x_{n}^{(t)})$
and in the beginning, $x_{i}^{(0)}=0$ for $i\in[n]$. Also
$y^{(t)}=(y_{1}^{(t)},y_{2}^{(t)},\ldots,y_{n}^{(t)})$ will be the permuted
load vector, sorted decreasingly in load. This can be described by ranks,
which form a permutation of $[n]$ that satisfies
$r=\operatorname{Rank}^{(t)}(i)\Rightarrow y_{r}^{(t)}=x_{i}^{(t)}.$ Following
previous work, we analyze allocation processes in terms of the

$\operatorname{Gap}(t):=\max_{1\leqslant i\leqslant
n}x_{i}^{(t)}-\frac{t}{n}=y_{1}^{(t)}-\frac{t}{n},$

i.e., the difference between maximum and average load at time $t\geqslant 0$.
It is well-known that even for Two-Choice, the gap between maximum and minimum
load is $\Omega(\log n)$ for large $m$ (e.g. [32]). Here our focus is on
sequential allocation processes based on binary queries. That is, at each step
$t$:

  1. 1.

Sample two bins independently and uniformly at random (with replacement).

  2. 2.

Send the same $k$ binary queries to each of the two bins about their load.

  3. 3.

Allocate the ball in the lesser loaded one of the two bins (based on the
answers to the queries), breaking ties randomly.

Figure 1: Example allocation using two $3$-threshold processes
$(f_{1},f_{2},f_{3})$. (Left): The ball is allocated in $j_{2}$, since
$i_{1}=2$ and $i_{2}=3$. (Right): For a different choice of thresholds, the
process may not be able to differentiate the two loaded bins, so the ball will
be allocated at random.

We first describe threshold-based processes, where queries to each bin $j$ are
of the type “Is $x_{j}^{(t)}\geqslant f(t)$” for some function $f$ that maps
into $\mathbb{N}$. For example, we could ask whether the load of a bin is at
least the average load. Formally, we denote such a process with two choices
and $k$ queries by $\textsc{Threshold}(f_{1},f_{2},\ldots,f_{k})$, where
$f_{1}>f_{2}>\ldots>f_{k}$ are $k$ different load thresholds, that may depend
on the time $t$, in which case we write $f_{i}(t)$. After sending all $k$
queries to a bin $j$, we receive the correct answers to all these queries and
then we determine the $i$ ($0\leqslant i\leqslant k$) for which,

$x_{j}^{(t)}\in(f_{i+1}(t),f_{i}(t)],$

where $f_{0}(t)=+\infty$ and $f_{k+1}(t)=-\infty$ (see Fig. 1). After having
obtained two such numbers $i_{1},i_{2}\in\\{0,1,\ldots,k\\}$, one for each bin
$j_{1}$ and $j_{2}$, we will allocate the ball “greedily”, i.e., into $j_{1}$
if $i_{1}<i_{2}$ and into $j_{2}$ if $i_{1}>i_{2}$. If $i_{1}=i_{2}$, then we
will break ties randomly.

We proceed to define quantile-based processes. In this process, queries to a
bin $j$ are of the type “Is $x_{j}^{(t)}\geqslant y_{\delta(t)\cdot
n}^{(t)}$?”, for some function $\delta$ that maps $t$ into
$\\{1/n,2/n,\ldots,1\\}$. For example if $\delta=1/2$, we are querying whether
the load of a bin is at most the median load. We denote such a process with
two choices and $k$ queries by
$\textsc{Quantile}(\delta_{1},\delta_{2},\ldots,\delta_{k})$, where
$\delta_{1}<\delta_{2}<\ldots<\delta_{k}$ are $k$ different quantiles, which
may depend on the time $t$. After sending all $k$ queries to a bin $j$ in step
$t$, we receive the correct answers and then we determine the $i$ ($0\leqslant
i\leqslant k$) for which,

$\operatorname{Rank}^{(t)}(j)\in(\delta_{i}(t)\cdot n,\delta_{i+1}(t)\cdot
n],$

where $\delta_{0}(t)=0$ and $\delta_{k+1}(t)=1$. As before, we allocate the
ball to the bin with smaller $i$-value and break ties randomly.

Quantile and Threshold processes can be classified into oblivious processes
and adaptive processes, depending on the type of queries. In an oblivious
process, the queries $f_{1},f_{2},\ldots$ (or $\delta_{1},\delta_{2},\ldots$)
may only depend on $t$ (as well as $n$) —a special case is a uniform process
where $\delta_{1},\delta_{2},\ldots$ are constants (independent of $t$), and
the $f_{i}$’s are of the form $t/n+f_{i}(n)$. In an adaptive process, queries
in step $t$ may depend on the full history of the process, i.e., the load
vector $x^{(t-1)}$, so each query $i$ involves a function $f_{i}(x^{(t-1)})$,
but this must be specified before receiving any answers. In the adaptive
setting, a $k$-quantile process can simulate any $k$-threshold process, by
setting the quantile to the largest $\delta_{i}(t)$ such that
$y_{\delta_{i}(t)\cdot n}\leqslant f_{i}(t)$ (3.7).

The $d$-Thinning process [18] works as follows. For each ball to be allocated,
an overseer can inspect up to $d$ randomly sampled bins in an online fashion,
and based on all previous history, can accept or reject each bin (however, one
of the $d$ proposed bins must be accepted).

The $d$-Choice process [6] (sometimes also called $\textsc{Greedy}[d]$) is the
process where, for each ball, $d$ bins are chosen uniformly at random and the
ball is placed in the least loaded bin. We will refer to the special case
$d=1$ as the One-Choice process, and $d=2$ as the Two-Choice process. The
$(1+\beta)$-process [32] is the process where each ball is placed with
probability $\beta$ according to Two-Choice and with probability $1-\beta$
according to One-Choice.

Finally, in graphical balanced allocation [25, 32], we are given an undirected
graph $G$ with $n$ vertices corresponding to $n$ bins. For each ball to be
allocated, we select an edge $\\{u,v\\}\in E(G)$ uniformly at random, and
place the ball in the lesser loaded bin among $\\{u,v\\}$. As pointed out in
[32], this setting can be generalized even to hypergraphs.

Following [32] and generalizing the processes above, an allocation process can
be described by a probability vector
$p^{(t)}=(p_{1}^{(t)},p_{2}^{(t)},\ldots,p_{n}^{(t)})$ for step $t$, where
$p_{i}^{(t)}$ is the probability for incrementing the load of the $i$-th most
loaded bin. Following the idea of majorization (see Lemma A.5), if two
processes with (time-invariant) probability vectors $p$ and $q$, for all
$i\in[n]$ satisfy $\sum_{j\leqslant i}p_{j}\leqslant\sum_{j\leqslant i}q_{j}$,
then there is a coupling between the allocation processes with sorted load
vectors $y(p)$ and $y(q)$ such that $\sum_{j\leqslant
i}y_{i}^{(t)}(p)\leqslant\sum_{j\leqslant i}y_{i}^{(t)}(q)$ for all $i\in[n]$
($q$ majorizes $p$).

Finally, we define the height of a ball as $i\geqslant 1$ if it is the $i$th
ball added to the bin.

Many statements in this work hold only for sufficiently large $n$, and several
constants are chosen generously with the intention of making it easier to
verify some technical inequalities.

##  3 Basic Relations between Allocation Processes

In this section we collect several basic relations between allocation
processes, following the notion of majorization [32]. Fig. 2 gives a high-
level overview of some of these relations, along the with the derived and
implied gap bounds.

One-Choice $=$ $(1+\beta)$ ($\beta=0$) $=$ Quantile($\delta_{1}=1$)
$\operatorname{Gap}(m)=\Theta\left(\sqrt{\frac{m}{n}\log(n)}\right)$ Two-
Choice $=$ $(1+\beta)$ ($\beta=1$) $=$
Quantile($\frac{1}{n},\frac{2}{n},\ldots,\frac{n-1}{n}$)
$\operatorname{Gap}(m)=\log\log n+\Theta(1)$ $(1+\beta)$ ($\beta=o(1)$)
$\operatorname{Gap}(m)=\Theta\left(\frac{\log n}{\beta}\right)$ $(1+\beta)$
($\beta\in(0,1)$) $\operatorname{Gap}(m)=\Theta\left(\log n\right)$
$(1+\beta)$ ($\beta=1-2^{-0.5(\log n)}$)
$\operatorname{Gap}(m)=\mathcal{O}\left(\sqrt{\log n}\right)$ $(1+\beta)$
($\beta=1-2^{-0.5(\log n)^{2/3}}$)
$\operatorname{Gap}(m)=\mathcal{O}\left((\log n)^{1/3}\right)$ $(1+\beta)$
($\beta=1-\frac{1}{\operatorname{poly}(n)}$)
$\operatorname{Gap}(m)=\Theta(\log\log n)$ Quantile($\delta_{1}$),
$\delta_{1}\in(0,1)$) $=$ $2$-Thinning $\displaystyle\operatorname{Gap}(m)$
$\displaystyle=\mathcal{O}\left(\log n\right)$
$\displaystyle\operatorname{Gap}(m)$ $\displaystyle=\Omega\left(\frac{\log
n}{\log\log n}\right)$ Quantile($2^{-0.5\sqrt{\log n}},2^{-1}$)
$\operatorname{Gap}(m)=\mathcal{O}(\sqrt{\log n})$ Quantile($2^{-0.5(\log
n)^{2/3}},2^{-0.5(\log n)^{1/3}},2^{-1}$)
$\operatorname{Gap}(m)=\mathcal{O}((\log n)^{1/3})$
Quantile($\delta_{1},\ldots,\delta_{\Theta(\log\log n)}$)
$\operatorname{Gap}(m)=\Theta(\log\log n)$ Power of Two ChoicesPower of Two
Queries majorizes majorizes majorizes majorizes increase probability of having
a second choice increase number of binary queries to estimate bin load

Figure 2: Overview of bounds on $\operatorname{Gap}(m)$ for various allocation
processes that interpolate between One-Choice and Two-Choice. All stated upper
bounds are valid for any $m\geqslant 1$, while lower bounds may only hold for
certain ranges of $m$. Some of the majorization results in the figure only
hold for a suitable Relaxed-Quantile process.

Recall that the Two-Choice probability vector is, for $i\in[n]$:

$p_{i}=\frac{2i-1}{n^{2}}.$

The $(1+\beta)$ probability vector [32] interpolates between those of One-
Choice and Two-Choice, so for any $i\in[n]$,

$p_{i}=(1-\beta)\cdot\frac{1}{n}+\beta\cdot\frac{2i-1}{n^{2}}.$

For the process $\textsc{Quantile}{(\delta_{1},\ldots,\delta_{k})}$, it is
straightforward to verify that the probability vector satisfies for any
$i\in[n]$:

$\displaystyle p_{i}=\begin{cases}\frac{\delta_{1}}{n}&1\leqslant
i\leqslant\delta_{1}\cdot n,\\\
\frac{\delta_{1}+\delta_{2}}{n}&\delta_{1}\cdot n<i\leqslant\delta_{2}\cdot
n,\\\ \ \ \ \vdots&\\\ \frac{\delta_{k-1}+\delta_{k}}{n}&\delta_{k-1}\cdot
n<i\leqslant\delta_{k}\cdot n,\\\ \frac{1+\delta_{k}}{n}&\delta_{k}\cdot
n<i.\end{cases}$ (3.1)

The next lemma shows that we can always execute the
$\textsc{Quantile}(\delta)$ in the same way as $2$-Thinning:

######  Lemma 3.1.

Consider a quantile process $\textsc{Quantile}(\delta)$ with one query. This
process can be always transformed into an equivalent instance of $2$-Thinning:
Sample a bin, if its rank is greater than $n\cdot\delta(t)$, then place the
ball there; otherwise, place the ball in a randomly chosen bin.

###### Proof.

Let $p$ be the probability vector of the $\textsc{Quantile}(\delta)$ process
and let $q$ be the probability vector of the $2$-Thinning process described in
the statement of the lemma. We will show that $p=q$. Let $R$ denote the set of
bins with rank $>n\cdot\delta(t)$. Let $B_{1}$ and $B_{2}$ be the two bin
choices at some time step. We consider two cases, based on the rank of bin
$i\in[n]$.

Case 1 (light bin): $i$ has rank $>n\cdot\delta(t)$, then

$\displaystyle p_{i}$
$\displaystyle=\frac{1}{2}\mathbf{Pr}\left[\,B_{1}=i,B_{2}\in
R\,\right]+\frac{1}{2}\mathbf{Pr}\left[\,B_{1}\in R,B_{2}=i\,\right]$
$\displaystyle\quad+\mathbf{Pr}\left[\,B_{1}=i,B_{2}\notin
R\,\right]+\mathbf{Pr}\left[\,B_{1}\notin R,B_{2}=i\,\right]$
$\displaystyle=\left(1-\delta(t)\right)\cdot\frac{1}{n}\cdot\frac{1}{2}\cdot
2+2\cdot\frac{1}{n}\cdot\delta(t)=\frac{\delta(t)+1}{n},$ $\displaystyle
q_{i}$
$\displaystyle=\mathbf{Pr}\left[\,B_{1}=i\,\right]+\mathbf{Pr}\left[\,B_{1}\notin
R,B_{2}=i\,\right]=\frac{1}{n}+\delta(t)\cdot\frac{1}{n}=\frac{\delta(t)+1}{n}.$

Case 2 (heavy bin): $i$ has rank $\leqslant n\cdot\delta(t)$, then

$\displaystyle p_{i}=\frac{1}{2}\mathbf{Pr}\left[\,B_{1}=i,B_{2}\notin
R\,\right]+\frac{1}{2}\mathbf{Pr}\left[\,B_{1}\notin
R,B_{2}=i\,\right]=\frac{1}{2}\cdot
2\cdot\frac{1}{n}\cdot\delta(t)=\frac{\delta(t)}{n},$
$q_{i}=\mathbf{Pr}\left[\,B_{1}\in
R,B_{2}=i\,\right]=\delta(t)\cdot\frac{1}{n}.$

∎

Similarly, for $\textsc{Threshold}{(f)}$ we have:

######  Lemma 3.2.

Consider a threshold process $\textsc{Threshold}(f)$ with one query. This
process can be always transformed into the following equivalent process: For
the first sampled bin $i$, if its load is smaller than $f(t)$, place the ball;
otherwise, place the ball in another randomly chosen bin $j$.

###### Proof.

The proof is similar to the one of 3.1, setting $R$ to be the set of bins with
load less than $f(t)$. ∎

######  Observation 3.3.

For any $n\geqslant 0$, the
$\textsc{Quantile}{(\frac{1}{n},\frac{2}{n}\ldots,\frac{n-1}{n})}$ process is
equivalent to the Two-Choice process.

###### Proof.

The probability vector of the
$\textsc{Quantile}{(\frac{1}{n},\frac{2}{n}\ldots,\frac{n-1}{n})}$ process is
equal to that of Two-Choice, since

$p_{i}=\frac{\delta_{i-1}+\delta_{i}}{n}=\frac{i-1+i}{n^{2}}=\frac{2i-1}{n^{2}},$

where we have used $\delta_{0}=0$ and $\delta_{n}=1$ for convenience. ∎

######  Observation 3.4.

For $k<n-1$, for any $\delta^{\prime},\delta_{1},\ldots,\delta_{k}$ quantiles,
the $\textsc{Quantile}{(\delta_{1},\ldots,\delta_{k})}$ process majorizes
$\textsc{Quantile}{(\delta_{1},\ldots,\delta_{i},\delta^{\prime},\allowbreak\delta_{i+1},\ldots,\delta_{k})}$.

###### Proof.

Consider the
$\textsc{Quantile}{(\delta_{1},\ldots,\delta_{i},\delta^{\prime},\delta_{i+1},\ldots,\delta_{k})}$
process. The additional quantile $\delta^{\prime}$ allows us to distinguish
between pairs of ranks in $(\delta_{i}\cdot n,\delta_{i+1}\cdot n]$, that were
not distinguishable by $\textsc{Quantile}{(\delta_{1},\ldots,\delta_{k})}$.
So, the probability vector of the new process is obtained from the old one by
moving probability mass from the lower part of the probability vector to the
higher part. Hence, majorization follows. ∎

By combining 3.3 and 3.4, we get:

######  Corollary 3.5.

Any $\textsc{Quantile}{(\delta_{1},\ldots,\delta_{k})}$ process majorizes Two-
Choice.

###### Proof.

Given any $\textsc{Quantile}{(\delta_{1},\ldots,\delta_{k})}$, by
incrementally adding the $n-1-k$ missing quantiles of the form $j/n$ for
$j\in[n]$, we obtain a sequence of quantile processes where each process
majorizes the next, by 3.4. The last process is
$\textsc{Quantile}{(\frac{1}{n},\ldots,\frac{n-1}{n})}$ which is Two-Choice,
by 3.3. ∎

######  Lemma 3.6.

For any $\delta\in(0,1)$ and any $\beta\in(0,1)$ with
$\beta\leqslant\delta\leqslant 1-\beta$, the process Quantile$(\delta)$ is
majorized by a $(1+\beta)$-process. In particular, the gap of the quantile
process is stochastically smaller than that of the $(1+\beta)$-process.

Note that for any given $\delta\in(0,1)$, $\beta:=\min\\{\delta,1-\delta\\}$
always satisfies the precondition of the lemma. Conversely, for any given
$\beta\leqslant 1/2$, we have $\beta\leqslant 1/2\leqslant(1-\beta)$, and thus
we can set $\delta:=1/2$.

###### Proof.

Let $p$ be the probability vector for the $\textsc{Quantile}{(\delta)}$ and
$q$ for the $(1+\beta)$-process. Recall that $p_{i}=\frac{\delta}{n}$ for
$1\leqslant i\leqslant n\cdot\delta$ and $p_{i}=\frac{1+\delta}{n}$ for
$n\cdot\delta<i\leqslant n$. The claim will follow immediately once we
establish that: (i) For any $1\leqslant i\leqslant n\cdot\delta$,
$p_{i}\leqslant q_{i}$, (ii) For any $n\cdot\delta<i\leqslant n$,
$p_{i}\geqslant q_{i}$.

For the first inequality, note that using $\delta\leqslant 1-\beta$,

$q_{i}\geqslant(1-\beta)\cdot\frac{1}{n}\geqslant\delta\cdot\frac{1}{n}=p_{i}.$

For the second inequality, we have, using $\beta\leqslant\delta$,

$q_{i}=(1-\beta)\cdot\frac{1}{n}+\beta\cdot\frac{2(i-1)}{n^{2}}\leqslant(1-\beta)\frac{1}{n}+\beta\cdot\frac{2}{n}=\frac{1}{n}+\frac{\beta}{n}\leqslant
p_{i}.$

∎

The majorization results in 3.5 and 3.6 are illustrated in Fig. 3 for $n=10$.

$2$$4$$6$$8$$10$$0$$0.1$$0.2$$0.3$Two-Choice$(1+\beta)$,
$\beta=0.4$$\textsc{Quantile}(0.6)$

$2$$4$$6$$8$$10$$0$$0.2$$0.4$$0.6$$0.8$$1$Two-Choice$(1+\beta)$,
$\beta=0.4$$\textsc{Quantile}(0.6)$

Figure 3: Illustration of the probability vector $(p_{1},p_{2},\ldots,p_{10})$
and cumulative probability distribution of Two-Choice, $(1+\beta)$ with
$\beta=0.4$ and Quantile$(0.6)$, which is sandwiched by the other two
processes.

######  Lemma 3.7.

Any $\textsc{Threshold}(f_{1},\ldots,f_{k})$ process can be simulated by an
adaptive quantile process with $k$ queries.

###### Proof.

Consider an arbitrary time step $t\geqslant 0$. Since the process is adaptive,
we are allowed to determine the value of $\delta_{j}(t)$ by looking at the
load distribution $x^{(t)}$. We want to choose $\delta_{j}(t)$, such that
comparing the rank $i\leqslant\delta_{j}(t)\cdot n$ gives the same answer as
$f_{j}(t)\leqslant x_{i}^{(t)}$ for every $i\in[n]$. This can be achieved by
choosing $\delta_{j}(t)$ to be the largest possible quantile such that
$y_{\delta_{j}(t)\cdot n}\leqslant f_{j}(t)$. This way any
$i\leqslant\delta_{j}(t)\cdot n$ will have $x_{i}^{(t)}\leqslant\delta_{j}(t)$
and these will be the only such $i$’s by construction. Hence, at each time
step the probability vectors of
$\textsc{Quantile}{(\delta_{1},\ldots,\delta_{k})}$ and
$\textsc{Threshold}{(f_{1},\ldots,f_{k})}$ will be the same. ∎

######  Lemma 3.8.

Any step $t$ of a $\textsc{Quantile}{(\delta_{1},\ldots,\delta_{k})}$ process
can be simulated by first choosing $f_{1}(t),f_{2}(t),\ldots,f_{k}(t)$
randomly (from a suitable distribution depending on $x^{(t)}$ and
$\delta_{1}(t),\ldots,\delta_{k}(t)$) and then running
$\textsc{Threshold}(f_{1},f_{2},\ldots,f_{k})$.

In other words, there is a reduction from Quantile to adaptive Threshold, but
the Threshold process must have the ability to randomize between different
instances of Threshold.

###### Proof.

Figure 4: The threshold process which uses a threshold of $y_{n\cdot\delta}$
probability $\alpha$ and $y_{n\cdot\delta}+1$ with probability $1-\alpha$,
corresponds to mixing the probability vectors of
$\textsc{Quantile}{(\delta^{1})}$ and $\textsc{Quantile}{(\delta^{2})}$. The
resulting probability vector differs from $\textsc{Quantile}{(\delta)}$ only
in the region $(n\cdot\delta_{1},n\cdot\delta_{2}]$, where by design all bins
have load $y_{n\cdot\delta}$. Hence, the effect of the two processes is
indistinguishable.

Let us first prove the claim for $k=1$, that is, $\textsc{Quantile}{(\delta)}$
can be simulated by an adaptive randomized threshold process with one
threshold. Since we only analyze one time-step $t$, we will for simplicity
omit this dependency and write $\delta=\delta(t)$.

Let $\delta^{1}$ be the quantile where the values equal to $y_{n\cdot\delta}$
start and $\delta^{2}$, where they end (so
$\delta^{1}\leqslant\delta\leqslant\delta^{2}$). Sampling between a threshold
of $y_{n\cdot\delta}$ and $y_{n\cdot\delta}+1$ with probability
$\alpha\in[0,1]$ interpolates between the $\textsc{Quantile}{(\delta^{1})}$
and $\textsc{Quantile}{(\delta^{2})}$. Let $p^{1}$ and $p^{2}$ be the
probability vectors for $\textsc{Quantile}{(\delta^{1})}$ and
$\textsc{Quantile}{(\delta^{2})}$, then the probability vector $q$ for this
adaptive randomized threshold process is given by,

$q_{i}=\alpha\cdot p_{i}^{1}+(1-\alpha)\cdot p_{i}^{2}.$

At $i\leqslant n\cdot\delta^{1}\leqslant n\cdot\delta^{2}$, we have,

$q_{i}=\alpha\cdot\frac{\delta^{1}}{n}+(1-\alpha)\cdot\frac{\delta^{2}}{n}.$

We pick $\alpha=\frac{\delta^{2}-\delta}{\delta^{2}-\delta^{1}}\in[0,1]$ so
that $q_{i}=\frac{\delta}{n}$ for $i\leqslant n\cdot\delta^{1}$. Then for
$i\geqslant n\cdot\delta^{2}\geqslant n\cdot\delta^{1}$, we get

$q_{i}=\alpha\cdot\frac{1+\delta^{1}}{n}+(1-\alpha)\cdot\frac{1+\delta^{2}}{n}=\frac{\alpha+(1-\alpha)}{n}+\frac{\alpha\cdot\delta^{1}+(1-\alpha)\cdot\delta^{2}}{n}=\frac{1+\delta}{n},$

by the choice of $\alpha$. So at the indices
$i\in[n]\setminus(n\delta^{1},n\delta^{2}]$ agree with
$\textsc{Quantile}{(\delta)}$.

At the indices $n\cdot\delta^{1}<i\leqslant n\cdot\delta^{2}$, the probability
is shared between bins with the same load, so the effect is indistinguishable
(see Fig. 4), in terms of the resulting load vectors.

We will extend this idea to $k>1$ quantiles, by replacing each quantile
$\delta_{j}$ with a mixture of two thresholds $y_{n\cdot\delta_{j}}$ and
$y_{n\cdot\delta_{j}}+1$ with probability $\alpha_{j}$. For this, we define
$\delta_{j}^{1}$ and $\delta_{j}^{2}$ with
$\delta_{j}^{2}\geqslant\delta_{j}\geqslant\delta_{j}^{1}$ to be the left and
right quantiles for the values of $y_{n\cdot\delta_{j}}$.

To argue that there exist coefficients $\alpha_{j}$ such that the two
processes are equivalent, we start with the probability vector $q$ of the
$\textsc{Quantile}{(\delta_{1},\ldots,\delta_{k})}$ process. For each
$j\in[k]$, construct the probability vector $q^{j}$ which agrees with $q$ at
all $i\leqslant n\cdot\delta_{j}$, except possibly for values equal to
$y_{n\cdot\delta_{j}}$. For these values at $i\leqslant\delta_{j}\cdot n$, we
will ensure that the processes have the same aggregate probability, so the
effect on these bins will be indistinguishable.

In each step we create probability vectors $p^{1j}$ and $p^{2j}$, by adding
quantiles $\delta_{j}^{1}$ and $\delta_{j}^{2}$ respectively to $q^{j-1}$.
These affect only the values of the entries in
$(n\cdot\delta_{j-1},n\cdot\delta_{j+1}]$. As in the one query case, we choose
$\alpha_{j}:=\frac{\delta_{j}^{2}-\delta_{j}}{\delta_{j}^{2}-\delta_{j}^{1}}$
such that, for $i\in(n\cdot\delta_{j-1},n\cdot\delta_{j}^{1}]$

$q_{i}^{j}=\alpha_{j}\cdot\left(\frac{\delta_{j-1}+\delta_{j}^{1}}{n}\right)+(1-\alpha_{j})\cdot\left(\frac{\delta_{j-1}+\delta_{j}^{2}}{n}\right)=\frac{\delta_{j-1}}{n}+\alpha_{j}\cdot\frac{\delta_{j}^{1}}{n}+(1-\alpha_{j})\cdot\frac{\delta_{j}^{2}}{n}=\frac{\delta_{j-1}+\delta_{j}}{n}=q_{i},$

and for $i\in(n\cdot\delta_{j}^{2},n\cdot\delta_{j+1}]$,

$q_{i}^{j}=\alpha_{j}\cdot\left(\frac{\delta_{j}^{1}+\delta_{j+1}}{n}\right)+(1-\alpha_{j})\cdot\left(\frac{\delta_{j}^{2}+\delta_{j+1}}{n}\right)=\frac{\delta_{j+1}}{n}+\frac{\alpha_{j}\delta_{j}^{1}+(1-\alpha_{j})\delta_{j}^{2}}{n}=\frac{\delta_{j-1}+\delta_{j}}{n}=q_{i}.$

The linear weighting preserves the following property: Let $B$ be a set of
bins, then if $\sum_{b\in B}p_{b}^{1j}=\sum_{b\in B}p_{b}^{2j}$ then
$\sum_{b\in B}q_{b}^{j}=\sum_{b\in B}p_{b}^{1j}=\sum_{b\in B}p_{b}^{2j}$. This
implies that:

  1. 1.

If $p_{i}^{1j}=p_{i}^{2j}$, then $q_{i}^{j}=p_{i}^{1j}=p_{i}^{2j}$.

  2. 2.

Let $B_{x}$ be the set of bins in $[1,\delta_{j-1}\cdot n]$ with equal load
$x$. By the inductive argument, in $q^{j}$ the probability of allocating a
ball to $x$ will be the same as in that of $q$.

Hence, this ensures that each step extends the agreement of probability vector
$q^{j}$ and $q$ to each bin $i\in[1,\delta_{j+1}\cdot n]$. The only possible
exceptions are bins with equal load, where the probability mass is just
rearranged among them. Hence, $q^{k}$ will be equivalent to $q$ for the given
load vector.∎

######  Lemma 3.9.

For any $k\geqslant 1$, a Quantile$(\delta_{1},\ldots,\delta_{k})$ process can
be simulated by an adaptive (and randomized) $(2k)$-Thinning process.

###### Proof.

We may assume that Quantile$(\delta_{1},\ldots,\delta_{k})$ will process $2k$
queries one by one, and alternate between the two bins. First, send the
largest quantile to bin $i_{1}$, then send the largest to bin $i_{2}$, then
send the second largest to bin $i_{1}$, etc. and stop as soon as you receive a
negative answer. Therefore, for ease of notation, let us set
$\gamma_{i}:=\delta_{k-i}$ for $i\in[k]$.

Further, let $i_{1}$ and $i_{2}$ be two chosen bins, and $\widetilde{i}$ be
the bin where the ball is finally placed. Note that

$\mathbf{Pr}\left[\,\operatorname{Rank}^{(t)}(\widetilde{i})\leqslant
n\cdot\gamma_{j}\,\right]=\gamma_{j}\cdot\gamma_{j}.$

since $\widetilde{i}\in\\{i_{1},i_{2}\\}$ will be of rank at least
$n\cdot\gamma_{j}$ if and only if both bins $i_{1}$ and $i_{2}$ satisfy
$\operatorname{Rank}^{(t)}(i_{1})\leqslant n\cdot\gamma_{j}$ and
$\operatorname{Rank}^{(t)}(i_{2})\leqslant n\cdot\gamma_{j}$; and those bins
are chosen independently.

On the other hand, consider now an adaptive $(2k)$-Thinning process with
increasing load thresholds $f_{1}\leqslant f_{2}\leqslant\ldots\leqslant
f_{2k}$ and $2k$ bin choices $i_{1},i_{2},\ldots,i_{2k}$, which are chosen
uniformly and independently at random. Each load threshold $f_{j}$ applied to
bin $i_{j}$ will be randomized so that it simulates a
Quantile$(\gamma_{\lfloor(j-1)/2\rfloor})$ see (3.8). Further, let
$\overline{i}$ be the final bin of this allocation process.

First, the bin $i_{\ell}$ in iteration $\ell$ will not be accepted with
probability

$\mathbf{Pr}\left[\,\operatorname{Rank}^{(t)}(i_{\ell})\leqslant
n\cdot\gamma_{1+\lfloor\ell/2\rfloor}\,\right]=\gamma_{1+\lfloor\ell/2\rfloor},$

and using the independence of the first $2j$ sampled different bins, we obtain

$\displaystyle\mathbf{Pr}\left[\,\operatorname{Rank}^{(t)}(\overline{i})\leqslant
n\cdot\gamma_{j}\,\right]$
$\displaystyle=\prod_{\ell=1}^{2j}\mathbf{Pr}\left[\,\operatorname{Rank}^{(t)}(i_{\ell})\leqslant
n\cdot\gamma_{1+\lfloor\ell/2\rfloor}\,\right]$
$\displaystyle=\gamma_{1}\cdot\gamma_{1}\cdot\gamma_{2}\cdot\gamma_{2}\cdot\ldots\cdot\gamma_{j}\cdot\gamma_{j}\leqslant\gamma_{j}\cdot\gamma_{j}\leqslant\mathbf{Pr}\left[\,\operatorname{Rank}^{(t)}(\widetilde{i})\leqslant
n\cdot\gamma_{j}\,\right].$

∎

##  4 Lower Bounds for One Quantile and One Threshold

In the lightly loaded case (i.e., $m=n$), [18] proved an upper bound of
$(2+o(1))\cdot(\sqrt{2\log n/\log\log n})$ on the maximum load for a uniform
Threshold$(f)$-process with $f=\sqrt{2\log n/\log\log n}$ ([20] extended this
to $d>2$). They also proved that this strategy is asymptotically optimal. In
[18, Problem 1.3], the authors suggest that the $\mathcal{O}(\sqrt{\log
n/\log\log n})$ bound on the gap extends to the heavily loaded case. Here we
will disprove this, establishing a slightly larger lower bound of
$\Omega(\sqrt{\log n})$ (4.2). We also derive additional lower bounds (4.1 and
4.6) that demonstrate that any Quantile or Threshold process will “frequently”
attain a gap which is even as large as $\Omega(\log n/\log\log n)$.

Let us describe the intuition behind this bound in case of uniform quantiles,
neglecting some technicalities. Consider $\textsc{Quantile}(\delta)$ and the
equivalent $2$-Thinning instance where a ball is placed in the first bin if
its load is among the $(1-\delta)\cdot n$ lightest bins, and otherwise it is
placed in a new (second) bin chosen uniformly at random (Lemma 3.1). We have
two cases:

  1. Case 1: We choose most times a “large” $\delta$. Then we allocate approximately $m\cdot\delta$ balls to their second bin choice which is uniform over all $n$ bins. This will lead to a behavior close to One-Choice (4.3).

  2. Case 2: We choose most times a “small” $\delta$. Then we allocate approximately $m\cdot(1-\delta)$ balls with the first bin choice, which is a One-Choice process over the $n\cdot(1-\delta)$ lightest bins. As we establish in 4.4, for small $\delta$ there are simply “too many” light bins that will reach a high load level, so the process is again close to One-Choice.

######  Theorem 4.1.

For any adaptive $\textsc{Quantile}(\delta)$ (or Threshold$(f)$) process,

$\mathbf{Pr}\left[\,\max_{t\in[1,n\log^{2}n]}\operatorname{Gap}(t)\geqslant\frac{1}{8}\cdot\frac{\log
n}{\log\log n}\,\right]\geqslant 1-o(n^{-2}).$

In fact, as shown in 4.6, this lower bound holds for a significant proportion
of time-steps. We also show a lower bound for fixed $m$, which is derived in a
similar way as 4.1, but with a different parameterization of “large” and
“small” quantiles:

######  Theorem 4.2.

For any adaptive $\textsc{Quantile}(\delta)$ (or Threshold$(f)$) process, with
$m=K\cdot n\sqrt{\log n}$ balls for $K=1/10$, it holds that

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\geqslant\frac{1}{20}\sqrt{\log
n}\,\right]\geqslant 1-o(n^{-2}).$

###  4.1 Preliminaries for Lower Bounds

Let us first formalize the intuition of the lower bound. Recall that we will
analyze the adaptive case, which means that the quantiles at each step $t$ may
depend on the full history of the process, or, equivalently, on the load
vector $(x_{1}^{(t-1)},x_{2}^{(t-1)},\ldots,x_{n}^{(t-1)})$. We also remind
the reader that any adaptive Threshold$(f)$ process can be simulated by
$\textsc{Quantile}(\delta)$ (3.7), which is why we will do the analysis below
for $\textsc{Quantile}(\delta)$ only.

The next lemma proves that if within $n$ consecutive allocations a large
quantile is used too often, then $\textsc{Quantile}(\delta)$ restricted to the
heavily loaded bins generates a high maximum load, similar to One-Choice.

######  Lemma 4.3.

Consider any adaptive $\textsc{Quantile}(\delta)$ process during the time-
interval $[t,t+n)$. If $\textsc{Quantile}(\delta)$ allocates at least $n/(\log
n)^{2}$ balls with a quantile larger than $(\log n)^{-2}$ in $[t,t+n)$, then

$\mathbf{Pr}\left[\,\operatorname{Gap}(t+n)\geqslant\frac{1}{8}\frac{\log
n}{\log\log n}\,\right]\geqslant 1-o(n^{-4}).$

###### Proof.

Assume there are at least $n/(\log n)^{2}$ allocations with quantile larger
than $(\log n)^{-2}$. Then, using A.1, w. p. at least $1-o(n^{-4})$, at least
$\frac{1}{e}\frac{n}{\log^{2}n}\cdot\frac{1}{\log^{2}{n}}\geqslant\frac{n}{\log^{5}n}$
balls are thrown using One-Choice.

Consider now the load configuration before the _batch_ , i.e. the next $n$
balls are allocated. If $\operatorname{Gap}(t)\geqslant\log n$, then
$\operatorname{Gap}(t+n)\geqslant\frac{1}{8}\log n/\log\log n$, as a load can
decrease by at most $1$ in $n$ steps. So we can assume
$\operatorname{Gap}(t)<\log n$. Let $B$ be the set of bins whose load is at
least the average load at time $t$, then $|B|\geqslant n/\log n$. Using A.1,
w. p. at least $1-o(n^{-4})$ the batch will allocate at least $n/(\log n)^{6}$
balls to the bins of $B$. Hence, by A.7, at least one bin in $B$ will increase
its load by an additive factor of $\frac{1}{7}\log n/\log\log n$ w. p. at
least $1-o(n^{-4})$. Since the average load only increases by one during the
batch, there will be a gap of $\frac{1}{8}\log n/\log\log n$ w.h.p., and our
claim is established. ∎

The next lemma implies that if for most allocations the largest quantile is
too small, then the allocations on the lightest bins follows that of One-
Choice, and we end up with a high maximum load.

######  Lemma 4.4.

Consider any adaptive $\textsc{Quantile}(\delta)$ process with $m=n\log^{2}n$
balls that allocates at most $n$ balls with a quantile larger than $(\log
n)^{-2}$. Then,

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\geqslant 0.2\log n\,\right]\geqslant
1-o(n^{-2}).$

The proof of this Lemma is similar to 4.3, but a bit more complex. We define a
coupling between the $\textsc{Quantile}(\delta)$ process and the One-Choice
process. We couple the allocation of balls whose first sample is among the
$(1-\delta(t))\cdot n$-lightest bins with a One-Choice process. The balls
whose first sample is among the $\delta(t)\cdot n$-heaviest bins are allocated
differently, and cause our process to diverge from an original One-Choice
process. However, we prove that the number of different allocations is too
small to change the order of the gap.

###### Proof.

We will use the following coupling between the allocations of
$\textsc{Quantile}{(\delta)}$ and One-Choice. At each step
$t\in[1,n\log^{2}n]$, we first sample a bin index $j\in[n]$ uniformly at
random. In the One-Choice process, we place the ball in the $j$-th most loaded
bin. In the Quantile process:

  1. 1.

If $j>\delta(t)\cdot n$, we place the ball in the $j$-th most loaded bin (of
Quantile), and we say that the processes agree.

  2. 2.

If $j\leqslant\delta(t)\cdot n$, we sample another bin index
$\widetilde{j}\in[n]$ uniformly at random and place the ball in the
$\widetilde{j}$-th most loaded bin (of Quantile).

Let $y^{(s)}$ and $z^{(s)}$ be the sorted load vectors of One-Choice and the
Quantile process respectively at step $s\geqslant 0$. Further, let
$L(s):=d_{\ell_{1}}(y^{(s)},z^{(s)})$ be the $\ell_{1}$-distance between these
vectors. Note that $L(0)=0$. If in a step both processes place a ball in the
$j$-th most loaded bin, using a simple coupling argument (see 4.5 below for
details) it follows that

$L(t+1)\leqslant L(t).$

Otherwise, if in a step the processes place a ball in a different bin, since
only two positions in the load vectors can increase by one, then

$L(t+1)\leqslant L(t)+2.$

Hence by induction over $s$, if $k$ is the number of steps for which the
processes disagree, then

$L(n\log^{2}n)\leqslant 2\cdot k.$

We will next show an upper bound on $k$, which in turn implies an upper bound
on $L(n\log^{2}n)$. First, for each of the at most $n$ steps
$t\in[1,n\log^{2}n]$ for which $\delta(t)\geqslant(\log n)^{-2}$, we
(pessimistically) assume that the two processes always disagree. Secondly, for
the at most $n\log^{2}n$ steps $t\in[1,n\log^{2}n]$ with
$\delta(t)\leqslant(\log n)^{-2}$, using a Chernoff bound (A.1), we have w. p.
$1-o(n^{-2})$ in at most $(n\log^{2}n)\cdot(\log n)^{-2}\cdot e=ne$ of these
steps $s$, the case that $j\leqslant\delta(s)\cdot n$, i.e., the two processes
disagree. Now if this event occurs,

$k\leqslant n\cdot 1+n\cdot e\leqslant 2n\cdot e\qquad\Rightarrow\qquad
L(n\log^{2}n)\leqslant 4n\cdot e.$

By A.9, there are constants $a=0.4,c=0.25$ such that with probability
$1-o(n^{-2})$, the One-Choice load vector $y^{(n\log^{2}n)}$ has at least
$cn\log n$ balls with height at least $\frac{a}{2}\log n$. However, any load
vector which has no balls at height $\frac{a}{2}\log n$ must have a
$\ell_{1}$-distance of at least $cn\log n$ to $y^{(n\log^{2}n)}$, and thus we
conclude by the union bound that
$\operatorname{Gap}(n\log^{2}n)\geqslant\frac{a}{2}\log n$ holds with
probability $1-2o(n^{-2})$.∎

######  Lemma 4.5.

Let $y$ and $z$ be two decreasingly sorted load vectors. Consider the sorted
vectors $y+\mathbf{e}_{i}$ and $z+\mathbf{e}_{i}$ after incrementing the value
at index $i$. Then, $d_{\ell_{1}}(y,z)\geqslant
d_{\ell_{1}}(y+\mathbf{e}_{i},z+\mathbf{e}_{i})$.

###### Proof.

If the items being updated end up both in the same indices (after sorting),
then their $\ell_{1}$ distance remains unchanged.

Let $u:=y_{i}$ and $v:=z_{i}$ for the updated index $i$ in the (old) sorted
load vector. To obtain the new sorted load vector, we have to search in both
$y$ and $z$ from right to left for the leftmost entry being equal to $u$ and
being equal to $v$, respectively, and then increment these values. Then, there
are the following three cases to consider (in bold is the value to be
updated):

Case 1 $u<v$: Let $v<w_{1}\leqslant\ldots\leqslant w_{k}$, where $w_{k}$ is
the matching value for $u+1$ in $z$, then $w_{k}>v\Rightarrow w_{k}\geqslant
u+2$

$\begin{array}[t]{c|cccccccc}y&\ldots&u&\ldots&u&u&\ldots&\mathbf{u}&\ldots\\\
\hline\cr z&\ldots&w_{k}&\ldots&w_{1}&v&\ldots&\mathbf{v}&\ldots\end{array}\ \
\raisebox{-6.0pt}{$\to$}\ \
\begin{array}[t]{c|cccccccc}y+\mathbf{e}_{i}&\ldots&u+1&\ldots&u&u&\ldots&u&\ldots\\\
\hline\cr z+\mathbf{e}_{i}&\ldots&w_{k}&\ldots&w_{1}&v+1&\ldots&v&\ldots\\\
\lx@intercol\hfil\hfil\lx<EMAIL_ADDRESS><EMAIL_ADDRESS>to0.0pt{$\underbrace{\hphantom{\mbox{$v+1$}}}_{+1}$\hss}}\hfil&&&\end{array}$

Case 2 $u<v$: Let $u<w_{1}\leqslant\ldots\leqslant w_{k}$, where $w_{k}$ is
the matching value for $v+1$ in $y$

$\begin{array}[t]{c|cccccccc}y&\ldots&w_{k}&\ldots&w_{1}&u&\ldots&\mathbf{u}&\ldots\\\
\hline\cr z&\ldots&v&\ldots&v&v&\ldots&\mathbf{v}&\ldots\end{array}\ \
\raisebox{-6.0pt}{$\to$}\ \
\begin{array}[t]{c|cccccccc}y+\mathbf{e}_{i}&\ldots&w_{k}&\ldots&w_{1}&u+1&\ldots&u&\ldots\\\
\hline\cr z+\mathbf{e}_{i}&\ldots&v+1&\ldots&v&v&\ldots&v&\ldots\\\
\lx@intercol\hfil\hfil\lx<EMAIL_ADDRESS>to0.0pt{$\underbrace{\hphantom{\mbox{$v+1$}}}_{\leqslant
<EMAIL_ADDRESS>to0.0pt{$\underbrace{\hphantom{\mbox{$u+1$}}}_{-1}$\hss}}\hfil&&&\end{array}$

Case 3 $u=v$: Let $u<w_{1}\leqslant\ldots\leqslant w_{k}$, where $w_{k}$ is
the matching value for $u+1$ in $z$

$\begin{array}[t]{c|cccccccc}y&\ldots&w_{k}&\ldots&w_{1}&u&\ldots&\mathbf{u}&\ldots\\\
\hline\cr z&\ldots&u&\ldots&u&u&\ldots&\mathbf{u}&\ldots\end{array}\ \
\raisebox{-6.0pt}{$\to$}\ \
\begin{array}[t]{c|cccccccc}y+\mathbf{e}_{i}&\ldots&w_{k}&\ldots&w_{1}&u+1&\ldots&u&\ldots\\\
\hline\cr z+\mathbf{e}_{i}&\ldots&u+1&\ldots&u&u&\ldots&u&\ldots\\\
\lx@intercol\hfil\hfil\lx<EMAIL_ADDRESS><EMAIL_ADDRESS>to0.0pt{$\underbrace{\hphantom{\mbox{$u+1$}}}_{+1}$\hss}}\hfil&&&\end{array}$

∎

###  4.2 Lower Bound for a Range of Values (Theorem 4.1)

With 4.3 and 4.4 proven in the previous subsection, we can now derive a lower
bound for any adaptive $\textsc{Quantile}(\delta)$ (or Threshold$(f)$)
process, establishing 4.1. After the proof, we also state two simple
consequences that follow immediately from this result.

See 4.1

###### Proof.

Since any adaptive Threshold$(f)$ can be simulated by an adaptive
$\textsc{Quantile}(\delta)$ process (see 3.7), it suffices to prove the claim
for adaptive $\textsc{Quantile}(\delta)$ processes. We will allow the
adversary to run two processes, and then choose one that achieves a gap of
$<\frac{1}{8}\log{n}/\log{\log{n}}$ (if such exists):

  * •

Process $P_{1}$. The adversary has to allocate $m=n\log^{2}n$ balls into $n$
bins. The adversary wins if for all steps $t\in[m]$,
$\operatorname{Gap}(t)<\frac{1}{8}\log n/\log\log n$, and, Condition $C_{1}$,
at least $n$ out of the $m$ quantiles are larger than $(\log n)^{-2}$.

  * •

Process $P_{2}$. The adversary has to allocate $m=n\log^{2}{n}$ balls into $n$
bins. The adversary wins if $\operatorname{Gap}(m)<\frac{1}{8}\log n/\log\log
n$ and, Condition $C_{2}$, at least $m-n=n\log^{2}n-n$ out of the $m$
quantiles are at most $(\log n)^{-2}$.

Note that the conditions $C_{1}$ and $C_{2}$ form a disjoint partition. We
will prove that the adversary cannot win any of the two games with probability
greater than $n^{-2}$. Now recall the original process, the one we would like
to analyze:

  * •

Process $P_{3}$ (adaptive $\textsc{Quantile}(\delta)$). The adversary has to
allocate $m=n\log^{2}n$ balls into bins at each step. The adversary wins if
$\operatorname{Gap}(t)<\frac{1}{8}\log n/\log\log n$ for all $t\in[m]$.

We will show below that $\mathbf{Pr}\left[\,\mbox{adversary wins
$P_{1}$}\,\right]=o(n^{-2})$ and $\mathbf{Pr}\left[\,\mbox{adversary wins
$P_{2}$}\,\right]=o(n^{-2})$, and these bounds hold for the best possible
strategies an adversary can use in each game, respectively. Assuming that
these bounds hold and by noticing that exactly one of $C_{1}$ and $C_{2}$ must
hold for $P_{3}$,

$\mathbf{Pr}\left[\,P_{3}\text{ wins}\,\right]=\mathbf{Pr}\left[\,P_{3}\text{
wins},C_{1}\,\right]+\mathbf{Pr}\left[\,P_{3}\text{
wins},C_{2}\,\right]\leqslant\mathbf{Pr}\left[\,P_{1}\text{
wins}\,\right]+\mathbf{Pr}\left[\,P_{2}\text{ wins}\,\right]\leqslant
o(n^{-2}).$

Analysis of Process 1: Let $\mathcal{E}_{t}$ be the event that (i) Quantile
allocates at least $n/(\log n)^{2}$ balls with a quantile larger than $(\log
n)^{-2}$ in the interval $[t,t+n)$, and (ii)
$\operatorname{Gap}(t+n)<\frac{1}{8}\log n/\log\log n$. Note that this is the
negation of 4.3, so by union bound over $1\leqslant t\leqslant m-n$,

$\mathbf{Pr}\left[\,\bigcup_{t=1}^{m-n}\mathcal{E}_{t}\,\right]\leqslant
n\log^{2}n\cdot o(n^{-4})=o(n^{-2}).$

Note that if none of the $\mathcal{E}_{t}$ for $1\leqslant t\leqslant m-n$
occur, then the adversary allocates at most $n/(\log n)^{2}\cdot(\log
n)^{2}\geqslant n$ out of the $m$ balls with a quantile at least $(\log
n)^{-2}$. Therefore,

$\mathbf{Pr}\left[\,\mbox{adversary wins $P_{1}$}\,\right]\leqslant
o(n^{-2}).$

Analysis of Process 2: The analysis of $P_{2}$ follows directly by 4.4.∎

Let us also observe a slightly stronger statement which follows directly from
Theorem 4.1:

######  Corollary 4.6.

Any adaptive process $\textsc{Quantile}(\delta)$ satisfies:

$\mathbf{Pr}\left[\,\bigcup_{t\in[1,n\log^{2}n]}\left\\{\min_{s\in\left[t,t+\frac{1}{16}n\frac{\log
n}{\log\log
n}\right)}\operatorname{Gap}(s)\geqslant\frac{1}{16}\cdot\frac{\log
n}{\log\log n}\right\\}\,\right]\geqslant 1-n^{-2}.$

###### Proof of 4.6.

If there is a step $t$ for which
$\operatorname{Gap}(t)\geqslant\frac{1}{8}\cdot\log n/\log\log n$, then for
any $s$ with $t\leqslant s\leqslant t+\frac{1}{16}\cdot\log n/\log\log n$,
$\operatorname{Gap}(s)\geqslant\operatorname{Gap}(t)-(s-t)/n\geqslant\frac{1}{16}\cdot\log
n/\log\log n$. Hence the statement follows from 4.1. ∎

In other words, the corollary states that for at least $\Omega(n\log
n/\log\log n)$ (consecutive) steps in $[1,\Theta(n\log^{2}n)]$, the gap is
$\Omega(\log n/\log\log n)$. This is in contrast to the behavior of the
process $\textsc{Quantile}(\delta_{1},\delta_{2})$, for which our result in
Section 6 implies that with high probability the gap is always below
$\mathcal{O}(\sqrt{\log n})$ during any time-interval of the same length.

For uniform $\textsc{Quantile}(\delta)$, we are always running either process
$P_{1}$ or $P_{2}$, so the following strengthened version of 4.1 holds:

######  Corollary 4.7.

For any uniform $\textsc{Quantile}(\delta)$ process for $m=n\log^{2}n$ balls,

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\geqslant\frac{1}{8}\cdot\frac{\log
n}{\log\log n}\,\right]\geqslant 1-o(n^{-2}).$

###### Proof.

Since $\delta$ is fixed, in the proof of 4.1, we are always running either
process $P_{1}$ or $P_{2}$. For process $P_{1}$, $\mathcal{E}_{m-n}$ holds
w.p. $1-o(n^{-4})$, so there is an $\Omega(\log n/\log\log n)$ gap at $m$. For
process $P_{2}$, there is an $\Omega(\log n/\log\log n)$ gap at $m$ w.p.
$1-o(n^{-2})$. Hence, in both cases the gap at step $m$ is $\Omega(\log
n/\log\log n)$ w.p. $1-o(n^{-2})$. ∎

###  4.3 Lower Bound for Fixed $m=\Theta(n\sqrt{\log n})$ (4.2)

We now prove a version of 4.1 that establishes a lower bound of
$\Omega(\sqrt{\log n})$ on the gap for a fixed value $m$. It follows the same
proof as 4.1 except that the parameters are different: (i)
$m=\Theta(n\sqrt{\log n})$ and (ii) Condition $C_{1}$ is defined as having at
least $m\cdot e^{-\sqrt{\log n}}$ out of the $m$ quantiles being at least
$e^{-\sqrt{\log n}}$. 4.8 is the modified 4.3 and 4.9 is the modified 4.4.

######  Lemma 4.8.

Consider any adaptive $\textsc{Quantile}(\delta)$ process during the time-
interval $[t,t+n)$. If $\textsc{Quantile}(\delta)$ allocates at least
$n/e^{\sqrt{\log{n}}}$ balls with a quantile larger than $e^{-\sqrt{\log{n}}}$
in $[t,t+n)$, then

$\mathbf{Pr}\left[\,\operatorname{Gap}(t+n)\geqslant\frac{1}{5}\sqrt{\log
n}\,\right]\geqslant 1-o(n^{-4}).$

###### Proof.

Assume there are at least $n/e^{\sqrt{\log{n}}}$ allocations with quantile
larger than $e^{-\sqrt{\log{n}}}$. Then, using A.1, w. p. at least
$1-o(n^{-4})$, at least
$\frac{1}{e}\frac{n}{e^{\sqrt{\log{n}}}}\cdot\frac{1}{e^{\sqrt{\log{n}}}}\geqslant\frac{n}{e^{3\sqrt{\log{n}}}}$
balls are thrown using One-Choice.

Consider now the load configuration before the batch is allocated. If
$\operatorname{Gap}(t)\geqslant\frac{1}{4}\sqrt{\log n}$, then
$\operatorname{Gap}(t+n)\geqslant\frac{1}{5}\sqrt{\log n}$, as a load can
decrease by at most $1$ in $n$ steps. So we can assume
$\operatorname{Gap}(t)<\frac{1}{4}\sqrt{\log n}$. Let $B$ be the set of bins
whose load is at least the average load at time $t$, then $|B|\geqslant
n/(\frac{1}{4}\sqrt{\log n})$. Using A.1, w. p. at least $1-o(n^{-4})$ the
batch will allocate at least $n/(e\cdot
e^{3\sqrt{\log{n}}}\cdot(\frac{1}{4}\sqrt{\log n}))\geqslant
n/e^{4\sqrt{\log{n}}}$ balls to the bins of $B$. Hence, using A.8 with
$c=1/2$, $u=4$ and $k=\frac{2}{9}$ at least one bin in $B$ will increase its
load by an additive factor of $\frac{2}{9}\sqrt{\log{n}}$ w. p. at least
$1-o(n^{-4})$. Since the average load only increases by one during the batch,
we have created a gap of
$\frac{2}{9}\sqrt{\log{n}}-1>\frac{1}{5}\sqrt{\log{n}}$, and our claim is
established. ∎

######  Lemma 4.9.

Consider any adaptive $\textsc{Quantile}(\delta)$ process with $m=Kn\sqrt{\log
n}$ balls that allocates at most $n$ balls with a quantile larger than
$e^{-\sqrt{\log n}}$, then

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\geqslant\frac{1}{20}\sqrt{\log
n}\,\right]\geqslant 1-o(n^{-2}),$

where $K=1/10$.

###### Proof.

Let $C=1/20$. We will use the same coupling as in the proof of 4.4. We now
obtain an upper bound on $k$, which in turn implies an upper bound on
$L(Kn\sqrt{\log n})$. First, for each of the at most $n$ steps
$t\in[1,Kn\sqrt{\log n}]$ for which $\delta(t)\geqslant e^{-\sqrt{\log n}}$,
we (pessimistically) assume that the two processes always disagree. Secondly,
for the at most $Kn\sqrt{\log n}$ steps $t\in[1,Kn\sqrt{\log n}]$ with
$\delta(t)\leqslant e^{-\sqrt{\log n}}$, using a Chernoff bound (A.1), we have
w. p. $1-o(n^{-2})$ in at most $e\cdot(Kn\sqrt{\log n})\cdot e^{-\sqrt{\log
n}}$ of these steps $s$ the case that $j\leqslant\delta(s)\cdot n$, i.e., the
two processes disagree. Now if this event occurs,

$k\leqslant n\cdot 1+n\cdot e\leqslant 2n\cdot e\qquad\Rightarrow\qquad
L(Kn\sqrt{\log n})\leqslant 4\cdot e\cdot(Kn\sqrt{\log n})\cdot e^{-\sqrt{\log
n}}.$

By A.10, with probability $1-o(n^{-2})$, the One-Choice load vector
$y^{(Kn\sqrt{\log n})}$ has at least $e^{-0.21\sqrt{\log n}}\cdot
Cn\sqrt{\log{n}}$ balls with at least $(K+C)\cdot\sqrt{\log n}$ height.
However, any load vector which has no balls at height $(K+C)\cdot\sqrt{\log
n}$ must have a $\ell_{1}$-distance of at least $e^{-0.21\sqrt{\log n}}\cdot
Cn\sqrt{\log{n}}\cdot K\cdot\sqrt{\log n}>L(Kn\sqrt{\log n})$ to
$y^{(Kn\sqrt{\log n})}$, and thus we conclude by the union bound that
$\operatorname{Gap}(Kn\sqrt{\log n})\geqslant C\sqrt{\log n}$ holds with
probability $1-2o(n^{-2})$. ∎

See 4.2

###### Proof.

Since any adaptive Threshold$(f)$ can be simulated by an adaptive
$\textsc{Quantile}(\delta)$ process (see Section 2), it suffices to prove the
claim for adaptive $\textsc{Quantile}(\delta)$ processes. We will allow the
adversary to run two processes, and then choose one that achieves a gap
smaller than $C\sqrt{\log n}$ (if such exists):

  * •

Process $P_{1}$. The adversary has to allocate $m=Kn\sqrt{\log n}$ balls into
$n$ bins. The adversary wins if for step $m$,
$\operatorname{Gap}(m)<C\sqrt{\log n}$, and, Condition $C_{1}$, at least
$(Kn\sqrt{\log n})\cdot e^{-\sqrt{\log n}}$ out of the $m$ quantiles are
larger than $e^{-\sqrt{\log n}}$.

  * •

Process $P_{2}$. The adversary has to allocate $m=Kn\sqrt{\log n}$ balls into
$n$ bins. The adversary wins if for step $m$,
$\operatorname{Gap}(m)<C\sqrt{\log n}$ and, Condition $C_{2}$, at least
$m-(Kn\sqrt{\log n})\cdot e^{-\sqrt{\log n}}$ out of the $m$ quantiles are at
most $e^{-\sqrt{\log n}}$.

We will prove that the adversary cannot win any of the two games with
probability greater than $n^{-2}$. Now recall the original process, the one we
would like to analyze:

  * •

Process $P_{3}$ (adaptive $\textsc{Quantile}(\delta)$). The adversary has to
allocate $m=Kn\sqrt{\log n}$ balls into bins using one adaptive query at each
step. The adversary wins if $\operatorname{Gap}(m)<C\sqrt{\log n}$.

Again, we will show below that $\mathbf{Pr}\left[\,\mbox{adversary wins
$P_{1}$}\,\right]=o(n^{-2})$ and $\mathbf{Pr}\left[\,\mbox{adversary wins
$P_{2}$}\,\right]=o(n^{-2})$, and these bounds imply that
$\mathbf{Pr}\left[\,P_{3}\text{ wins}\,\right]=o(n^{-2})$. We now turn to the
analysis of $P_{1}$ and $P_{2}$:

Analysis of Process 1: Let $\mathcal{E}_{t}$ be the event that (i) Quantile
allocates at least $n\cdot e^{-\sqrt{\log n}}$ balls with a quantile at least
$e^{-\sqrt{\log n}}$ in the interval $[t,t+n]$, and (ii)
$\operatorname{Gap}(t+n)\leqslant\frac{1}{5}\sqrt{\log n}$. Note that this is
the negation of 4.8, so by union bound over $1\leqslant t\leqslant m-n$,

$\mathbf{Pr}\left[\,\bigcup_{t=1}^{m-n}\mathcal{E}_{t}\,\right]\leqslant
K\cdot n\sqrt{\log n}\cdot o(n^{-4})=o(n^{-2}).$

Note that if none of the $\mathcal{E}_{t}$ for $1\leqslant t\leqslant m-n$
occur, then we either have
$\operatorname{Gap}(t)\geqslant\frac{1}{5}\sqrt{\log{n}}$ at some time
$t\leqslant m$ (implying
$\operatorname{Gap}(m)\geqslant(\frac{1}{5}-\frac{1}{10})\sqrt{\log
n}\geqslant\frac{1}{20}\sqrt{\log n}$), or the adversary allocates less than
$\frac{n}{e^{\sqrt{\log n}}}\cdot K\sqrt{\log n}$ out of the $m$ balls with a
quantile at least $e^{-\sqrt{\log n}}$. Therefore,

$\mathbf{Pr}\left[\,\mbox{adversary wins $P_{1}$}\,\right]=o(n^{-2}).$

Analysis of Process 2: The analysis of $P_{2}$ follows directly by 4.9. ∎

##  5 Upper Bounds for One Quantile

In this section we study the $\textsc{Quantile}(\delta)$ process for constant
$\delta\in(0,1)$. This analysis will also serve as the basis for the
$k$-quantile case with $k>1$ in Section 6. First, we define the following
exponential potential function (similarly to [32]): For any time-step
$s\geqslant 0$,

$\displaystyle\Phi_{0}^{(s)}:=\sum_{i=1}^{n}\exp\left(\alpha_{2}\cdot(x_{i}^{(s)}-\frac{s}{n})^{+}\right),$

where $z^{+}=\max(z,0)$ and $\alpha_{2}>0$ to be specified later. We first
remark that with the results in [32], a bound on the expected value of
$\Phi_{0}$ can be easily derived:

######  Theorem 5.1 (cf. Theorem 2.10 in [32]).

Consider any allocation process with probability vector $p$ that is (i) non-
decreasing in $i$, $p_{i}\leqslant p_{i+1}$ and (ii) for some
$0<\varepsilon<1/4$,

$p_{n/3}\leqslant\frac{1-4\varepsilon}{n}\quad\text{ and }\quad
p_{2n/3}\geqslant\frac{1+4\varepsilon}{n}.$

Then, for $0<\alpha_{2}<\varepsilon/6$, we have for any $s\geqslant 0$,
$\mathbf{E}\left[\,\Phi_{0}^{(s)}\,\right]\leqslant cn$, where
$c=\frac{40\cdot 128^{3}}{\varepsilon^{5}}$.

In particular, by verifying the condition on the probability vector and
applying Markov’s inequality, we immediately obtain an upper bound of
$\mathcal{O}(\log n)$ on the gap.

######  Theorem 5.2.

For the quantile process $\textsc{Quantile}(\delta)$ with $\delta\in[1/3,2/3]$
and any $m\geqslant 1$,

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\leqslant 300\log n\,\right]\geqslant
1-\mathcal{O}(n^{-2}).$

###### Proof.

We will show that the $\textsc{Quantile}(\delta)$ process for
$\delta\in[1/3,2/3]$ satisfies the preconditions of 5.1. For the potential
$\Phi_{0}$, we pick $\alpha_{2}:=0.01$. The probability vector of
$\textsc{Quantile}(\delta)$ is clearly non-decreasing in $i$, and choosing
$\varepsilon:=\frac{1}{12}$ it also satisfies

$p_{n/3}=\frac{\delta}{n}\leqslant\frac{1-4\cdot\frac{1}{12}}{n}=\frac{3}{4}\cdot\frac{1}{n}\quad\text{and}\quad
p_{2n/3}=\frac{1+\delta}{n}\geqslant\frac{1+4\cdot\frac{1}{12}}{n}=\frac{1+\frac{1}{3}}{n}.$

Hence 5.1 yields $\mathbf{E}[\,\Phi_{0}^{(m)}\,]\leqslant cn$. Using Markov’s
inequality, $\mathbf{Pr}\left[\,\Phi_{0}^{(m)}\leqslant
n^{3}\,\right]\geqslant 1-\mathcal{O}(n^{-2})$ for sufficiently large $n$.
Assume the gap is $\operatorname{Gap}(m)>300\cdot\log n$, then

$\Phi_{0}^{(m)}\geqslant\exp{(\alpha_{2}\cdot\operatorname{Gap}(m))}>\exp{(0.01\cdot
300\cdot\log n)}=n^{3},$

which is a contradiction. Hence, $\operatorname{Gap}(m)\leqslant 300\cdot\log
n$ w. p. at least $1-\mathcal{O}(n^{-2})$. ∎

We note that an alternative way of proving a gap bound of $\mathcal{O}(\log
n)$ is to use the fact that any $\textsc{Quantile}(\delta)$ process with
$\delta\in(0,1)$ is majorized by a $(1+\beta)$-process with
$\beta=\min\\{\delta,1-\delta\\}$ (see Lemma 3.6). However, this proof is less
direct and leads to a slightly worse constant, which is why we apply 5.1 to
$\textsc{Quantile}(\delta)$ instead.

However, to analyze the process with more than one quantile in the next
section, we will need a tighter analysis. We prove the following refined
version of 5.1:

######  Theorem 5.3.

Consider any probability vector $p$ that is $(i)$ non-decreasing in $i$, i.e.,
$p_{i}\leqslant p_{i+1}$ and $(ii)$ for $\varepsilon=1/12$,

$p_{n/3}\leqslant\frac{1-4\varepsilon}{n}\quad\text{ and }\quad
p_{2n/3}\geqslant\frac{1+4\varepsilon}{n}.$

Then, for any $t\geqslant 0$ and $\alpha_{2}:=0.0002$,
$c:=c_{\varepsilon,\alpha_{2}}:=2\cdot 40\cdot
128^{3}\cdot\varepsilon^{-7}\cdot 4\cdot\alpha_{2}^{-1}$,

$\mathbf{Pr}\left[\,\bigcap_{s\in[t,t+n\log^{5}n]}\\{\Phi_{0}^{(s)}\leqslant
2cn\\}\,\right]\geqslant 1-n^{-3}.$

Note that 5.3 not only implies a gap of $\mathcal{O}(\log n)$ using Markov’s
inequality (as 5.1), but also that for any fixed time $s$, the number of bins
with load at least $s/n+\lambda$ is at most $2cn/\exp(\alpha_{2}\cdot\lambda)$
for any $\lambda\geqslant 0$. In particular, for any $\lambda=\Theta(\log n)$,
only a polynomially small fraction of all bins have load at least
$s/n+\lambda$.

Proof Outline of Theorem 5.3. In order to prove that $\Phi_{0}$ is small, we
will reduce it to the potential function $\Gamma$ used in [32]:

$\Gamma^{(s)}:=\sum_{i=1}^{n}\left(\exp\bigl{(}\alpha(x_{i}^{(s)}-s/n)\bigr{)}+\exp\bigl{(}-\alpha(x_{i}^{(s)}-s/n)\bigr{)}\right),$

for some constant $0<\alpha<1/(6\cdot 12)$. Note that if $\alpha=\alpha_{2}$,
then $\Phi_{0}^{(s)}\leqslant\Gamma^{(s)}$, so it suffices to upper bound
$\Gamma^{(s)}$. It is crucial that this potential includes both the
$\exp(\alpha(\cdot))$ and $\exp(-\alpha(\cdot))$ terms, as otherwise the
potential may not decrease, even if it is large (see [32, Appendix]).

######  Lemma 5.4 (Theorem 2.9 and 2.10 in [32]).

For any process satisfying the conditions of 5.3, $(i)$ for any $t\geqslant
0$,

$\mathbf{E}\left[\,\Gamma^{(t+1)}\mid\Gamma^{(t)}\,\right]\leqslant\Big{(}1-\frac{\varepsilon^{\prime}_{\alpha}}{n}\Big{)}\cdot\Gamma^{(t)}+c^{\prime},$

where $\varepsilon^{\prime}_{\alpha}:=\frac{\alpha\varepsilon}{4}$ and
$c^{\prime}:=\frac{40\cdot 128^{3}}{\varepsilon^{5}}$. Furthermore, $(ii)$ for
any $t\geqslant 0$, $\mathbf{E}\left[\,\Gamma^{(t)}\,\right]\leqslant cn$.

To obtain the stronger statement that $\Gamma^{(t)}=\mathcal{O}(n)$ w.h.p., we
will be using two instances of the potential function: $\Gamma_{1}$ with
$\alpha_{1}=0.01$ and $\Gamma_{2}$ with $\alpha_{2}=0.0002$; so
$\Gamma_{1}\geqslant\Gamma_{2}$. The interplay between these two potentials is
shown in Fig. 5. We pick $\alpha_{1}$ such that
$12.1\cdot\frac{\alpha_{1}}{\alpha_{2}}<\frac{1}{3}$ and hence the additive
change of $\Gamma_{2}$ (given $\Gamma_{1}$ is small) is at most $n^{1/3}$:

######  Lemma 5.5.

For any $t\geqslant 0$, if $\Gamma_{1}^{(t)}\leqslant cn^{9}$, then, $(i)$
$\bigl{|}x_{i}^{(t)}-\frac{t}{n}\bigr{|}\leqslant\frac{9.1}{\alpha_{1}}\log n$
for all $i\in[n]$, $(ii)$ $\Gamma_{2}^{(t)}\leqslant n^{4/3},$ and, $(iii)$
$|\Gamma_{2}^{(t+1)}-\Gamma_{2}^{(t)}|\leqslant n^{1/3}.$

The precondition of 5.5 is easy to satisfy thanks to 5.4 and Markov’s
inequality. The next lemma proves a weaker version of 5.3, in the sense that
the potential $\Gamma_{2}^{(s)}$ is small in _at least_ one step. Note that
due to the choice of $\alpha_{1}$ and $\alpha_{2}$, we have
$c>\frac{2c^{\prime}}{\varepsilon^{\prime}_{\alpha_{2}}}$.

######  Lemma 5.6.

For any $t\geqslant n\log^{2}n$, for constants
$c^{\prime}>0,\varepsilon^{\prime}_{\alpha_{2}}>0$ defined as above,

$\mathbf{Pr}\left[\,\bigcup_{s\in[t-n\log^{2}n,t]}\\{\Gamma_{2}^{(s)}\leqslant\frac{2c^{\prime}}{\varepsilon^{\prime}_{\alpha_{2}}}\cdot
n\\}\,\right]\geqslant 1-2cn^{-8}.$

To prove the strong version that $\Gamma_{2}^{(s)}$ is small at _all_ time-
steps in $[t,t+n\log^{5}n]$, we will use 5.6 to obtain a starting point
$s_{0}$. For the following time-steps, we bound the expected value of
$\Gamma_{2}^{(s)}$ for $s\geqslant s_{0}$, using 5.4. Then we apply a
concentration inequality for supermartingales (Theorem A.4), and use the
bounded difference $|\Gamma_{2}^{(s+1)}-\Gamma_{2}^{(s)}|\leqslant n^{1/3}$
for all $s\geqslant t$ (5.5).

$t$$t+n\log^{2}n$$t+n\log^{5}n$$\Gamma_{1}^{(s)}\leqslant cn^{9}$ for all
$s\in[t,t+n\log^{5}n]$ (5.4 $(ii)$+Markov’s
Inequality)$\Gamma_{2}^{(t)}\leqslant n^{4/3}$$\exists
s_{0}:\Gamma_{2}^{(s_{0})}\leqslant cn$ w.h.p.$\Gamma_{2}^{(s)}\leqslant cn$
for all $s\in[s_{0},t+n\log^{5}n]$5.5 $(ii)$5.6Starting point Bounded
difference (5.5 $(iii)$) Expectation drop
(5.4 $(i)$) Completion of the Proof of 5.3 (Section 5.2) Figure 5: Outline for
the proof of 5.3. Results in green are used in the application of the
concentration inequality (A.4) in 5.3.

###  5.1 Tools for Theorem 5.3

See 5.5

###### Proof.

_First Statement._ For any bin $i\in[n]$,

$\Gamma_{1}^{(t)}\leqslant cn^{9}\Rightarrow
e^{\alpha_{1}\cdot(x_{i}^{(t)}-\frac{t}{n})}+e^{-\alpha_{1}\cdot(x_{i}^{(t)}-\frac{t}{n})}\leqslant
cn^{9}\Rightarrow x_{i}^{(t)}-\frac{t}{n}\leqslant\frac{9.1}{\alpha_{1}}\log
n\,\wedge\,\frac{t}{n}-x_{i}^{(t)}\leqslant\frac{9.1}{\alpha_{1}}\log n,$

where in the second implication we used $\log c+\frac{9}{\alpha_{1}}\log
n\leqslant\frac{9.1}{\alpha_{1}}\log n$, for sufficiently large $n$.

_Second Statement._ By the definition of $\Gamma_{2}^{(t)}$ and the bound on
each bin load,

$\Gamma_{2}^{(t)}<2\cdot\sum_{i=1}^{n}\exp\Big{(}\alpha_{2}\cdot\frac{9.1}{\alpha_{1}}\cdot\log
n\Big{)}\leqslant 2n\cdot n^{1/4}<n^{4/3}.$

_Third Statement._ Consider $\Gamma_{2}^{(t+1)}$ as a sum over $2n$
exponentials, which is obtained from $\Gamma_{2}^{(t)}$ by slightly changing
the values of the $2n$ exponents. The total $\ell_{1}$-change in the exponents
is upper bounded by $4$, as we will increment one entry in the load vector
$x^{(t)}$ (and this entry appears twice), and we will also increment the
average load by $\frac{1}{n}$ in all $2n$ exponents. Since $\exp(.)$ is
convex, the largest change is upper bounded by the (hypothetical) scenario in
which the largest exponent increases by $4$ and all others remain the same,

$\displaystyle\left|\Gamma_{2}^{(t+1)}-\Gamma_{2}^{(t)}\right|$
$\displaystyle\leqslant\exp\Big{(}\alpha_{2}\cdot\max\\{x_{\max}^{(t)}+4-t/n,t/n-x_{\min}^{(t)}-4\\}\Big{)}$
$\displaystyle\leqslant
e^{4\alpha_{2}}\cdot\exp\Big{(}\alpha_{2}\cdot\frac{9.1}{\alpha_{1}}\cdot\log
n\Big{)}=e^{4\alpha_{2}}\cdot\exp\Big{(}0.0002\cdot\frac{9.1}{0.01}\cdot\log
n\Big{)}\leqslant n^{1/3}.$

∎

######  Claim 5.7.

For any step $t\geqslant 0$,
$\mathbf{E}[\,\Gamma_{2}^{(t+1)}\,\mid\,\Gamma_{2}^{(t)},\Gamma_{2}^{(t)}\geqslant\frac{2c^{\prime}}{\varepsilon^{\prime}_{\alpha_{2}}}\cdot
n\,]\leqslant(1-\frac{\varepsilon^{\prime}_{\alpha_{2}}}{2n})\cdot\Gamma_{2}^{(t)}$.

###### Proof.

If
$\Gamma_{2}^{(t)}\geqslant\frac{2c^{\prime}}{\varepsilon^{\prime}_{\alpha_{2}}}\cdot
n$, then the inequality of 5.4 yields,

$\displaystyle\mathbf{E}[\,\Gamma_{2}^{(t+1)}\,\mid\,\Gamma_{2}^{(t)},\Gamma_{2}^{(t)}\geqslant\frac{2c^{\prime}}{\varepsilon^{\prime}_{\alpha_{2}}}\cdot
n\,]$
$\displaystyle\leqslant\Gamma_{2}^{(t)}-\frac{\varepsilon^{\prime}_{\alpha_{2}}}{n}\cdot\Gamma_{2}^{(t)}+c^{\prime}$
$\displaystyle\leqslant\Gamma_{2}^{(t)}-\frac{\varepsilon^{\prime}_{\alpha_{2}}}{2n}\cdot\Gamma_{2}^{(t)}+\Big{(}c^{\prime}-\frac{\varepsilon^{\prime}_{\alpha_{2}}}{2n}\cdot\Gamma_{2}^{(t)}\Big{)}\leqslant\Big{(}1-\frac{\varepsilon^{\prime}_{\alpha_{2}}}{2n}\Big{)}\cdot\Gamma_{2}^{(t)}.$

∎

See 5.6 The proof of this lemma relies on the two statements in 5.4.

###### Proof.

By 5.4, using Markov’s inequality at time $t-n\log^{2}n$, we have

$\mathbf{Pr}\left[\,\Gamma_{1}^{(t-n\log^{2}n)}\leqslant
cn^{9}\,\right]\geqslant 1-cn^{-8}.$

Assuming $\Gamma_{1}^{(t-n\log^{2}n)}\leqslant cn^{9}$, then the second
statement of 5.5 implies $\Gamma_{2}^{(t-n\log^{2}n)}\leqslant n^{4/3}$. By
5.7 if at some step
$\Gamma_{2}^{(r)}>\frac{2c^{\prime}}{\varepsilon^{\prime}_{\alpha_{2}}}\cdot
n$, then

$\mathbf{E}\left[\,\Gamma_{2}^{(r+1)}\,\mid\,\Gamma_{2}^{(r)}\,\right]\leqslant(1-\frac{\varepsilon^{\prime}_{\alpha_{2}}}{2n})\cdot\Gamma_{2}^{(r)}.$

For any $r\in[t-n\log^{2}n,t]$, we define the “killed” potential function,

$\widetilde{\Gamma}_{2}^{(r)}:=\Gamma_{2}^{(r)}\cdot\mathbf{1}_{\bigcap_{\widetilde{r}\in[t-n\log^{2}n,r]}\\{\Gamma_{2}^{(\widetilde{r})}>\frac{2c^{\prime}}{\varepsilon^{\prime}_{\alpha_{2}}}\cdot
n\\}}.$

This satisfies the inequality of 5.4 without any constraint on the value of
$\widetilde{\Gamma}_{2}^{(r)}$, that is,

$\mathbf{E}\left[\,\widetilde{\Gamma}_{2}^{(r+1)}\,\mid\,\widetilde{\Gamma}_{2}^{(r)}\,\right]\leqslant(1-\frac{\varepsilon^{\prime}_{\alpha_{2}}}{2n})\cdot\widetilde{\Gamma}_{2}^{(r)}.$

Inductively applying this for $n\log^{2}n$ steps, and noting that
$\varepsilon^{\prime}_{\alpha_{2}}=\frac{\alpha_{2}\varepsilon}{4}<1$,

$\mathbf{E}\left[\,\widetilde{\Gamma}_{2}^{(t)}\mid\widetilde{\Gamma}_{2}^{(t-n\log^{2}n)}\,\right]\leqslant
e^{-\frac{n\log^{2}n}{n}}\cdot n^{4/3}\leqslant n^{-7}.$

So, by Markov’s inequality,

$\mathbf{Pr}\left[\,\widetilde{\Gamma}_{2}^{(t)}\geqslant
n\,\mid\,\Gamma_{1}^{(t-n\log^{2}n)}\leqslant cn^{9}\,\right]\leqslant
n^{-{8}}\Rightarrow\mathbf{Pr}\left[\,\widetilde{\Gamma}_{2}^{(t)}\geqslant
n\,\right]<2cn^{-8}.$

Due to the definition of $\widetilde{\Gamma}_{2}$ we conclude that w.p. at
least $1-2cn^{-8}$, there must be at least one time step
$s\in[t-n\log^{2}n,t]$,
$\Gamma_{2}^{(s)}\leqslant\frac{2c^{\prime}}{\varepsilon^{\prime}_{\alpha_{2}}}\cdot
n$. ∎

###  5.2 Completing the proof of Theorem 5.3

See 5.3

###### Proof.

The proof will be concerned with time-steps $\in[t-n\log^{2}n,t+n\log^{5}n]$.
First, by applying 5.6,

$\displaystyle\mathbf{Pr}\left[\,\bigcup_{s\in[t-n\log^{2}n,t]}\\{\Gamma_{2}^{(s)}\leqslant\frac{2c^{\prime}}{\varepsilon^{\prime}_{\alpha_{2}}}\cdot
n\\}\,\right]$ $\displaystyle\geqslant 1-2cn^{-8}.$

Assuming that such a time $s\in[t-n\log^{2}n,t]$ indeed exists, we partition
the time-steps $r\in[s,t+n\log^{5}n]$ into red and green phases (see Fig. 6):

  1. 1.

Red Phase: The process at step $r$ is in a red phase if
$\Gamma_{2}^{(r)}>\frac{2c^{\prime}}{\varepsilon^{\prime}_{\alpha_{2}}}\cdot
n=:T$.

  2. 2.

Green Phase: Otherwise, the process is in a green phase.

Figure 6: Green phases indicate time-steps where $\Gamma_{2}^{(r)}$ is small
and red phases indicate time-steps for which the potential is large and drops
(in expectation). The main objective is to prove a $<3cn/2$ guarantee at every
point within a red phase using a concentration inequality.

Note that by the choice of $s$, the process is at a green phase at time $s$,
which means that every red phase is preceded by a green phase. Obviously, for
steps in a green phase, we have $\Gamma_{2}^{(r)}\leqslant T$. Hence for $r$
being a (possible) first step of a red phase after a green phase, it follows
that $\Gamma_{2}^{(r+1)}\leqslant e^{\alpha_{2}}\cdot\Gamma_{2}^{(r)}\leqslant
2\cdot\Gamma_{2}^{(r)}$, and therefore

$\displaystyle\Gamma_{2}^{(r+1)}\leqslant 2\cdot T.$ (5.1)

The remaining part of the proof is to analyze $\Gamma_{2}^{(r)}$ during the
time steps of a red phase, and to establish that
$\Gamma_{2}^{(r)}=\mathcal{O}(n)$ holds for all $r\in[s,t+n\log^{5}n]$ (see
Fig. 6).

The idea of this partitioning is that within a red phase, i.e.,
$\Gamma_{2}^{(r)}\geqslant\frac{2c^{\prime}n}{\varepsilon^{\prime}_{\alpha_{2}}}$,
so by 5.7,

$\displaystyle\mathbf{E}\left[\,\Gamma_{2}^{(r+1)}\mid\Gamma_{2}^{(r)}\geqslant\frac{2c^{\prime}n}{\varepsilon^{\prime}_{\alpha_{2}}}\,\right]\leqslant\Gamma_{2}^{(r)}.$
(5.2)

In order to analyze the behavior of $\Gamma_{2}$ till the end of a red phase,
we define for every $r\in[s,t+n\log^{5}n]$ being the (potential) beginning of
a red phase, a stopping time $\tau(r):=\min\\{u\geqslant
r\colon\Gamma_{2}^{(u)}\leqslant\frac{2c^{\prime}n}{\varepsilon^{\prime}_{\alpha_{2}}}\\}$.
Further, define

$X_{r}^{(u)}:=\Gamma_{2}^{(u\wedge\tau_{r})}.$

Our goal is to apply a concentration inequality for supermartingales (A.4) to
$X_{r}^{(u)}$. As a preparation, we will first derive some basic bounds for
$\Gamma_{1}^{(r)}$. For any time step $r\in[t-n\log^{2}n,t+n\log^{5}n]$,
applying 5.4 and using Markov’s inequality, we have that
$\mathbf{Pr}\left[\,\Gamma_{1}^{(r)}\leqslant cn^{9}\,\right]\geqslant
1-cn^{-8}$. Hence, by the union bound over $[t-n\log^{2}n,t+n\log^{5}n]$,

$\mathbf{Pr}\left[\,\bigcap_{u\in[t-n\log^{2}n,t+n\log^{5}n]}\\{\Gamma_{1}^{(u)}\leqslant
cn^{9}\\}\,\right]\geqslant 1-\frac{2\log^{5}n}{n^{7}}.$

Following the notation in A.4, we set
$\overline{B^{(r)}}:=\bigcap_{u\in[r,t+n\log^{5}n]}\\{\Gamma_{1}^{(u)}\leqslant
cn^{9}\\}$. As for the three preconditions in A.4, we obtain by choice of
$\overline{B^{(r)}}$:

  1. 1.

$\mathbf{E}[\,X_{r}^{(u)}\mid\mathcal{F}_{r}^{(u-1)}\,]\leqslant
X_{r}^{(u-1)}$. This holds, since if event $\overline{B^{(r)}}$ occurs, we can
apply 5.7 to deduce that Eq. 5.2 holds.

  2. 2.

$\displaystyle\mathbf{Var}[\,X_{i}^{(u)}\mid\mathcal{F}_{i}^{(u-1)}\,]$
$\displaystyle\leqslant\frac{1}{4}\big{|}\bigl{(}\max X_{i}^{(u)}-\min
X_{i}^{(u)}\bigr{)}\,\mid\,\mathcal{F}_{i}^{(u-1)}\bigr{|}^{2}$
$\displaystyle\leqslant\frac{1}{4}\big{|}\bigl{(}\max X_{i}^{(u)}-\min
X_{i}^{(u)}\bigr{)}\,\mid\,\mathcal{F}_{i}^{(u-1)}\bigr{|}^{2}\leqslant
n^{2/3},$

where the first inequality follows by Popovicius’ inequality, the second and
third by the triangle inequality and 5.5 (third statement).

  3. 3.

$X_{r}^{(u)}-\mathbf{E}[\,X_{r}^{(u)}\mid\mathcal{F}_{r}^{(u-1)}\,]\leqslant\bigl{|}\Gamma_{2}^{(u)}-\Gamma_{2}^{(u-1)}\bigr{|}\mid\mathcal{F}_{r}^{(u-1)}\leqslant
2n^{1/3}$ by 5.5 (third statement).

Since each possible red phase will end before $t+2n\log^{5}n$, applying A.4
for any $u\in[r,t+2n\log^{5}n]$ gives

$\mathbf{Pr}\left[\,X_{r}^{(u)}\geqslant
X_{r}^{(r)}+\frac{cn}{2}\,\right]\leqslant\exp\left(-\frac{c^{2}n^{2}/4}{2\cdot(2n\log^{5}n)\cdot(2n^{1/3})}\right)+\frac{2\log^{5}n}{n^{7}}\leqslant\frac{3\log^{5}n}{n^{7}}.$

Also recall that $X_{r}^{(r)}\leqslant 2T\leqslant cn$ by Eq. 5.1, so if a red
phase starts at time $r$, then with probability $1-\frac{3\log^{5}n}{n^{7}}$,
$\Gamma_{2}^{(u)}$ will always be $\leqslant\frac{3cn}{2}$. Now taking the
union bound over $u\in[r,t+2n\log^{5}n]$ and taking a union bound over all
possible starting points of a red phase yields:

$\mathbf{Pr}\left[\,\bigcup_{r\in[s,t+n\log^{5}n]}\bigcup_{u\in[r,t+n\log^{5}n]}\\{X_{r}^{(u)}>\frac{3cn}{2}\\}\,\right]\leqslant
3\cdot\frac{\log^{5}n}{n^{7}}\cdot(4n^{2}\log^{10}n)\leqslant\frac{1}{2}n^{-4}.$

Hence with probability $1-\frac{1}{2}n^{-4}-2cn^{-8}\geqslant 1-n^{-4}$, it
holds that $\Gamma_{2}^{(r)}\leqslant\frac{3cn}{2}$ for all time-steps $r$
which are within a red phase in $[s,t+n\log^{5}n]\subseteq[t,t+n\log^{5}n]$.
Since $\Gamma_{2}^{(r)}\leqslant T\leqslant cn$ holds (deterministically) by
definition for all time-steps $r$ within a green phase, the theorem follows.∎

##  6 Upper Bounds for More Than One Quantile

###  6.1 Upper Bounds on the Original Quantile Process and Consequences

We now generalize the analysis from Section 5 for one quantile to $2\leqslant
k\leqslant\kappa\cdot\log\log n$ quantiles, where $\kappa:=1/\log(10^{4})$. We
emphasize that our chosen quantiles are oblivious and even uniform, i.e.,
independent of $t$ (but dependent on $n$). Specifically, we define

$\widetilde{\delta}_{i}=\begin{cases}\frac{1}{2}&\quad\text{ for }i=k,\\\
2^{-0.5(\log n)^{(k-i)/k}}&\quad\text{ for $1\leqslant i<k$ },\end{cases}$

and let each $\delta_{i}$ be $\widetilde{\delta}_{i}$ rounded up to the
nearest multiple of $\frac{1}{n}$. The intuition is that the largest quantile
$\delta_{k}=\frac{1}{2}$ ensures that the load distribution is at least
“coarsely” balanced, analogous to the $(1+\beta)$-process. All smaller
quantiles $\delta_{1},\delta_{2},\ldots,\delta_{k-1}$ almost always returns a
negative answer, but they gradually reduce the probability of allocating to a
heavily loaded bin.

######  Theorem 6.1 (simplified version of Theorem 6.6).

For any integer $2\leqslant k\leqslant\kappa\log\log n$, consider the
$\textsc{Quantile}(\delta_{1},\delta_{2},\ldots,\delta_{k})$ process with the
$\delta_{i}$’s defined above. Then for any $m\geqslant 1$,

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\leqslant 1000\cdot k\cdot(\log
n)^{1/k}\,\right]\geqslant 1-n^{-3}.$

For $k=2$ and $k=3$, 6.1 directly implies the following corollary:

######  Corollary 6.2.

For $k=2$, the process $\textsc{Quantile}(2^{-0.5\sqrt{\log n}},\frac{1}{2})$
satisfies for any $m\geqslant 1$,

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\leqslant 2000\cdot\sqrt{\log
n}\,\right]\geqslant 1-n^{-3}.$

Similarly, for $k=3$ the process $\textsc{Quantile}(2^{-0.5(\log
n)^{2/3}},2^{-0.5(\log n)^{1/3}},\frac{1}{2})$ satisfies for any $m\geqslant
1$,

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\leqslant 3000\cdot(\log
n)^{1/3}\,\right]\geqslant 1-n^{-3}.$

Using the fact that any allocation process with $k$ quantiles majorizes a
suitable adaptive (and randomized) $2k$-Thinning process (3.9), we also
obtain:

######  Corollary 6.3.

For any even $d\leqslant\frac{2}{\kappa}\log\log n$, there is an (adaptive and
randomized) $d$-Thinning process, satisfying for any $m\geqslant 1$,
$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\leqslant 2000\cdot d\cdot(\log
n)^{(2/d)}\,\right]\geqslant 1-n^{-3}.$

In particular for the $d$-Thinning process where the $j$-th decision is given
by the quantile $\delta_{j}$, we get an extension of [20, Theorem 1.1] to the
heavily-loaded case

######  Lemma 6.4.

Consider the $d$-Thinning process for $d<\kappa\log\log n$ induced by the
quantiles $\delta_{1},\ldots,\delta_{d-1}$, given by $\delta_{j}=2^{-0.5(\log
n)^{j/(d-1)}}$. Then there is a constant $c>0$ such that for every $m\geqslant
1$,

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\leqslant c\cdot(d-1)\cdot(\log
n)^{1/(d-1)}\,\right]\geqslant 1-n^{-2}.$

###### Proof.

We will show that this $d$-Thinning process is majorized by the
$\textsc{Quantile}(\delta_{1},\ldots,\delta_{d-1})$ process. We consider two
cases for bins $i\in[n]$:

  * •

Case 1 [$i\leqslant n\cdot\delta_{1}$]: We allocate to $i\leqslant
n\cdot\delta_{1}$ if the first $d$ samples are heavy and the last one is equal
to $i$. So,

$p_{i}=\delta_{1}\cdot\delta_{2}\cdot\ldots\cdot\delta_{d}\cdot\frac{1}{n}\leqslant\frac{\delta_{1}}{n}.$

  * •

Case 2 [$j<d-1$, $n\cdot\delta_{j}<i\leqslant n\cdot\delta_{j+1}$]: Let
$j_{1},\ldots,j_{d}$ be the sampled bins. The probability of allocating to $i$
is if the first $\ell_{1}\geqslant j$ samples where heavy and then we picked
$i$:

$\displaystyle p_{i}$
$\displaystyle=\frac{1}{n}\cdot\sum_{\ell_{1}=j}^{k}\prod_{\ell_{2}=1}^{\ell_{1}}\mathbf{Pr}\left[\,j_{\ell_{2}}\leqslant
n\cdot\delta_{\ell_{2}}\,\right]$
$\displaystyle=\frac{1}{n}\cdot\delta_{1}\cdot\ldots\cdot\delta_{j}\cdot(1+\delta_{j+1}+\delta_{j+1}\cdot\delta_{j+2}+\ldots+\delta_{j+1}\cdot\ldots\cdot\delta_{k})$
$\displaystyle\leqslant\frac{1}{n}\cdot\delta_{1}\cdot\ldots\cdot\delta_{j}\cdot\Big{(}1+\delta_{j+1}+\delta_{j+1}\cdot\frac{1}{2}+\delta_{j+1}\cdot\frac{1}{2^{2}}+\ldots\Big{)}$
$\displaystyle\leqslant\frac{1}{n}\cdot\delta_{j}\cdot(1+2\delta_{j+1})$
$\displaystyle\leqslant\frac{1}{n}\cdot(\delta_{j}+2\cdot\delta_{j}\cdot\delta_{j+1})$
$\displaystyle\leqslant\frac{1}{n}\cdot(\delta_{j}+\delta_{j+1}),$

using that $\delta_{j}\leqslant 1/2$ for any $j$.

Hence, by 6.1 majorization the $d$-Thinning process w.h.p. has an
$\mathcal{O}((d-1)\cdot(\log n)^{1/(d-1)})$ gap. ∎

Finally, for $k=\Theta(\log\log n)$, the bound on the gap in 6.1 is
$C\cdot\log\log n$ for some (large) constant $C>0$. Surprisingly, this matches
the gap of the full information setting (Two-Choice process), even though the
Quantile process behaves quite differently. For instance, Quantile cannot
discriminate among the $n/2$ most lightly loaded bins. Also since any Quantile
process majorizes Two-Choice (see 3.5), we deduce:

######  Corollary 6.5.

For Two-Choice, there is a constant $C>0$ such that for any $m\geqslant 1$,
$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\leqslant C\log\log
n\,\right]\geqslant 1-n^{-3}.$

This result originally shown in [10] proved the tighter bound
$\operatorname{Gap}(m)=\log_{2}\log n\pm\mathcal{O}(1)$, w.h.p. However, their
analysis combines sophisticated tools from Markov chain theory and computer-
aided calculations. The simpler analysis in [37] derives the same gap bound up
to an additive $\mathcal{O}(\log\log\log n)$ term, but the error probability
is much larger, i.e., $\Theta((\log\log n)^{-4})$. In comparison to their
bound, our result achieves a much smaller error probability of
$\mathcal{O}(n^{-3})$, but it comes at the cost of a multiplicative constant
in the gap bound.

###  6.2 Relaxed Quantile Process and Outline of the Inductive Step

We now define a class of processes $\textsc{Relaxed-
Quantile}_{\gamma}(\delta_{1},\ldots,\delta_{k})$, which relaxes the
definition of $\textsc{Quantile}{(\delta_{1},\ldots,\delta_{k})}$, with
$1\leqslant k\leqslant\kappa\log\log n$ and a relaxation factor
$\gamma\geqslant 1$. The probability vector $p$ of such a process satisfies
four conditions: $(i)$, for each $i\in[n]$,

$p_{i}\leqslant\begin{cases}\gamma\cdot\frac{\delta_{1}}{n}&\text{for
}1\leqslant i\leqslant\delta_{1}\cdot n,\\\
\gamma\cdot\frac{\delta_{1}+\delta_{2}}{n}&\text{for }\delta_{1}\cdot
n<i\leqslant\delta_{2}\cdot n,\\\ \ \ \ \vdots&\\\
\gamma\cdot\frac{\delta_{k-1}+\delta_{k}}{n}&\text{for }\delta_{k-1}\cdot
n<i\leqslant\delta_{k}\cdot n,\\\ \end{cases}$

$(ii)$ the probability vector $p$ is non-decreasing in $i$, $(iii)$
$p_{n/3}\leqslant\frac{1-4\varepsilon}{n}$ and, $(iv)$
$p_{2n/3}\geqslant\frac{1+4\varepsilon}{n}$ for some $0<\varepsilon<1/4$. Note
that the process $\textsc{Quantile}(\delta_{1},\delta_{2},\ldots,\delta_{k})$
with the $\delta_{i}$’s as defined above falls into this class with $\gamma=1$
and $\varepsilon=1/12$ (cf. Eq. 3.1).

######  Theorem 6.6 (generalization of Theorem 6.1).

Consider a $\textsc{Relaxed-
Quantile}_{\gamma}(\delta_{1},\delta_{2},\ldots,\delta_{k})$ process with the
$\delta_{i}$’s defined above. Let $2\leqslant k\leqslant\kappa\log\log n$ and
$1\leqslant\gamma\leqslant 6$. Then for any $m\geqslant 1$,

$\mathbf{Pr}\left[\,\operatorname{Gap}(m)\leqslant 1000\cdot k\cdot(\log
n)^{1/k}\,\right]\geqslant 1-n^{-3}.$

##### Reduction of 6.6 to 6.7.

The proof of 6.6 employs some type of layered induction over $k$ different,
super-exponential potential functions. Generalizing the definition of
$\Phi_{0}^{(s)}$ from Section 5, for any $0\leqslant j\leqslant k-1$:

$\Phi_{j}^{(s)}:=\sum_{i=1}^{n}\exp\Big{(}\alpha_{2}\cdot(\log
n)^{j/k}\cdot\Big{(}x_{i}^{(s)}-\frac{s}{n}-\frac{2}{\alpha_{2}}j(\log
n)^{1/k}\Big{)}^{+}\Big{)},$

where $\alpha_{2}=0.0002$ (recall $z^{+}=\max\\{z,0\\}$). We will then employ
this series of potential functions $j=0,1,\ldots,k-1$ to analyze the process
over the time-interval $s\in[m-n\log^{5}n,m]$.

The next lemma (6.7) formalizes this inductive argument. It shows that if for
all steps $s$ within some suitable time-interval, the number of balls of
height at least $\frac{s}{n}+\frac{2}{\alpha_{2}}j(\log n)^{1/k}$ is small,
then the number of balls of height at least
$\frac{s}{n}+\frac{2}{\alpha_{2}}(j+1)(\log n)^{1/k}$ is even smaller. This
“even smaller” is encapsulated by the (non-constant) base of $\Phi_{j}$, which
increases in $j$; however, this comes at the cost of reducing the time-
interval slightly by a $\Theta(n\log^{3}n)$ term. Finally, for $j=k-1$, we can
conclude that at step $s=m$, there are no balls of height
$\frac{s}{n}+\frac{2}{\alpha_{2}}k(\log n)^{1/k}$. Hence we can infer that the
gap is $\mathcal{O}(k\cdot(\log n)^{1/k})$, and 6.1 follows (see Section 6.6
for the complete proof of this step).

######  Lemma 6.7 (Inductive Step).

Assume that for some $1\leqslant j\leqslant
k\leqslant\frac{1}{\log(10^{4})}\log\log n$, the process $\textsc{Relaxed-
Quantile}_{\gamma}(\delta_{1},\ldots,\delta_{k})$ with the $\delta_{i}$’s as
defined before, and $\gamma\leqslant 6$ and $t\geqslant 0$ satisfies:

$\mathbf{Pr}\left[\,\bigcap_{s\in[\beta_{j-1},t+n\log^{5}n]}\\{\Phi_{j-1}^{(s)}\leqslant
2cn\\}\,\right]\geqslant 1-\frac{(\log n)^{8(j-1)}}{n^{4}},$

where $\beta_{j}:=t+2jn\log^{3}n$ and $c=c_{1/12,\alpha_{2}}$ (see 5.3). Then,
it also satisfies:

$\mathbf{Pr}\left[\,\bigcap_{s\in[\beta_{j},t+n\log^{5}n]}\\{\Phi_{j}^{(s)}\leqslant
2cn\\}\,\right]\geqslant 1-\frac{(\log n)^{8j}}{n^{4}}.$

As in Section 5, we will also use a second version of the potential function
to extend an expected bound on the potential into a w.h.p. bound. Intuitively,
we exploit the property that potential functions will have linear expectations
for a range of coefficients. With this in mind, we define the following
potential function for any $0\leqslant j\leqslant k-1$,

$\displaystyle\Psi_{j}^{(s)}:=\sum_{i=1}^{n}\exp\Big{(}\alpha_{1}\cdot(\log
n)^{j/k}\cdot\Big{(}x_{i}^{(s)}-\frac{s}{n}-\frac{2}{\alpha_{2}}j(\log
n)^{1/k}\Big{)}^{+}\Big{)},$

where $\alpha_{1}=0.01$. Note that $\Psi_{j}$ is defined in the same way as
$\Phi_{j}$ with the only difference that $\alpha_{1}$ is significantly larger
$\alpha_{2}$. The interplay between $\Psi_{j}$ and $\Phi_{j}$ is similar to
the interplay between $\Gamma_{1}$ and $\Gamma_{2}$ in the proof of 5.3, but
some extra care is needed. In particular, while underloaded bins with load of
$m/n-\Theta(\log n)$ contribute heavily to $\Gamma_{1}$ (or $\Gamma_{2}$),
their contribution has to be eliminated here in order to derive a gap bound
better than $\mathcal{O}(\log n)$.

###  6.3 Proof Outline of Lemma 6.7.

$\beta_{j-1}$$\beta_{j-1}+n\log^{3}n$$\beta_{j}$$t+n\log^{5}n$$\Phi_{j-1}^{(s)}\leqslant
2cn$ for all $s\in[\beta_{j-1},t+n\log^{5}n]$ (Inductive
hypothesis)$\Psi_{j}^{(\beta_{j-1})}\leqslant e^{0.01\log^{3}n}$$\exists
s_{0}:\mathbf{E}[\,\widetilde{\Psi}_{j}^{(s_{0})}\,]\leqslant
cn$$\mathbf{E}[\,\widetilde{\Psi}_{j}^{(s)}\,]\leqslant cn$ for all
$s\in[s_{0},t+n\log^{5}n]$$\widetilde{\Psi}_{j}^{(s)}\leqslant cn^{12}$ w.h.p.
for all
$s\in[\beta_{j-1}+n\log^{3}n,t+n\log^{5}n]$$\widetilde{\Phi}_{j}^{(\beta_{j-1}+n\log^{3}n)}\leqslant
n^{4/3}$$\exists r_{0}:\widetilde{\Phi}_{j}^{(r_{0})}\leqslant cn$
w.h.p.$\Phi_{j}^{(s)}\leqslant 2cn$ for all $s\in[r_{0},t+n\log^{5}n]$
(Inductive step)6.146.116.12Markov & U.-Bound6.15 (ii)6.13Starting point
Bounded difference (6.15 (i)) Expectation drop
using 6.9 Completion of the Proof of 6.7 (Section 6.5) Figure 7: Outline for
the proof of 6.7. Results in blue are given in Section 6.4, while results in
green are used in the application of the concentration inequality (A.4) in
Section 6.5.

We will now give a summary of the main technical steps in the proof of 6.7 (an
illustration of the key steps is shown in Fig. 7). On a high level, the proof
mirrors the proof of 5.3; however, there are some differences, especially in
the final part of the proof.

First, fix any $1\leqslant j\leqslant k-1$. Then the inductive hypothesis
ensures that $\Phi_{j-1}^{(r)}$ is small for $r\in[\beta_{j-1},t+n\log^{5}n]$.
From that, it follows by a simple estimate that
$\Psi_{j}^{(\beta_{j-1})}\leqslant e^{0.01\log^{3}n}$ (6.14). Using a
multiplicative drop (6.9) repeatedly, it follows that there exists
$u\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]$,
$\mathbf{E}[\,\Psi_{j}^{(u)}\,]\leqslant cn$ (6.11). Then by 6.12, this
statement is extended to the time-interval
$[\beta_{j-1}+n\log^{3}n,t+n\log^{5}n]$. By simply using Markov’s inequality
and a union bound, we can deduce that $\Psi_{j}^{(r)}\leqslant cn^{12}$ for
all $r\in[\beta_{j-1}+n\log^{3}n,t+n\log^{5}n]$. By a simple relation between
two potentials, this implies $\Phi_{j}^{(r)}\leqslant n^{4/3}$ (6.15 (ii)).
Now using a multiplicative drop (6.9) guarantees that this becomes
$\Phi_{j}^{(r)}\leqslant cn$ w.h.p. for _a single_ time-step
$r\in[\beta_{j-1},\beta_{j}]$ (6.13).

To obtain the stronger statement which holds for all time-steps
$r\in[\beta_{i-1},\beta_{j}]$, we will use a concentration inequality. The key
point is that whenever $\Psi_{j}^{(s)}\leqslant cn^{12}$, then the absolute
difference $|\Phi_{j}^{(s+1)}-\Phi_{j}^{(s)}|$ is at most $n^{1/3}$, because
$12.1\frac{\alpha_{2}}{\alpha_{1}}<1/3$ (6.15 (ii)). This is crucial so that
applying the supermartingale concentration bound A.4 from [12] to $\Phi_{j}$
yields an $\mathcal{O}(n)$ guarantee for the entire time interval.

In Section 6.4 we collect and prove all lemmas and claims mentioned above.
After that, in Section 6.5 we use these lemmas to complete the Proof of 6.7.

###  6.4 Auxiliary Definitions and Claims for the proof of Lemma 6.7

In the following, we will always implicitly assume that $1\leqslant j\leqslant
k-1$, as the base case $j=0$ has been done. We define the following event,
which will be used frequently in the proof:

$\mathcal{E}_{j-1}^{(s)}:=\left\\{\Phi_{j-1}^{(s)}\leqslant 2cn\right\\}.$

Recall that the induction hypothesis asserts that $\mathcal{E}_{j-1}^{(s)}$
holds for all steps $s\in[\beta_{j-1},t+n\log^{5}n]$. In the following
arguments we will be working frequently with the “killed” versions of the
potentials, i.e., we condition on $\mathcal{E}_{j-1}^{(s)}$ holding on all
time steps:

$\widetilde{\Phi}_{j}^{(s)}:=\Phi_{j}^{(s)}\cdot\mathbf{1}_{\cap_{r\in[\beta_{j-1},s]}\mathcal{E}_{j-1}^{(r)}}\text{
and
}\widetilde{\Psi}_{j}^{(s)}:=\Psi_{j}^{(s)}\cdot\mathbf{1}_{\cap_{r\in[\beta_{j-1},s]}\mathcal{E}_{j-1}^{(r)}}.$

As the proof of 6.7 requires several claims and lemmas, the remainder of this
section is divided further in:

  1. 1.

Analysis of the (expected) drop of the potentials $\Phi_{j}$ and $\Psi_{j}$.
(Section 6.4.1)

  2. 2.

Auxiliary (probabilistic) lemmas based on these drop results. (Section 6.4.2)

  3. 3.

(Deterministic) inequalities that involve one or two potentials. (Section
6.4.3)

After that, we proceed to complete the proof of 6.7 in Section 6.5.

####  6.4.1 Analysis of the Drop of the Potentials $\Phi_{j}$ and $\Psi_{j}$

We define $\alpha_{j}^{(s)}:=\frac{s}{n}+\frac{2}{\alpha_{2}}\cdot j(\log
n)^{1/k}$, so that when $\mathcal{E}_{j-1}^{(s)}$ holds, then
$y_{n\cdot\delta_{k-j}}^{(s)}\leqslant\alpha_{j}^{(s)}-1$; this will be
established in the next lemma below.

######  Lemma 6.8.

For any step $s\geqslant 1$, if $\mathcal{E}_{j-1}^{(s)}$ holds then
$y_{n\cdot\delta_{k-j}}^{(s)}\leqslant\alpha_{j}^{(s)}-1$.

###### Proof.

Assuming the opposite $y_{n\cdot\delta_{k-j}}^{(s)}>\alpha_{j}^{(s)}-1$, we
conclude

$\displaystyle\Phi_{j-1}^{(s)}$
$\displaystyle\geqslant\sum_{i=1}^{n\cdot\delta_{k-j}}\exp\Big{(}\alpha_{2}(\log
n)^{(j-1)/k}\cdot\Big{(}\alpha_{j}^{(s)}-\frac{s}{n}-\frac{2}{\alpha_{2}}\cdot(j-1)(\log
n)^{1/k}\Big{)}^{+}\Big{)}$ $\displaystyle\geqslant n\cdot 2^{-0.5(\log
n)^{j/k}}\cdot
e^{\alpha_{2}\cdot(\log{n})^{(j-1)/k}\cdot\frac{2}{\alpha_{2}}(\log n)^{1/k}}$
$\displaystyle\geqslant n\cdot 2^{-0.5(\log n)^{j/k}}\cdot
e^{2\cdot(\log{n})^{j/k}}$ $\displaystyle>2cn,$

since $(e^{2}\cdot 2^{-0.5})^{2\cdot(\log{n})^{j/k}}>(e^{2}\cdot
2^{-0.5})^{10^{4}}>2c$ for sufficiently large $n$, which contradicts
$\mathcal{E}_{j-1}^{(s)}$. ∎

######  Lemma 6.9.

For any step $s\geqslant\beta_{j-1}=t+2jn\log^{3}n$,

$\mathbf{E}\left[\,\Phi_{j}^{(s+1)}\,\big{|}\,\mathcal{E}_{j-1}^{(s)},\Phi_{j}^{(s)}\,\right]\leqslant\Big{(}1-\frac{1}{n}\Big{)}\cdot\Phi_{j}^{(s)}+2,$

and

$\mathbf{E}\left[\,\Psi_{j}^{(s+1)}\,\big{|}\,\mathcal{E}_{j-1}^{(s)},\Psi_{j}^{(s)}\,\right]\leqslant\Big{(}1-\frac{1}{n}\Big{)}\cdot\Psi_{j}^{(s)}+2.$

###### Proof.

We will prove the statement for the potential function $\Psi_{j}$. The same
proof holds for $\Phi_{j}$, since the only steps dependent on the coefficients
($\alpha_{1}$ vs. $\alpha_{2}$) are 6.8 to obtain the bound
$y_{n\cdot\delta_{k-j}}<\alpha_{j}^{(t)}-1$ and the facts that
$2^{0.5}>e^{0.01}>e^{\alpha_{2}}$ and $0.5\cdot\alpha_{1}\cdot(\log
n)^{j/k}>0.5\cdot\alpha_{2}\cdot(\log n)^{j/k}>1.2$ (which also hold for
$\alpha_{2}$).

In the following part of the proof, we will break down $\Psi_{j}^{(s+1)}$
(and, similarly, $\Psi_{j}^{(s)}$) as follows:

$\displaystyle\Psi_{j}^{(s+1)}=\sum_{i=1}^{n}\Psi_{j,i}^{(s+1)}$
$\displaystyle=\sum_{i=1}^{n}\exp\left(0.01(\log
n)^{j/k}\cdot(x_{i}^{(s+1)}-\alpha_{j}^{(s+1)})^{+}\right).$

Then we will split this sum into bins that have load at least (or less than)
$\alpha_{j}^{(s)}$, i.e.,

$\displaystyle\Psi_{j}^{(s+1)}$ $\displaystyle=\sum_{i\colon
x_{i}^{(s)}\geqslant\alpha_{j}^{(s)}}\Psi_{j,i}^{(s+1)}+\sum_{i\colon
x_{i}^{(s)}<\alpha_{j}^{(s)}}\Psi_{j,i}^{(s+1)}.$

After that we will apply linearity of expectation to bound the expected value
of the potential at step $s+1$.

Case 1: First, consider the contribution of a bin $i$ with
$x_{i}^{(s)}\geqslant\alpha_{j}^{(s)}$ to $\Psi_{j}^{(s+1)}$,

$\Psi_{j,i}^{(s+1)}=\begin{cases}\exp{\left(0.01(\log{n})^{j/k}(1-\frac{1}{n})\right)}\Psi_{j,i}^{(s)}&\quad\text{if
}x_{i}^{(s+1)}=x_{i}^{(s)}+1,\\\
\exp{\left(0.01(\log{n})^{j/k}\left(-\frac{1}{n}\right)\right)}\Psi_{j,i}^{(s)}&\quad\text{otherwise.}\end{cases}$

Define
$u_{i}:=\mathbf{Pr}\left[\,x_{i}^{(s+1)}=x_{i}^{(s)}+1\,\big{|}\,\mathcal{E}_{j-1}^{(s)},\Psi_{j}^{(s)}\,\right]$.
We have:

$\displaystyle\mathbf{E}\left[\,\Psi_{j,i}^{(s+1)}\,\big{|}\,\mathcal{E}_{j-1}^{(s)},\Psi_{j}^{(s)}\,\right]=e^{0.01(\log{n})^{j/k}(1-\frac{1}{n})}\cdot\Psi_{j,i}^{(s)}\cdot
u_{i}+e^{0.01(\log{n})^{j/k}(-\frac{1}{n})}\cdot\Psi_{j,i}^{(s)}\cdot(1-u_{i})$
$\displaystyle\quad=\left(e^{0.01(\log{n})^{j/k}(1-\frac{1}{n})}-e^{0.01(\log{n})^{j/k}(-\frac{1}{n})}\right)\cdot\Psi_{j,i}^{(s)}\cdot
u_{i}+e^{0.01(\log{n})^{j/k}(-\frac{1}{n})}\cdot\Psi_{j,i}^{(s)}.$

Note that since $y_{n\cdot\delta_{k-j}}^{(s)}\leqslant\alpha_{j}^{(s)}-1$ (see
6.8), bin $i$ must be among the $(\delta_{k-j})$-th heaviest bins. To
increment the load of bin $i$, $i$ has to be one of the two randomly chosen
bins, and the other choice must be a bin whose load is at most
$y_{n\cdot\delta_{k-j}}^{(s)}$, hence
$u_{i}\leqslant\frac{2}{n}\delta_{k-j}\leqslant\frac{3\gamma}{n}\widetilde{\delta}_{k-j}\leqslant\frac{18}{n}\widetilde{\delta}_{k-j}$
(see 6.10 below this lemma for details), which yields

$\displaystyle\mathbf{E}\left[\,\Psi_{j,i}^{(s+1)}\,\big{|}\,\mathcal{E}_{j-1}^{(s)},\Psi_{j}^{(s)}\,\right]$
$\displaystyle\quad\leqslant
e^{0.01(\log{n})^{j/k}(1-\frac{1}{n})}\cdot\Psi_{j,i}^{(s)}\cdot\frac{18}{n}\widetilde{\delta}_{k-j}+e^{0.01(\log{n})^{j/k}(-\frac{1}{n})}\cdot\Psi_{j,i}^{(s)}$
$\displaystyle\quad=e^{-0.01(\log{n})^{j/k}\frac{1}{n}}\cdot\Psi_{j,i}^{(s)}\cdot\left(1+\frac{18}{n}\cdot\frac{e^{0.01(\log{n})^{j/k}}}{2^{0.5(\log{n})^{j/k}}}\right)$
$\displaystyle\quad=\Psi_{j,i}^{(s)}\cdot\left(1-0.6\cdot\frac{0.01}{n}\cdot(\log
n)^{j/k}\right)\cdot\left(1+\frac{18}{n}\cdot\left(\frac{e^{0.01}}{2^{0.5}}\right)^{(\log{n})^{j/k}}\right)$
$\displaystyle\quad<\Psi_{j,i}^{(s)}\cdot\left(1-\frac{1.2}{n}\right)\cdot\left(1+\frac{0.06}{n}\right)$
$\displaystyle\quad<\Psi_{j,i}^{(s)}\cdot\left(1-\frac{1}{n}\right),$

where we have used that $e^{x}<1+0.6\cdot x$ for any $-1.1\leqslant x<0$ and
$(\log n)^{j/k}>\exp(\frac{1}{k}\log\log n)>\exp(\frac{\log(10^{4})}{\log\log
n}\cdot\log\log n)=10^{4}$ for sufficiently large $n$. In conclusion, we have
shown that for any bin $i$ with load $x_{i}^{(s)}\geqslant\alpha_{j}^{(s)}$,

$\mathbf{E}\left[\,\Psi_{j,i}^{(s+1)}\,\big{|}\,\mathcal{E}_{j-1}^{(s)},\Psi_{j}^{(s)}\,\right]\leqslant\Psi_{j,i}^{(s)}\cdot\left(1-\frac{1}{n}\right).$

Case 2: Let us now consider the contributions of a bin $i$ with
$x_{i}^{(s)}<\alpha_{j}^{(s)}$ to $\Psi_{j}^{(s+1)}$. Note that out of those
bins, only bins $i$ with $x_{i}^{(s)}\in[\alpha_{j}^{(s)}-1,\alpha_{j}^{(s)})$
can change the potential. Hence,

$\Psi_{j,i}^{(s+1)}\leqslant\begin{cases}\exp{\left(0.01(\log{n})^{j/k}(1-\frac{1}{n})\right)}&\quad\text{if
}x_{i}^{(s+1)}=x_{i}^{(s)}+1,\\\ 1&\quad\text{otherwise.}\end{cases}$

Since $y_{n\cdot\delta_{k-j}}\leqslant\alpha_{j}^{(s)}-1$, we can conclude as
in the previous case that such a bin $i$ is incremented with probability at
most $u_{i}\leqslant\frac{18}{n}\delta_{k-j}$, so

$\displaystyle\mathbf{E}\left[\,\Psi_{j,i}^{(s+1)}\,\big{|}\,\mathcal{E}_{j-1}^{(s)},\Psi_{j}^{(s)}\,\right]$
$\displaystyle\leqslant(1-u_{i})\cdot\Psi_{j,i}^{(s)}+u_{i}\cdot\exp\left(0.01(\log
n)^{j/k}(1-\frac{1}{n})\right)$ $\displaystyle\leqslant 1\cdot
1+\frac{18}{n}\widetilde{\delta}_{k-j}\cdot\exp\left(0.01(\log
n)^{j/k}(1-\frac{1}{n})\right).$

Combining the two cases, we find that

$\displaystyle\mathbf{E}\left[\,\Psi_{j}^{(s+1)}\,\big{|}\,\mathcal{E}_{j-1}^{(s)},\Psi_{j}^{(s)}\,\right]$
$\displaystyle=\sum_{i\colon
x_{i}^{(s)}\geqslant\alpha_{j}^{(s)}}\mathbf{E}\left[\,\Psi_{j,i}^{(s+1)}\,\big{|}\,\mathcal{E}_{j-1}^{(s)},\Psi_{j}^{(s)}\,\right]+\sum_{i\colon
x_{i}^{(s)}<\alpha_{j}^{(s)}}\mathbf{E}\left[\,\Psi_{j,i}^{(s+1)}\,\big{|}\,\mathcal{E}_{j-1}^{(s)},\Psi_{j}^{(s)}\,\right]$
$\displaystyle\leqslant\sum_{i\colon
x_{i}^{(s)}\geqslant\alpha_{j}^{(s)}}\Psi_{j,i}^{(s)}\cdot\left(1-\frac{1}{n}\right)$
$\displaystyle\quad\quad\quad+\sum_{i\colon
x_{i}^{(s)}<\alpha_{j}^{(s)}}\Psi_{j,i}^{(s)}+\frac{18}{n}\delta_{k-j}\cdot
e^{0.01(\log{n})^{j/k}(1-\frac{1}{n})}$
$\displaystyle\leqslant\Psi_{j}^{(s)}\cdot\left(1-\frac{1}{n}\right)+n\cdot\frac{18}{n}\cdot
2^{-0.5(\log n)^{j/k}}e^{0.01(\log n)^{j/k}}+1$
$\displaystyle\leqslant\Psi_{j}^{(s)}\cdot\left(1-\frac{1}{n}\right)+2,$

where the second inequality used the fact that $\Psi_{j,i}^{(s)}=1$ for
$x_{i}^{(j)}<\alpha_{j}^{(s)}$. ∎

######  Claim 6.10.

Let $\widetilde{\Phi}_{j}^{(s)}$, $\mathcal{E}_{j-1}^{(s)}$ and
$\alpha_{j}^{(s)}$ be defined as in 6.9. Then for any bin $i\in[n]$ with
$x_{i}^{(s)}\geqslant\alpha_{j}^{(s)}$, we get

$\mathbf{Pr}\left[\,x_{i}^{(s+1)}=x_{i}^{(s)}+1\,\big{|}\,\widetilde{\Phi}_{j}^{(s)},\mathcal{E}_{j-1}^{(s)},x_{i}^{(s)}\geqslant\alpha_{j}^{(s)}\,\right]\leqslant\frac{\gamma\delta}{n}.$

###### Proof.

By 6.8 we get, $x_{i}^{(s)}\geqslant\alpha_{j}^{(s)}\geqslant
y_{n\cdot\delta}^{(s)}$. By the definition of the process, incrementing bin
$i$ depends only on $\operatorname{Rank}^{(s)}(i)$.

$\mathbf{Pr}\left[\,x_{i}^{(s+1)}=x_{i}^{(s)}+1\,\big{|}\,\widetilde{\Phi}_{j}^{(s)},\mathcal{E}_{j-1}^{(s)},\operatorname{Rank}^{(s)}(i)=r\,\right]=\mathbf{Pr}\left[\,x_{i}^{(s+1)}=x_{i}^{(s)}+1\,\big{|}\,\operatorname{Rank}^{(s)}(i)=r\,\right]$

So,

$\displaystyle\mathbf{Pr}\left[\,x_{i}^{(s+1)}=x_{i}^{(s)}+1\,\big{|}\,\widetilde{\Phi}_{j}^{(s)},\mathcal{E}_{j-1}^{(s)},x_{i}^{(s)}\geqslant\alpha_{j}^{(s)}\,\right]$
$\displaystyle=\mathbf{Pr}\left[\,x_{i}^{(s+1)}=x_{i}^{(s)}+1\,\big{|}\,\widetilde{\Phi}_{j}^{(s)},\mathcal{E}_{j-1}^{(s)},x_{i}^{(s)}\geqslant\alpha_{j}^{(s)},\operatorname{Rank}^{(s)}(i)\leqslant
n\cdot\delta\,\right]$
$\displaystyle=\sum_{u}\mathbf{Pr}\left[\,x_{i}^{(s+1)}=x_{i}^{(s)}+1\,\big{|}\,\operatorname{Rank}^{(s)}(i)=u,\widetilde{\Phi}_{j}^{(s)},\mathcal{E}_{j-1}^{(s)},x_{i}^{(s)}\geqslant\alpha_{j}^{(s)},\operatorname{Rank}^{(s)}(i)\leqslant
n\cdot\delta\,\right]$
$\displaystyle\quad\quad\quad\quad\cdot\mathbf{Pr}\left[\,\operatorname{Rank}^{(s)}(i)=u\,\big{|}\,\widetilde{\Phi}_{j}^{(s)},\mathcal{E}_{j-1}^{(s)},x_{i}^{(s)}\geqslant\alpha_{j}^{(s)},\operatorname{Rank}^{(s)}(i)\leqslant
n\cdot\delta\,\right]$
$\displaystyle=\sum_{u:y_{u}^{(s)}\geqslant\alpha_{j}^{(s)}}\mathbf{Pr}\left[\,x_{i}^{(s+1)}=x_{i}^{(s)}+1\,\big{|}\,\operatorname{Rank}^{(s)}(i)=u\,\right]$
$\displaystyle\quad\quad\quad\quad\cdot\mathbf{Pr}\left[\,\operatorname{Rank}^{(s)}(i)=u\,\big{|}\,\widetilde{\Phi}_{j}^{(s)},\mathcal{E}_{j-1}^{(s)},x_{i}^{(s)}\geqslant\alpha_{j}^{(s)},\operatorname{Rank}^{(s)}(i)\leqslant
n\cdot\delta\,\right]$
$\displaystyle\leqslant\sum_{u:y_{u}^{(s)}\geqslant\alpha_{j}^{(s)}}\frac{\gamma\delta}{n}\cdot\mathbf{Pr}\left[\,\operatorname{Rank}^{(s)}(i)=u\,\big{|}\,\widetilde{\Phi}_{j}^{(s)},\mathcal{E}_{j-1}^{(s)},x_{i}^{(s)}\geqslant\alpha_{j}^{(s)},\operatorname{Rank}^{(s)}(i)\leqslant
n\cdot\delta\,\right]$ The information in the previous potential functions,
$\widetilde{\Phi}_{j}^{(s)}$ and $\mathcal{E}_{j-1}^{(s)}$, does not allow to
distinguish bins, so each one is equally likely to have any of the loads,
$\displaystyle=\sum_{u:y_{u}^{(s)}\geqslant\alpha_{j}^{(s)}}\frac{\gamma\delta}{n}\cdot\frac{1}{\left|u:y_{u}^{(s)}\geqslant\alpha_{j}^{(s)}\right|}=\frac{\gamma\delta}{n}.$

∎

####  6.4.2 Auxiliary Probabilistic Lemmas on the Potential Functions

The first lemma proves that $\widetilde{\Psi}_{j}^{(s)}$ is small in
expectation for at _at least one_ time-step. It relies on the multiplicative
drop (6.9), and the fact that precondition
$\cap_{r\in[\beta_{j-1},s]}\mathcal{E}_{j-1}^{(r)}$ holds due to the
definition of the killed potential $\widetilde{\Psi}_{j-1}$.

######  Lemma 6.11.

There exists $s\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]$ such that
$\mathbf{E}[\,\widetilde{\Psi}_{j}^{(s)}\,]\leqslant cn$.

###### Proof.

In this lemma, we analyze
$\widetilde{\Psi}_{j}^{(s)}=\Psi_{j}^{(s)}\cdot\mathbf{1}_{\cap_{r\in[\beta_{j-1},s]}\mathcal{E}_{j-1}^{(r)}}$,
so we will implicitly only deal with the case where $\mathcal{E}_{j-1}^{(r)}$
holds for all $r\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]$.

Since $\mathcal{E}_{j-1}^{(\beta_{j-1})}$ holds,
$\Phi_{j-1}^{(\beta_{j-1})}\leqslant 2cn$ holds, so using 6.14, we have
$\Psi_{j}^{(\beta_{j-1})}\leqslant\exp(0.01(\log n)^{3})$. Note that if at
step $r\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]$,
$\widetilde{\Psi}_{j}^{(r)}\geqslant cn$, then the second inequality from 6.9
implies,

$\mathbf{E}\left[\,\widetilde{\Psi}_{j}^{(r+1)}\,\big{|}\,\widetilde{\Psi}_{j}^{(r)}\,\right]\leqslant\left(1-\frac{1}{2n}\right)\cdot\widetilde{\Psi}_{j}^{(r)},$
(6.1)

since whenever $\widetilde{\Psi}_{j}^{(s)}=0$, the inequality holds trivially.
We define the killed potential function,

$\Lambda_{j}^{(r)}:=\widetilde{\Psi}_{j}^{(r)}\cdot\mathbf{1}_{\bigcap_{\widetilde{r}\in[\beta_{j-1},r]}\widetilde{\Psi}_{j}^{(\widetilde{r})}\geqslant
cn},$

for $r\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]$. This satisfies the
multiplicative drop in (6.1), but regardless of how large $\Lambda_{j}^{(r)}$
is. By inductively applying the inequality for $\Delta=n\log^{3}n$ steps, we
have

$\mathbf{E}\left[\,\Lambda_{j}^{(\beta_{j-1}+\Delta)}\,\right]=\mathbf{E}\left[\,\mathbf{E}\left[\,\Lambda_{j}^{(\beta_{j-1}+\Delta)}\,\big{|}\,\Lambda_{j}^{(\beta_{j-1})}\,\right]\,\right]\leqslant
e^{-\frac{\Delta}{2n}}\cdot\mathbf{E}\left[\,\widetilde{\Psi}_{j}^{(\beta_{j-1})}\,\right]\leqslant
1\leqslant c.$

Hence, there exists $s\in[\beta_{j-1},\beta_{j-1}+\Delta]$, such that
$\mathbf{E}\left[\,\widetilde{\Psi}_{j}^{(s)}\,\right]\leqslant cn$. ∎

Generalizing the previous lemma, and again exploiting the conditioning on
$\cap_{r\in[\beta_{j-1},s]}\mathcal{E}_{j-1}^{(r)}$ of $\Psi_{j}^{(s)}$, we
know prove that $\widetilde{\Psi}_{j}^{(s)}$ is small in expectation for the
entire time interval.

######  Lemma 6.12.

For all $s\in[\beta_{j-1}+n\log^{3}n,t+n\log^{5}n]$,
$\mathbf{E}[\,\widetilde{\Psi}_{j}^{(s)}\,]\leqslant cn$.

###### Proof.

Again, note that this lemma analyzes
$\widetilde{\Psi}_{j}^{(s)}=\Psi_{j}^{(s)}\cdot\mathbf{1}_{\cap_{r\in[\beta_{j-1},s]}\mathcal{E}_{j-1}^{(r)}}$,
and thus we will implicitly only deal with the case where
$\mathcal{E}_{j-1}^{(r)}$ holds for all
$r\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]$.

By using 6.11, we get that
$\mathbf{E}[\,\widetilde{\Psi}_{j}^{(r_{0})}\,]\leqslant cn$ for some
$r_{0}\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]$. Further, by using the
inequality of 6.9 and the fact that $2\leqslant c$, we have for any
$r\in[\beta_{j-1},t+n\log^{5}n]$,

$\mathbf{E}\left[\,\widetilde{\Psi}_{j}^{(r+1)}\,\big{|}\,\widetilde{\Psi}_{j}^{(r)}\,\right]\leqslant\left(1-\frac{1}{n}\right)\cdot\widetilde{\Psi}_{j}^{(r)}+c.$

For all $r\in[r_{0},t+n\log^{5}n]$ such that
$\mathbf{E}[\,\widetilde{\Psi}_{j}^{(r)}\,]\leqslant cn$ holds, it follows
that,

$\mathbf{E}\left[\,\widetilde{\Psi}_{j}^{(r+1)}\,\right]=\mathbf{E}\left[\,\mathbf{E}\left[\,\widetilde{\Psi}_{j}^{(r+1)}\,\big{|}\,\widetilde{\Psi}_{j}^{(r)}\,\right]\,\right]\leqslant\left(1-\frac{1}{n}\right)\cdot\mathbf{E}\left[\,\widetilde{\Psi}_{j}^{(r)}\,\right]+c\leqslant\left(1-\frac{1}{n}\right)cn+c=cn.$

Hence, starting from $\mathbf{E}[\,\widetilde{\Psi}_{j}^{(r_{0})}\,]\leqslant
cn$, it follows inductively that for any $s\in[r_{0},t+n\log^{5}n]$,
$\mathbf{E}[\,\widetilde{\Psi}_{j}^{(s)}\,]\leqslant cn$. Since
$r_{0}\leqslant\beta_{j-1}+n\log^{3}n$, the claim follows. ∎

We now switch to the other potential function $\widetilde{\Phi}_{j}^{(s)}$,
and prove that if it is polynomial in _at least one step_ , then it is also
linear in _at least one_ step (not much later).

######  Lemma 6.13.

For all $1\leqslant j<k$ it holds that,

$\mathbf{Pr}\left[\,\bigcup_{s\in[\beta_{j-1},\beta_{j}]}\\{\widetilde{\Phi}_{j}^{(s)}\leqslant
cn\\}~{}\,\Big{|}\,~{}\bigcup_{r\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]}\\{\widetilde{\Phi}_{j}^{(r)}\leqslant
n^{4/3}\\}\,\right]\geqslant 1-n^{-5}.$

###### Proof.

Note that if at step $\widetilde{r}$,
$\widetilde{\Phi}_{j}^{(\widetilde{r})}>cn$, then the first inequality from
6.9 implies,

$\mathbf{E}\left[\,\widetilde{\Phi}_{j}^{(\widetilde{r}+1)}\,\big{|}\,\widetilde{\Phi}_{j}^{(\widetilde{r})},\widetilde{\Phi}_{j}^{(\widetilde{r})}\geqslant
cn\,\right]\leqslant\left(1-\frac{1}{2n}\right)\cdot\widetilde{\Phi}_{j}^{(\widetilde{r})}.$
(6.2)

We define the killed potential function

$\Lambda_{j}^{(\widetilde{r})}:=\widetilde{\Phi}_{j}^{(\widetilde{r})}\cdot\mathbf{1}_{\bigcap_{\widetilde{s}\in[r,\widetilde{r})}\widetilde{\Phi}_{j}^{(\widetilde{s})}\geqslant
cn},$

for $\widetilde{r}\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]$. This satisfies
inequality 6.2 for all $\widetilde{r}\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]$,
regardless of the value of $\widetilde{\Phi}_{j}^{(\widetilde{r})}$.

Let $r\geqslant\beta_{j-1}$ be the smallest time-step such that
$\widetilde{\Phi}_{j}^{(r)}\leqslant n^{4/3}$ holds. By inductively applying
6.2 for $\Delta=n\log^{2}n$ steps, we have

$\mathbf{E}\left[\,\Lambda_{j}^{(r+\Delta)}\,\big{|}\,\Lambda_{j}^{(r)},\widetilde{\Phi}_{j}^{(r)}\leqslant
n^{4/3}\,\right]\leqslant
e^{-\frac{\Delta}{2n}}\cdot\widetilde{\Phi}_{j}^{(r)}\leqslant
e^{-\frac{1}{2}\log^{2}n}\cdot n^{4/3}\leqslant n^{-4},$

for sufficiently large $n$. By Markov’s inequality,

$\mathbf{Pr}\left[\,\Lambda_{j}^{(r+\Delta)}>cn\,\big{|}\,\widetilde{\Phi}_{j}^{(r)}\leqslant
n^{4/3}\,\right]\leqslant n^{-4}\cdot\frac{1}{cn}\leqslant n^{-5}.$

Since, $\Lambda_{j}^{(r+\Delta)}\leqslant cn\Rightarrow\exists
s\in[r,r+\Delta]\subseteq[\beta_{j-1},\beta_{j}]\colon\,\widetilde{\Phi}_{j}^{(s)}\leqslant
cn$, we get the conclusion. ∎

####  6.4.3 Deterministic Relations between the Potential Functions

We collect several basic facts about the potential functions $\Phi_{j}^{(s)}$
and $\Psi_{j}^{(s)}$.

######  Claim 6.14.

For any $s\geqslant 0$,

$\Phi_{j}^{(s)}\leqslant
2cn\Rightarrow\Psi_{j+1}^{(s)}\leqslant\exp(0.01\cdot\log^{3}n).$

###### Proof.

Assuming $\Phi_{j}^{(s)}\leqslant 2cn$, implies that for any bin $i\in[n]$,

$\displaystyle\exp\left(\alpha_{2}\cdot(\log
n)^{j/k}\cdot\left(x^{(s)}_{i}-\frac{s}{n}-\frac{2}{\alpha_{2}}j(\log
n)^{1/k}\right)\right)\leqslant 2cn$
$\displaystyle\Rightarrow~{}~{}x^{(s)}_{i}\leqslant\frac{s}{n}+\log(2c)+\frac{1}{\alpha_{2}}(\log
n)^{\frac{k-j}{k}}+\frac{2}{\alpha_{2}}j(\log
n)^{1/k}\leqslant\frac{s}{n}+0.5\cdot(\log n)^{2},$

for sufficiently large $n$. Hence,

$\Psi_{j+1}^{(s)}\leqslant n\cdot\exp(0.01\cdot(\log n)^{\frac{j+1}{k}}\cdot
0.5\cdot(\log n)^{2})\leqslant\exp(0.01\cdot\log^{3}n).$

∎

The next claim is crucial for applying the concentration inequality, since the
third statement bounds the maximum additive change of $\Phi^{(s)}$ (assuming
$\Psi^{(s)}$ is small enough):

######  Claim 6.15.

For any $s\geqslant 0$, if $\Psi_{j}^{(s)}\leqslant cn^{12}$, then (i)
$x_{i}^{(s)}\leqslant\frac{s}{n}+\frac{12.1}{\alpha_{1}}\cdot(\log
n)^{\frac{k-j}{k}}+\frac{2}{\alpha_{2}}j(\log n)^{1/k}$ for all $i\in[n]$,
(ii) $\Phi_{j}^{(s)}\leqslant n^{4/3}$ and (iii)
$|\Phi_{j}^{(s+1)}-\Phi_{j}^{(s)}|\leqslant n^{1/3}$.

###### Proof.

Let $s$ be some time-step with $\Psi_{j}^{(s)}\leqslant cn^{12}$. For $(i)$,
assuming that $x_{i}^{(s)}>\frac{s}{n}+\frac{12.1}{\alpha_{1}}\cdot(\log
n)^{\frac{k-j}{k}}+\frac{2}{\alpha_{2}}j(\log n)^{1/k}$, then we get
$\Psi_{j}^{(s)}>\exp(\alpha_{1}\cdot\frac{12.1}{\alpha_{1}}\cdot\log
n)=n^{12.1}$, which is a contradiction. For $(ii)$, it suffices to prove
$\Phi_{j,i}^{(s)}\leqslant n^{1/3}$, so,

$\displaystyle\Phi_{j,i}^{(s)}$
$\displaystyle\leqslant\exp\bigl{(}\alpha_{2}\cdot(\log
n)^{j/k}\cdot\bigl{(}x_{i}^{(s)}-\frac{s}{n}-\frac{2}{\alpha_{2}}j(\log
n)^{1/k}\bigr{)}^{+}\bigr{)}$
$\displaystyle\leqslant\exp\bigl{(}\alpha_{2}\cdot(\log
n)^{j/k}\cdot\frac{12.1}{\alpha_{1}}\cdot(\log n)^{\frac{k-j}{k}}\bigr{)}$
$\displaystyle=\exp\bigl{(}\frac{12.1\cdot 0.0002}{0.01}\cdot\log
n\bigr{)}\leqslant n^{1/3}.$

For $(iii)$, following the argument in the proof of 6.15, because the
potential function is convex, the maximum change is upper bounded by the
hypothetical scenario of placing two balls in the heaviest bin, i.e. by
$n^{1/3}$. ∎

The next claim is a simple “smoothness” argument showing that the potential
cannot decrease quickly within $n/\log^{2}n$ steps. The derivation is
elementary and relies on the fact that average load does not change by more
than $1/\log^{2}n$.

######  Claim 6.16.

For any $s\geqslant 0$ and any $r\in[s,s+n/\log^{2}n]$, we have
$\Phi_{j}^{(r)}\geqslant 0.99\cdot\Phi_{j}^{(s)}$.

###### Proof.

The normalized load after $r-s$ steps can decrease by at most
$\frac{r-s}{n}\leqslant\frac{1}{\log^{2}n}$. Hence,

$\displaystyle\Phi_{j,i}^{(r)}$ $\displaystyle=\exp\left(0.01\cdot(\log
n)^{j/k}\cdot(x_{i}^{(s)}-\frac{r-s}{n}-\frac{s}{n}-\frac{2}{\alpha_{2}}j(\log
n)^{1/k})^{+}\right)$ $\displaystyle\geqslant\exp\left(0.01\cdot(\log
n)^{j/k}\cdot(x_{i}^{(s)}-\frac{s}{n}-\frac{2}{\alpha_{2}}j(\log
n)^{1/k})^{+}-\frac{0.01\cdot(\log n)^{j/k}\frac{n}{\log^{2}n}}{n}\right)$
$\displaystyle\geqslant\Phi_{j,i}^{(s)}\cdot e^{-\frac{0.01\cdot(\log
n)^{j/k}}{\log^{2}n}}\geqslant 0.99\cdot\Phi_{j,i}^{(s)},$

for sufficiently large $n$. ∎

###  6.5 Completing the Proof of Key Lemma (6.7)

The proof of 6.7 shares some of the ideas from the proof of 5.3. However,
there we could more generously take a union bound over the entire time-
interval to ensure that the potential is indeed small everywhere with high
probability. Here we cannot afford to lose a polynomial factor in the error
probability, as the inductive step has to be applied $k=\omega(1)$ times. To
overcome this, we will partition the time-interval into consecutive intervals
of length $n/\log^{2}n$. Then, we will prove that at the end of each such
interval the potential is small w.h.p., and finally use a simple smoothness
argument of the potential to show that the potential is small w.h.p. for _all_
time steps.

###### Proof of 6.7.

The first and second statements in 6.15, imply that if
$\Psi_{j}^{(s)}\leqslant cn^{12}$ holds, then

$\left|\widetilde{\Phi}_{j}^{(s+1)}-\widetilde{\Phi}_{j}^{(s)}\right|\leqslant
n^{1/3},$

and $\widetilde{\Phi}_{j}^{(s)}\leqslant n^{4/3}$.

Thus we will next establish that $\Psi_{j}^{(s)}\leqslant cn^{12}$ occurs with
high probability.

By 6.12, for all $s\in[\beta_{j-1}+n\log^{3}n,t+n\log^{5}n]$,
$\mathbf{E}[\,\widetilde{\Psi}_{j}^{(s)}\,]\leqslant cn$. Using Markov’s
inequality, we have with probability at least $1-n^{-11}$ that
$\widetilde{\Psi}_{j}^{(s)}\leqslant cn^{12}$. Hence by the union bound it
follows that

$\displaystyle\mathbf{Pr}\left[\,\bigcap_{s\in[\beta_{j-1}+n\log^{3}n,t+n\log^{5}n]}\\{\widetilde{\Psi}_{j}^{(s)}\leqslant
cn^{12}\\}\,\right]\geqslant 1-n^{-9}.$ (6.3)

We now define the intervals

$\mathcal{I}_{1}:=(t_{0},t_{0}+\Delta],\mathcal{I}_{2}=(t_{0}+\Delta,t_{0}+2\Delta],~{}\ldots~{},\mathcal{I}_{q}:=(t_{0}+(q-1)\Delta,t+n\log^{5}n],$

where $t_{0}\in[\beta_{j-1}+n\log^{3}n,\beta_{j}]$ is arbitrary (but will be
chosen later), $\Delta:=n/\log^{2}n$ and
$q:=\lfloor\frac{t+n\log^{5}n-t_{0}}{\Delta}\rfloor\leqslant\log^{7}n$. In
order to prove that $\Phi_{j}$ is at most $2cn$ over all these intervals, we
will use our auxiliary lemmas and the supermartingale concentration inequality
(A.4) to establish that $\Phi_{j}$ is at most $(c+1)\cdot n$ at the points
$t_{0}+\Delta,t_{0}+2\Delta,\ldots t_{0}\cdot q,t+n\log^{5}n$. By using a
smoothness argument (6.16), this will establish that $\Phi$ is at most $2cn$
at all points in $[t_{0},t+n\log^{5}n]$, which is the conclusion of the lemma.

For each interval $i\in[q]$, we define for
$s\in(t_{0}+(i-1)\Delta,t_{0}+i\Delta]$,

$X_{i}^{(s)}:=\begin{cases}\Phi_{j}^{(s)}&\text{if }\exists
u\in(t_{0}+(i-1)\cdot\Delta,s)$ such that $\Phi_{j}^{(u)}>5\cdot c\cdot n,\\\
5cn+n^{1/3}&\text{otherwise}.\end{cases}$

Note that whenever the first condition in the definition of $X_{i}^{(s)}$ is
satisfied, it remains satisfied until $t_{0}+i\cdot\Delta$, again by 6.16.

Following the notation of A.4, define the event

$\overline{B_{i}^{(s)}}:=\left(\bigcap_{u\in[t_{0}+(i-1)\cdot\Delta,s)}\\{\widetilde{\Psi}_{j}^{(u)}\leqslant
cn^{12}\\}\right)\bigcap\left(\bigcap_{u\in[t_{0}+(i-1)\cdot\Delta,s)}\mathcal{E}_{j-1}^{(u)}\right).$

By the inductive hypothesis of 6.7 for $j-1$,

$\mathbf{Pr}\left[\,\bigcap_{u\in[\beta_{j-1},t+n\log^{5}n]}\mathcal{E}_{j-1}^{(u)}\,\right]\geqslant
1-\frac{(\log n)^{8(j-1)}}{n^{4}},$

and hence by the union bound over this and Eq. 6.3,

$\mathbf{Pr}\left[\,\overline{B}_{i}^{(s)}\,\right]\geqslant
1-n^{-9}-\frac{(\log n)^{8(j-1)}}{n^{4}}\geqslant 1-\frac{2(\log
n)^{8(j-1)}}{n^{4}}.$

######  Claim 6.17.

Fix any interval $i\in[q]$. Then the sequence of random variable $X_{i}^{(s)}$
with filtration $\mathcal{F}_{i}^{(s)}$, for
$s\in[t_{0}+(i-1)\Delta,t_{0}+i\Delta]$ and $B_{i}^{(s)}$ being the bad set
associated, satisfies for all $s$,

$\displaystyle\mathbf{E}\left[\,X_{i}^{(s)}\,\mid\,\mathcal{F}_{i}^{(s-1)}\,\right]\leqslant
X_{i}^{(s-1)},$

and

$\left|\left(X_{i}^{(s)}-X_{i}^{(s-1)}\right)\,\mid\,\mathcal{F}_{i}^{(s-1)}\right|\leqslant
2n^{1/3}.$

###### Proof of 6.17.

We begin by noting that, step $s\in[t_{0}+(i-1)\Delta,t_{0}+i\Delta]$ with
$X_{i}^{(s)}\geqslant 4n$, the first inequality of 6.9 can be relaxed to,

$\displaystyle\mathbf{E}\left[\,\Phi_{j}^{(s+1)}\,\mid\,\mathcal{E}_{j-1}^{(s)},\Phi_{j}^{(s)}\,\right]\leqslant\Big{(}1-\frac{1}{2n}\Big{)}\cdot\Phi_{j}^{(s)}.$
(6.4)

We consider the following three cases:

  * •

Case 1: Assume that $\Phi_{j}^{(s)}<5\cdot c\cdot n$ and this was the case for
all previous time steps. Then, the $X_{i}^{(s+1)}=X_{i}^{(s)}$, so the two
statements hold trivially.

  * •

Case 2: Assume that $\Phi_{j}^{(u)}>5\cdot c\cdot n$ for some $u\leqslant
s-2$, then by 6.16, since $s-u\leqslant n/\log^{2}n$,

$\Phi_{j}^{(s-1)}\geqslant 0.99\cdot\Phi_{j}^{(u)}>2cn,$

and thus by Eq. 6.4, the first statement follows. The second statement
follows, since conditional on $\overline{\mathcal{B}}_{i}^{(s)}$, the
precondition of 6.15 (iii) holds.

  * •

Case 3: Assume that $\Phi_{j}^{(u)}<5cn$ for $u\leqslant s-2$ and
$\Phi_{j}^{(s-1)}>5cn$. First, we obtain that
$\Phi_{j}^{(s-1)}\leqslant\Phi_{j}^{(s-2)}+n^{1/3}<5\cdot c\cdot n+n^{1/3}$
(by 6.15 (ii), using again that $\overline{\mathcal{B}}_{i}^{(s)}$ holds).
Further, by definition, $X_{i}^{(s-1)}=5cn+n^{1/3}$, so
$\mathbf{E}[\,X_{i}^{(s)}\,\mid\,\Phi_{i}^{(s-1)}\,]=\mathbf{E}[\,\Phi_{j}^{(s)}\,\mid\,\Phi_{i}^{(s-1)}\,]\leqslant\Phi_{j}^{(s-1)}<X_{i}^{(s-1)}$
by Eq. 6.4. The second inequality follows by 6.15 (iii), since
$|X_{i}^{(s-1)}-X_{i}^{(s)}|\leqslant
n^{1/3}+|\Phi_{j}^{(s)}-\Phi_{j}^{(s-1)}|\leqslant 2n^{1/3}$.

∎

Next we claim that $X_{i}^{(s)}$ satisfies the following conditions of A.4
(where $\mathcal{F}_{i}$ are the filtrations associated with the balls
allocated at $\mathcal{I}_{i}$ and $B_{i}^{(s)}$ is the bad set associated):

  1. 1.

$\mathbf{E}[\,X_{i}^{(s)}\mid\mathcal{F}_{i}^{(s-1)}\,]\leqslant
X_{i}^{(s-1)}$ by the first statement of 6.17.

  2. 2.

$\mathbf{Var}[\,X_{i}^{(s)}\mid\mathcal{F}_{i}^{(s-1)}\,]\leqslant n^{2/3}$.
This holds, since

$\displaystyle\mathbf{Var}\left[\,X_{i}^{(s)}\mid\mathcal{F}_{i}^{(s-1)}\,\right]$
$\displaystyle\leqslant\frac{1}{4}\left|\left(\max X_{i}^{(s)}-\min
X_{i}^{(s)}\right)\,\mid\,\mathcal{F}_{i}^{(s-1)}\right|^{2}$
$\displaystyle\leqslant\frac{1}{4}\left(2\cdot\left|X_{i}^{(s)}-X_{i}^{(s-1)}\right|\,\mid\,\mathcal{F}_{i}^{(s-1)}\right)^{2}\leqslant
4n^{2/3},$

where the first inequality follows by Popovicius’ inequality, the second by
the triangle inequality and the third by 6.17.

  3. 3.

$X_{i}^{(s)}-\mathbf{E}[\,X_{i}^{(s)}\mid\mathcal{F}_{i}^{(s-1)}\,]\leqslant
2\cdot\bigl{(}\bigl{|}X_{i}^{(s)}-X_{i}^{(s-1)}\bigr{|}\,\mid\,\mathcal{F}_{i}^{(s-1)}\bigr{)}\leqslant
4n^{1/3}$ which follows by the second statement of 6.17.

Now applying A.4 for $i\in[q]$ with $\lambda=\frac{n}{\log^{7}n}$,
$a_{i}=4n^{1/3}$, and $M=0$, we get

$\displaystyle\mathbf{Pr}\left[\,X_{i}^{(t_{0}+i\Delta)}\geqslant
X_{i}^{(t_{0}+(i-1)\Delta)}+\lambda\,\right]$
$\displaystyle\leqslant\exp\left(-\frac{n^{2}/\log^{14}n}{2(\Delta\cdot(16n^{2/3}+4n^{2/3}))}\right)+\frac{2(\log
n)^{8(j-1)}}{n^{4}}$ $\displaystyle\leqslant\frac{3(\log n)^{8(j-1)}}{n^{4}}.$

Taking the union bound over the $\log^{7}n$ intervals $i\in[q]$, it follows
that

$\displaystyle\mathbf{Pr}\left[\,\bigcup_{i\in[q]}\\{X_{i}^{(t_{0}+i\Delta)}\geqslant
X_{1}^{(t_{0})}+i\cdot\lambda\\}\,\right]\leqslant\log^{7}n\cdot\frac{3(\log
n)^{8(j-1)}}{n^{4}}.$ (6.5)

It remains to show the existence of a
$t_{0}\in[\beta_{j-1},\beta_{j-1}+n\log^{3}n]$ for which $X_{1}^{(t_{0})}$ is
small.

Since $\Psi_{j}^{(s)}\leqslant\widetilde{\Psi}_{j}^{(s)}$, we can conclude
from Eq. 6.3 that with probability at least $1-n^{-9}$, for
$s=\beta_{j-1}+n\log^{3}n$ we have
$\widetilde{\Phi}_{j}^{(\beta_{j-1}+n\log^{3}n)}\leqslant n^{4/3}$.

Assuming this occurs, then by 6.13, there exists a time step
$t_{0}\in[\beta_{j-1},\beta_{j}]$ such that
$\widetilde{\Phi}_{j}^{(t_{0})}\leqslant cn$ w.p. at least $1-n^{-4}$. Thus by
the union bound over this and Eq. 6.3,

$\mathbf{Pr}\left[\,\bigcup_{t_{0}\in[\beta_{j-1},\beta_{j}]}\\{\widetilde{\Phi}_{j}^{(t_{0})}\leqslant
cn\\}\,\right]\geqslant 1-n^{-4}-n^{-9}.$

As

$\widetilde{\Phi}_{j}^{(t_{0})}=\Phi_{j}^{(t_{0})}\cdot\mathbf{1}_{\cap_{s\in[\beta_{j-1},t_{0}]}\Phi_{j-1}^{(s)}\leqslant
2cn},$

and
$\mathbf{Pr}\left[\,\bigcap_{s=\beta_{j-1}}^{t_{0}}\\{\Phi_{j-1}^{(s)}\leqslant
2cn\\}\,\right]\geqslant\frac{(\log n)^{8(j-1)}}{n^{4}}$ by the inductive
hypothesis, a union bound yields

$\displaystyle\mathbf{Pr}\left[\,\bigcup_{t_{0}\in[\beta_{j-1},\beta_{j}]}\\{\Phi_{j}^{(t_{0})}\leqslant
cn\\}\,\right]\geqslant 1-n^{-4}-n^{-9}-\frac{(\log
n)^{8(j-1)}}{n^{4}}\geqslant 1-\frac{2(\log n)^{8(j-1)}}{n^{4}}.$

Since $c>4$, we conclude that

$\displaystyle\mathbf{Pr}\left[\,\bigcup_{t_{0}\in[\beta_{j-1},\beta_{j}]}\\{X_{1}^{(t_{0})}\leqslant
cn\\}\,\right]=\mathbf{Pr}\left[\,\bigcup_{t_{0}\in[\beta_{j-1},\beta_{j}]}\\{X_{1}^{(t_{0})}\leqslant\max\\{cn,4n+n^{1/3}\\}\\}\,\right]\geqslant
1-\frac{2(\log n)^{8(j-1)}}{n^{4}}.$

Taking the union bound over this and Eq. 6.5, we conclude

$\displaystyle\mathbf{Pr}\left[\,\bigcup_{i\in[q]}\\{X_{i}^{(t_{0}+i\Delta)}\geqslant
cn+\log^{7}n\cdot\frac{n}{\log^{7}n}\\}\,\right]\leqslant\log^{7}n\cdot\frac{4(\log
n)^{8(j-1)}}{n^{4}}.$ (6.6)

For the time-step $u=u(i):=t_{0}+i\Delta$ at the end of the interval $u$, we
cannot deduce anything about $\Phi_{j}$ from $X_{i}$ because of the shift-by-
one in time-steps. To fix this, recall that by 6.15 (third statement),
$\Psi_{j}^{(u)}\leqslant cn^{12}$ implies
$\left|\Phi_{j}^{(u+1)}-\Phi_{j}^{(u)}\right|\leqslant 2n^{1/3}$. Hence Eq.
6.3 (together with the inductive hypothesis) implies that

$\displaystyle\mathbf{Pr}\left[\,X_{i}^{(u)}+2n^{1/3}\geqslant\Phi_{j}^{(u)}\,\right]\geqslant
1-\mathbf{Pr}\left[\,\left|\Phi_{j}^{(u+1)}-\Phi_{j}^{(u)}\right|\leqslant
2n^{1/3}\,\right]\geqslant 1-n^{-9}-\frac{(\log n)^{8(j-1)}}{n^{4}}.$

Using this, Eq. 6.6 and then applying a union bound over $i\in[q]$

$\displaystyle\mathbf{Pr}\left[\,\bigcup_{i\in[q]}\\{\Phi_{j}^{(u(i))}\geqslant
cn+\log^{7}n\cdot\frac{n}{\log^{7}n}+2n^{1/3}\\}\,\right]\leqslant\log^{7}n\cdot\frac{6(\log
n)^{8(j-1)}}{n^{4}}.$

Finally, by 6.16 the above statement extends to _all_ time-steps at the cost
of a slightly larger threshold:

$\displaystyle\mathbf{Pr}\left[\,\bigcup_{s\in[\beta_{j},t+n\log^{5}n]}\\{\Phi_{j}^{(s)}\geqslant
2c\cdot n\\}\,\right]\leqslant\log^{7}n\cdot\frac{6(\log n)^{8(j-1)}}{n^{4}},$

since $(c+2)\cdot\frac{1}{0.99}\leqslant 2c$.∎

###  6.6 Proof of Main Theorem (6.1) using 6.7

###### Proof of 6.1.

Consider first the case where $m\geqslant n\log^{5}n$ and let
$t=m-n\log^{5}n$. We will proceed by induction on the potential functions
$\Phi_{j}$. The base case follows by noting that the probability vector $p$
satisfies the precondition of 5.3, and applying this to all time steps
$s\in[t,m]$ and taking the union bound gives,

$\mathbf{Pr}\left[\,\bigcap_{s\in[t,m]}\\{\Phi_{0}^{(s)}\leqslant
2cn\\}\,\right]\geqslant 1-n^{-4}.$

For the inductive step, we use 6.7. After $k$ applications, we get