# The $k$-Cap Process on Geometric Random Graphs

Mirabel Reid
<EMAIL_ADDRESS>
Georgia Tech  Santosh S. Vempala
<EMAIL_ADDRESS>
Georgia Tech

###### Abstract

The $k$-cap (or $k$-winners-take-all) process on a graph works as follows: in
each iteration, a subset of $k$ vertices of the graph are identified as
winners; the next round winners are the vertices that have the highest total
degree from the current winners, with ties broken randomly. This natural
process is a simple model of firing activity and inhibition in the brain and
has been found to have desirable robustness properties as an activation
function. We study its convergence on directed geometric random graphs in any
constant dimension, revealing rather surprising behavior, with the support of
the current active set converging to lie in a small ball and the active set
itself remaining essentially random within that.

###### Contents

  1. 1 Introduction
    1. 1.1 Main Results
    2. 1.2 Analysis Outline
  2. 2 Analysis of the discrete $k$-cap process
    1. 2.1 Characterization of $A_{1}$
    2. 2.2 Convergence of $A_{t}$
  3. 3 Continuous $\alpha$-cap process
  4. 4 Conclusion and further questions
  5. 5 Appendix
    1. 5.1 Probability Preliminaries

##  1 Introduction

The function $k$-cap, also known as $k$-winners take all, takes $n$ real-
valued elements and selects the $k$ elements with the highest values, i.e., it
assigns $1$ to those $k$ and $0$ to all others, breaking ties randomly. It has
found applications in machine learning, image processing and related fields
[Maa00, Wan10, XZZ19]. It has been proven to be computationally powerful;
circuits employing $k$-WTA gates as nonlinearities can approximate arbitrary
Boolean functions [Maa00]. Additionally, since the gradient of the $k$-WTA
function is undefined at key points, it has been recently proposed as a
technique for defending against attacks which use the gradient of a neural
network to generate adversarial examples [XZZ19]. This property differentiates
it from typical activation functions, such as ReLU or tanh. The $k$-cap
process has also been proposed as a model of neural firing behavior, a
motivation that we will discuss in more detail presently.

We study the $k$-cap process, which repeatedly applies $k$-cap to the degrees
of a random graph: at each time step $t>0$, the set $A_{t}$ consists of the
$k$ vertices with the highest degree in $A_{t-1}$ (with ties broken randomly).
Given this process, some natural questions arise:

  * •

What does the $k$-cap process “converge” to?

  * •

When the process does converge, how quickly does it do so?

To understand these and related questions, we investigate how the $k$-cap
$A_{t}$ at time $t$, evolves as $t\rightarrow\infty$. If $G$ is the complete
graph, every vertex has degree $k$ from $A_{t}$; so, assuming random tie-
breaking, all vertices fire with probability $k/n$ at each time step. On the
other hand, if $G$ is a sparse graph with a planted $k$-clique $H$, we expect
$A_{t}=H$ to be a fixed point (for $k$ sufficiently large). These examples
indicate that the answers to the above questions depend on the graph
structure; there are many classes of random graphs in which no meaningful
convergence is expected. For example, we don’t expect this process to converge
on a directed Erdős–Rényi model of random graphs. Since this early influential
model, many interesting variants of random graphs have been proposed, e.g.,
Power Law Random graphs, Stochastic Block Models, Geometric Random graphs,
etc. The last of these seems particularly well-motivated for studying the
$k$-cap process. In geometric random graphs, each vertex is assigned a
position in a hidden variable space (for example, the cube $[0,1]^{d}$). The
probability that an edge $\mathbbm{1}_{(x,y)}$ exists in the graph is a
function of the hidden variables of the endpoints. By using an edge
probability function which decreases with distance in the hidden variable
space, this creates subgraphs which are dense and concentrated within a small
diameter subset of the space. The hidden variables can correspond to spatial
distance, or they can represent similarity in a wider set of features. For
example, the geometric random graph model has been used for social networks,
where the hidden variable represents a closeness in “social space” rather than
physical distance [Bog+04]. This model has also been studied in the context of
transportation networks, communication networks, and networks of neurons
[BS09, Bar11].

Properties of geometric random graphs have been thoroughly explored; see
[Pen03] for comprehensive exposition. In the most common variant of the model,
all vertices are placed in a $d$-dimensional space according to some
distribution. If the distance between two vertices is less than $r$ (where $r$
is a parameter of the model), they are connected by an edge; otherwise, they
are not. We study a directed, soft geometric random graph where the edge
probability decays exponentially with squared distance, i.e., the Gaussian
kernel. This alternative model introduces asymmetry as well as long-range
connections, both of which are important for real-life networks.

#### Motivation from the Brain.

The network of the brain, called the connectome, is modeled as a sparse
directed graph whose nodes represent neurons and whose directed edges
represent synaptic connections. It is useful to view the connectome as
consisting of many directed subgraphs (also called brain areas) with some
connectivity between them. Neurons fire based on the total (weighted) input
they sense from other neurons that are currently firing. An important and
longstanding idea in neuroscience is that of an assembly of neurons — a subset
of densely interconnected nodes within a brain area which tend to fire
together in response to the same input to the brain area [Pap+20, Buz19].
Assemblies are created through projection, where an outside stimulus fires
(repeatedly), activating a subset of neurons. Two ideas, rooted in
experimental findings in neuroscience, lead to the convergence of assembly
projection in a random brain graph. The first is inhibition: at each step, the
$k$ neurons with the highest total synaptic input are chosen to fire, while
the rest are suppressed. The second is plasticity: if a neuron fires
immediately following one of its pre-synaptic neighbors, the weight of the
edge between them is increased. This causes neurons that ‘fire together’ to
‘wire together’, and strengthens internal connections each time an assembly is
activated.

Rigorous analysis of the assembly model has thus far been based on a directed
Erdös-Rényi random graph, where each pair of neurons has an equal probability
of being connected via a synapse. There are two important ways in which this
model departs from observed reality. First, the locations of neurons in the
brain and the physical distance between them have a significant impact on the
probability of connection. Long axons come with a cost in both material and
energy, so neurons tend to prefer to create connections that are close in
physical space. The principle of conservation of axonal wiring costs was
proposed by Ramon y Cajal in the early 20th century [Ram11], and the
relationship between distance and connection probability has been confirmed
empirically [BS09, Cun+10]. Moreover, models that take locality into account
are better able to explain statistical deviations of the connectome from the
standard random graph model, as observed in experiments [Son+05]. Second, in
the standard random graph model, assemblies are shown to correspond to the
firing of $k$ neurons, with most of them in a fixed set of size $(1+o(1))k$
with at most $o(k)$ outside this set. On the other hand, what has been
observed is that assemblies represent increased firing activity of a
relatively small but significantly larger than $k$ subset of neurons for a
period of time [DSS00, Buz19]. An exciting aspect of our investigation is a
rigorous explanation of this phenomenon.

###  1.1 Main Results

As a warm-up, we consider the infinite limit, i.e., the continuous interval
$[0,1]$ in one dimension. Then we turn to the discrete setting of graphs, with
vertices chosen uniformly from the $d$-dimensional unit cube. While the brain
motivation applies directly to $d=2,3$, higher dimension is also relevant and
interesting, as vertex location could indicate some set of relevant features
(e.g., type of neuron).

#### A Continuous Process.

A natural abstraction of the $k$-cap process on geometric random graphs is to
consider what happens when the number of vertices, $n$, goes to infinity. On a
finite graph, the input to a discrete vertex $v$ is the sum of its edges from
$A_{t}\subset V=\\{1/n,2/n,\dots,1\\}$. In the infinite limit, we assume that
$A_{t}\subset[0,1]$ is a set of measure $\alpha$, leading to a corresponding
$\alpha$-cap process. The input to a given point $v\in[0,1]$ is the integral
of the edge probability function over $A_{t}$ and the $\alpha$ fraction of
points with the highest input will form $A_{t+1}$. We provide a formal
definition of this process in Section 3.

This continuous abstraction leads to a clean convergence phenomenon. We find
that $A_{t}$ converges to a single interval of length $\alpha$. The number of
steps to convergence depends on how large the derivative of the edge
probability function can be. The exact result proven in this paper is stated
below.

######  Theorem 1.1.

Let $A_{0}$ be a countable set of intervals in [0,1] and $g$ be the edge
probability function. For any differentiable, even, nonnegative and integrable
function $g:[0,1]\rightarrow\mathbb{R}_{+}$ with $g^{\prime}(x)<0$ for all
$x>0$, the $\alpha$-cap process converges to a single interval of width
$\alpha$. Moreover, the number of steps to convergence is

$O\left(\frac{\max_{[0,1]}|g^{\prime}(x)|}{\min_{[\frac{\alpha}{8},1]}|g^{\prime}(x)|}\right).$

Note that the above conditions capture any distance function that decays
smoothly with the distance between its endpoints, e.g., the well-known
Gaussian kernel. This process is deterministic given the initial choice of
$A_{0}$. We are able to bound the convergence using a simple potential
function:

The distance between the medians of the leftmost and rightmost intervals of
$A_{t}$ decreases.

In this way, the intervals are “squeezed” together until they collapse into
one. In this continuous version, any sub-interval in $[0,1]$ of length
$\alpha$ is a fixed point; if $A_{t}=[a,b]$, then $A_{t+1}=A_{t}$. Moreover, a
single interval is the only possible fixed point.

#### Formal Definition of the Discrete Process.

Now we turn to the main setting of this paper, the $k$-cap process on a finite
directed graph $G$. The following symbols will be used for the rest of the
paper. Let $n$ be the number of vertices in the graph and $k$ be the number of
vertices activated at each step. $A_{t}$ represents the set of $k$ vertices
activated at step $t$ for $t=0,1,2,\ldots$. Let $\mathbbm{1}_{(x,y)}$ be the
indicator variable for the directed edge between two vertices $x$ and $y$.

######  Definition 1.1 ($k$-cap Process).

Assume $A_{t}\subset\\{1,2,\dots,n\\}$, and $|A_{t}|=k$. Let
$F_{t}:\\{1,2,\dots,n\\}\rightarrow\\{0,1,2,\dots,k\\}$ be the synaptic input
function at time $t$, defined as follows:

$F_{t}(x)=\sum_{y\in A_{t}}\mathbbm{1}_{(y,x)}$

Let $C_{t}$ be the smallest integer such that $|\\{x\mid
F_{t}(x)>C_{t}\\}|\leq k$, and let

$A_{t+1}=\\{x\mid F_{t}(x)>C_{t}\\}\cup A_{t+1}^{*}$

where $A_{t+1}^{*}$ is a set of points sampled at random from $\\{x\mid
F_{t}(x)=C_{t}\\}$ such that $|A_{t+1}|=k$.

In the $k$-cap process, $A_{t+1}$ is chosen as the $k$ vertices with the
highest degree from $A_{t}$. If there are ties, the remaining vertices are
chosen uniformly at random from the set of vertices with the next highest
degree. $A_{0}$ can be instantiated in any way, but we assume that it is
chosen uniformly at random from the set of vertices.

We analyze the convergence of the $k$-cap process on a $d$-dimensional
Gaussian geometric random graph; the probability of an edge between two
vertices with hidden variables $x$ and $y$ is a Gaussian kernel; i.e.,
$\mathbb{P}((x,y)\in G)=g(x,y)=\exp\left(-(x-y)^{2}/(2\sigma^{2})\right)$.
Here, $\sigma$ is a parameter of the model. For simplicity, we use $x$ to
represent both the vertex and its hidden variable in $[0,1]^{d}$. Throughout
this paper, we will use the terms point and vertex interchangeably.

######  Definition 1.2 ($d$-dim Gaussian Geometric Random Graph).

Let $G=G_{\sigma}=(V,E)$. Let $V=\\{v_{1},v_{2},\dots,v_{n}\\}$ where each
vertex is a point chosen uniformly at random in $[0,1]^{d}$. Each directed
edge $(x,y)$ is present in the graph with probability

$\mathbb{P}(\mathbbm{1}_{(x,y)})=g(x,y)=\exp\left(-\frac{\|x-y\|_{2}^{2}}{2\sigma^{2}}\right)$

Unless otherwise stated, assume $\|x-y\|=\|x-y\|_{2}$ is the Euclidean
distance.

#### Convergence of the Discrete Process.

The discrete process on graphs turns out to exhibit much more complex behavior
than the continuous variant. With the randomness induced by the choice of
edges, the convergence behavior also becomes probabilistic rather than ending
in a fixed set or distribution. We will prove that in the interesting range of
$\sigma$, the cap $A_{t}$ converges with high probability to lie within a
small ball (an interval when $d=1$). Note that the process will not converge
to a fixed set of points; it will instead randomly oscillate within a small
subset of the hidden variable space, corresponding to a small dense subgraph
of $G$. The reasons for this type of convergence are discussed in Section 1.2.
We believe that this behavior is both interesting mathematically and of
relevance to modeling the brain; it provides a new perspective on the notion
of an assembly.

Given that $A_{t}$ will not converge to a fixed set of points, we will
determine the size and structure of the set of likely points. First, it is not
immediately obvious that the set will converge to having its support in a
single small interval, e.g., it may be the case that the set of points which
fire are split between two weakly connected subgraphs. Additionally, we are
interested in the width of the set of likely points. When two points are at a
distance $\Theta(\sigma)$, the probability that they are connected by an edge
is a constant, bounded away from $0$. At a larger distance, the probability
drops off quickly; therefore, we might expect that $A_{t}$ will be contained
within an interval of size $O(\sigma)$. In fact, as stated in Theorem 1.2
below, we find that it will converge to an interval much smaller than
$\sigma$.

######  Theorem 1.2.

There exists a $t^{*}\leq\ln^{c}k$, for a constant $c$, such that $A_{t}$ can
be covered by a single ball of radius $\Theta\left(\sigma\sqrt{\ln
k/k}\right)$.

#### Evolution of the $k$-cap.

Figure 1: The $k$-cap at 4 time steps, with parameters $n=90000$ and $k=40$.

The evolution of the structure of $A_{t}$ also reveals interesting properties
of the $k$-cap process on random graphs. In the first step, $A_{0}$ is
uniformly distributed. However, due to the the Poisson clumping phenomenon
[Ald13], there will be a several regions of the ball with a higher
concentration than average. As we will show, for $\sigma$ sufficiently small,
$A_{1}$ will be concentrated within $k^{1/4+o(1)}$ balls which are small
compared to $[0,1]^{d}$ (This result is described formally in Theorem 1.3). As
$t$ increases, all but one of these balls will diminish and disappear. With
high probability, each ball will shrink by a fixed fraction at each step.
After this, we will show that one ball will “win” over the others.

When $n$ is sufficiently large, $A_{t}$ eventually lies within a subset of a
ball of radius $\sigma\sqrt{\ln k/k}$. The distribution of $A_{t}$ is fairly
uniform in the core of the ball, and the probability drops toward
$\frac{1}{n}$ as it moves to the edges. Figure 1 graphs the points which fired
in a simulation of the $k$-cap process over 4 time steps. In both, the graph
is random with each edge added with probability $\exp(-|x-y|^{2}k^{2}/2)$.

#### Parameter Range.

In this paper, we focus on $\sigma=\Theta(1/k^{1/d})$. The justification for
this parameter range lies in the concentration behavior of uniform random
variables. The soft geometric random graph model can be thought of as an
approximation of an interval graph with radius $\Theta(\sigma)$. Let
$U=\\{U_{1},U_{2},\dots U_{k}\\}$ be a set of $k$ random variables, each
chosen uniformly at random in $[0,1]^{d}$. For a given radius $r$, we can
compute the maximum number of points which are likely to fall into a ball of
radius $r$ (this result is described in Lemma 5.0.3). Note the expected number
of points in a ball $I$ is $k\text{Vol}(I)$, and
$\text{Vol}(I)=\Theta(r^{d})$; as $r$ increases, the maximum degree approaches
the expected value. This phenomenon means that the concentration behavior
starts to disappear as $\sigma$ increases past $1/k^{1/d}$. On the other hand,
as $r$ decreases, the maximum degree approaches $1$. Therefore, we focus on an
intermediate range of $\sigma$ where the concentration of $A_{0}$ leads to
interesting behavior.

#### Organization.

We next discuss the discrete process in detail and present our precise
findings about its convergence. Following that, in Section 2, we prove our
main theorem about this, starting with a detailed exposition of related
probabilistic considerations. In Section 3 we prove the convergence of the
continuous process.

###  1.2 Analysis Outline

An important quantity in the analysis will be the probability that $F_{t}(x)$
exceeds a given threshold: $p_{C,t}(x)=\mathbb{P}(F_{t}(x)\geq C)$. The
probability is conditioned on the random choice of edges in the graph. If $n$
is sufficiently large, we can make the assumption that with high probability,
the random variable $F_{t}(x)$ depends only on the edges from $x$ to $A_{t}$
and is independent of $A_{0},\dots,A_{t-1}$. This will be proven formally when
it becomes relevant. When not otherwise specified, $p_{t}(x)=p_{C_{t},t}(x)$
is the probability that $F_{t}(x)$ strictly exceeds the $k$-cap threshold
$C_{t}$, conditioned on the choice of the set $A_{t}$. Figure 2 shows an
empirical demonstration of how the functions $\mathbb{E}F_{t}(x)$ and
$p_{t}(x)$ evolve over time.

(a) $t=0$

(b) $t=2$

Figure 2: Expected input and $p_{t}(x)$ at two different time steps for
$n=20000$ and $k=200$. The probability $p_{t}(x)$ was estimated by fixing the
firing set, and then repeatedly redrawing the graph edges. The probability of
$x$ is defined as the percentage of times $x$ was chosen by the top-k
function. The left figure illustrates the input due to $A_{0}$, which is
uniformly random on $[0,1]$. The right figure shows the input two steps later,
when the set $A_{2}$ has converged to lie in a single, narrow interval.

The proof will be divided into three parts. First, we will characterize the
structure of $A_{1}$. The set $A_{0}$ is drawn uniformly at random from the
set of vertices. However, due to the Poisson clumping phenomenon [Ald13],
there will be a few regions of the hidden variable space which have a
significantly higher concentration of points than average. Vertices with
hidden variables in these regions will have larger inputs $F_{0}$. We have the
following theorem describing points which have a significant probability of
exceeding the threshold at Step $0$.

######  Theorem 1.3.

Let $n=k^{\beta}$ for some constant $\beta\geq 2+d$. Then, with high
probability, $A_{1}$ can be covered by $k^{\frac{1}{4}+o(1)}$ balls, each of
radius $O(\sigma\sqrt{\ln\ln k})$ and pairwise separated by a distance of at
least $2\sigma\sqrt{\ln n}$.

By the assumption that $\sigma=\Theta(k^{-1/d})$, the set $A_{1}$ is contained
in a small region relative to $[0,1]^{d}$.

The next step of the analysis will show that $A_{t}$ will gradually become
concentrated in a single ball of radius $O(\sigma\sqrt{\ln k/k})$. The key
idea is that each individual ball shrinks with high probability at each step,
almost in place.

The statement of this lemma is below. We use $r(S)$ to denote the radius of
the smallest ball containing a set $S$.

######  Lemma 1.4.

Suppose that $A_{t}\subset I_{1}\cup\dots\cup I_{i}$, where
$i=O(k^{1/4+o(1)})$, and for each $j$, $I_{j}$ is a ball of radius $r_{j}$,
bounded by $r(I_{j})=\Omega(\sigma\sqrt{\ln k/|I_{j}\cap A_{t}|})$ and
$r(I_{j})<C\sigma\sqrt{\ln\ln k}$ for some constant $C$. Also assume that the
distance between any two balls is at least $2(1-o(1))\sigma\sqrt{\ln n}$. At
the next step, with high probability, $A_{t+1}\subset I_{1}^{\prime}\cup
I_{2}^{\prime}\cup\dots\cup I_{i}^{\prime}$, where
$d(I_{j},I_{j}^{\prime})=\max_{x\in I_{j}^{\prime}}\min_{y\in I_{j}}\lVert
x-y\rVert<5(r(I_{j})-r(I_{j}^{\prime}))$, and
$r(I_{j}^{\prime})\leq(1-\frac{1}{(\ln k)^{c}})r(I_{j})$ for an absolute
constant $c$.

Up to some small deviations, each ball determined by time Step $1$ will either
disappear or shrink slightly in place. Moreover, the surviving balls will
remain separated; the maximum distance moved by a single ball by time $t$ is
$5(r(I^{(0)}_{j})-r(I^{(t)}_{j}))=O(\sigma\sqrt{\ln\ln k})$. Using this, we
will show convergence to a structure contained within a single ball of radius
$O(\sigma\sqrt{\ln k/k})$. This is the content of Theorem 1.2.

This structure is, to within a log factor, the smallest subgraph we can expect
$A_{t}$ to converge to. Within a region of radius $O(\sigma k^{-1/2})$, the
edge probability is greater than $e^{-1/k}$; hence, the degree of any vertex
to $A_{t}$ will be almost constant in this interval. The probability that a
vertex fires remains uniform in the center and drops off toward $\frac{1}{n}$
at the ends of the interval.

Finally, we show that conditioned on the structure of the graph, almost all of
$A_{t}$ is contained within a ball of radius $O(\sigma k^{-1/3+\epsilon})$ for
all $t\geq t^{*}$.

######  Theorem 1.5.

For all $t\geq t^{*}$, with high probability, there exists a ball $I_{t}$ with
radius $r=\sigma k^{-1/3+\epsilon}$, for a constant $\epsilon>0$, such that
$|A_{t}\cap I_{t}|>k-k^{2/3}$.

The proof of this theorem directly implies the following structural property
of geometric random graphs, which holds for all $S\subset V$ of size $k$ that
are mostly contained in a small ball in $[0,1]^{d}$. With high probability
over all such sets, the set of $k$ vertices with the highest degree from $S$
are also mostly contained in a small ball.

######  Corollary 1.6.

Let $G=(V,E)$ be a geometric random graph such that for every vertex $x\in V$,
its location $h_{x}$ is chosen uniformly at random from $[0,1]^{d}$ and for
every pair $x,y\in V$, $\mathbb{P}((x,y)\in E)=e^{-\lVert h_{x}-h_{y}\rVert
k^{2/d}}$, where $k=O(|V|^{\frac{1}{2+d}})$. Let $r=k^{-1/d-1/3+\epsilon}$ for
any $\epsilon>0$. Then, with high probability (over the edges of $G$), for
every set $S\subset V$ of size $k$, if at least $k-k^{2/3}$ points of $S$ are
contained in a ball of radius $r$, then there exists a ball of radius $r$
which contains at least $k-k^{2/3}$ points of $S^{\prime}$, the set of $k$
points with the highest degree from $S$.

##  2 Analysis of the discrete $k$-cap process

In Appendix 5.1, we will introduce a few general results on probability which
play key roles in the proof. In Section 2.1, we describe the structure of
$A_{1}$ given the random initial firing set $A_{0}$. Lastly, in Section 2.2,
we investigate the evolution of $A_{t}$ as $t$ increases, and we prove the
main theorem on the convergence of the process, stated in Theorem 1.2.

###  2.1 Characterization of $A_{1}$

Since the initial firing set $A_{0}$ is chosen uniformly at random from $V$,
$A_{1}$ is concentrated near dense sections of $A_{0}$. We argue that the
probability that $x\in A_{1}$ can be characterized by conditioning on the
number of points of $A_{0}$ within $\tilde{O}(\sigma)$ of $x$. By analyzing
the distribution of dense subsets of a set of uniform random variables, we
show that $A_{1}$ is contained within a union of $k^{1/4+o(1)}$ small balls.

First, in Lemma 2.0.1, we give a lower bound on the first threshold, $C_{0}$,
by examining the maximum number of uniform random points within a ball of
radius $r$. There are, with high probability, at least $k$ vertices of $V$
which connect to the every point in the intersection of the ball with $A_{0}$.

Next, Lemma 2.0.2 shows that if $|\\{y\in A_{0}:\lVert
x-y\rVert=O(\sigma\sqrt{\ln\ln k})\\}|$ is not large, $x$ has a very small
probability of achieving an input of $C_{0}$. This implies that $A_{1}$ must
be solely contained within high-density regions of $A_{0}$.

Finally, we combine these two lemmas to prove Theorem 1.3, restated later in
this section. Since the number of high-density regions can be bounded of
$A_{0}$ using a combinatorial argument, $A_{1}$ must be contained within
$k^{1/4+o(1)}$ small balls.

######  Lemma 2.0.1.

With probability $1-o(1)$ (where $\ln^{(3)}k=\ln\ln\ln k$):

$C_{0}\geq\frac{\ln k}{\ln\ln k}\left(1+\frac{1}{4}\frac{\ln^{(3)}k}{\ln\ln
k}\right)$

###### Proof.

Consider a graph constructed on $A_{0}$ as follows. For any $a_{1},a_{2}\in
A_{0}$, add an edge if $\lVert a_{1}-a_{2}\rVert<\frac{1}{2}\sigma\sqrt{\ln\ln
k}$. Denote the maximum degree of this graph as $\Delta_{k}$. $\Delta_{k}+1$
is the maximum intersection of $A_{0}$ with a circle of radius
$r=\frac{1}{2}\sigma\sqrt{\ln\ln k}$.

By Lemma 5.0.3,

$\displaystyle\Delta_{k}$ $\displaystyle\geq\frac{\ln k}{\ln\ln
k-\ln(\sigma^{d}k(1/4\ln\ln k)^{d/2})}$ $\displaystyle=\frac{\ln k}{\ln\ln
k-d/2\ln^{(3)}k+O(1)}$ $\displaystyle\geq\frac{\ln k}{\ln\ln
k}\left(1+\eta\right)=M_{k}\qquad\mbox{where }\eta=\frac{\ln^{(3)}k}{4\ln\ln
k}.$

As per above, there exists a ball with $M_{k}$ points of $A_{0}$ almost
surely. Call this ball $I$.

The maximum distance within the ball is $\sigma\sqrt{\ln\ln k}$. For any $x\in
I$, the probability that $x$ connects to $M_{k}$ points is at least
$g(x,x+v)^{M_{k}}$, where $v$ is a vector of size $\sigma\sqrt{\ln\ln k}$.
Substituting:

$\displaystyle\mathbb{P}(F_{0}(x)\geq M_{k})$
$\displaystyle\geq\exp\left(-\frac{(\sigma\sqrt{\ln\ln
k})^{2}}{2\sigma^{2}}\right)^{M_{k}}=\exp\left(-\frac{\ln\ln
k}{2}\right)^{(1+\eta)\frac{\ln k}{\ln\ln k}}$
$\displaystyle=k^{-\frac{(1+\eta)}{2}}$

By Lemma 5.0.1, $|I\cap V|=\Omega\left(\frac{\text{Vol}(I)\cdot n}{\log
n}\right)=\Omega\left(\sigma^{d}(\ln\ln k)^{d/2}\cdot\frac{n}{\log n}\right)$.
By the assumption that $\sigma=\Theta(k^{-1/d})$ and $n=k^{\beta}$, there are
$k^{\beta-1-o(1)}$ vertices of $G$ in $I$.

The expected number of points with degree $M_{k}$ from $|A_{0}\cap I|$ is at
least $k^{\beta-1-o(1)}k^{-\frac{(1+\eta)}{2}}$, which is much greater than
$k$. Therefore, there are at least $k$ points with input $M_{k}$ with high
probability. This implies that the threshold $C_{0}$ is bounded from below by
$M_{k}$. ∎

######  Lemma 2.0.2.

For any $x\in[0,1]^{d}$, define $B_{r}(x)=\\{y\in[0,1]^{d}:\lVert
x-y\rVert<r\\}$. Let $r=\sigma\sqrt{24\beta\ln\ln k)}$. Suppose that the
overlap between $B_{r}(x)$ and $A_{0}$ is at most $\frac{3\ln k}{4\ln\ln k}$.
Conditioned on this event, the probability that $x\in A_{1}$ is at most
$\frac{1}{n^{3}}$.

###### Proof.

Let $r=\alpha\sigma\sqrt{\ln\ln k}$. Suppose $|B_{r}(x)\cap
A_{0}|\leq\frac{3\ln k}{4\ln\ln k}$.

By Lemma 2.0.1, if $x\in A_{1}$, then $F_{0}(x)\geq C_{0}\geq\frac{\ln
k}{\ln\ln k}$. Hence, by assumption, $x\in A_{1}$ only if it achieves an input
of $M=\frac{\ln k}{4\ln\ln k}$ from outside $B_{r}(x)$.

Conditioned on $|B_{r}(x)\cap A_{0}|=\lambda k$, the remaining $(1-\lambda)k$
points are distributed uniformly on $[0,1]^{d}\setminus B_{r}(x)$.

By definition, $\mathbb{P}(\mathbbm{1}_{(x,Y)}\mid
Y=y)=g(x,y)=\exp\left(-\lVert x-y\rVert^{2}/2\sigma^{2}\right)$. Let $f_{r}$
be the conditional distribution function of $\lVert y-x\rVert$, which has
support on $(r,\sqrt{d}]$ ($\sqrt{d}$ being the longest diagonal of the
hypercube $[0,1]^{d}$). Define $\partial B_{r}(x)=\\{y\in[0,1]^{d}:\lVert
x-y\rVert=r\\}$ to be the spherical shell of radius $r$ around $x$.

$f_{r}(\rho)=\frac{\text{Vol}(\partial
B_{\rho}(x)\cap[0,1]^{d})}{1-\text{Vol}(B_{r}(x))}$

The boundaries of the hypercube make $f_{r}$ somewhat difficult to calculate.
Therefore, we will ignore the boundaries and set
$f_{r}(\rho)<\frac{\text{Vol}(\partial B_{\rho}(x))}{1-\text{Vol}(B_{r}(x))}$.
Note that $\text{Vol}(\partial
B_{\rho}(x))=\frac{2\pi^{d/2}}{\Gamma(d/2)}\rho^{d-1}$.

$\displaystyle\mathbb{E}[\mathbbm{1}_{(x,y)}\mid y\notin B_{r}(x)]$
$\displaystyle=\int_{r}^{\sqrt{d}}e^{-\rho^{2}/(2\sigma^{2})}f_{r}(\rho)\,d\rho$
$\displaystyle\leq\frac{1}{1-\text{Vol}(B_{r}(x))}\int_{r}^{\sqrt{d}}e^{-\rho^{2}/(2\sigma^{2})}\text{Vol}(\partial
B_{\rho}(x))\,d\rho$ $\displaystyle\leq
2\frac{2\pi^{d/2}}{\Gamma(d/2)}\int_{r}^{\infty}\rho^{d-1}e^{-\rho^{2}/(2\sigma^{2})}\,d\rho$
$\displaystyle=\frac{4\pi^{d/2}\sigma^{d}}{\Gamma(d/2)}\int_{r/\sigma}^{\infty}z^{d-1}e^{-z^{2}/2}\,dz$

This integral can be estimated by observing that for $r$ sufficiently large,
$z^{d-1}e^{-z^{2}/2}$ is decreasing on $[r/\sigma,\infty]$. Therefore,

$\int_{r/\sigma}^{\infty}x^{d-1}e^{-x^{2}/2}\,dx\leq\left(\frac{\sigma}{r}\right)^{d-2}\int_{r/\sigma}^{\infty}xe^{-x^{2}/2}\,dz=\left(\frac{r}{\sigma}\right)^{d-2}e^{-r^{2}/(2\sigma^{2})}$
(1)

Returning to the original equation, for any $d\geq 1$:

$\mathbb{E}[\mathbbm{1}_{(x,y)}\mid y\notin
B_{r}(x)]\leq\frac{4\pi^{d/2}\sigma^{d}}{\Gamma(d/2)}\left(\frac{r}{\sigma}\right)^{d-2}e^{-r^{2}/(2\sigma^{2})}=\Theta(1)\sigma^{d}\left(\frac{r}{\sigma}\right)^{d-2}e^{-r^{2}/2\sigma^{2}}$

Substituting $r=\sigma\alpha\sqrt{\ln\ln k}$, this equals
$\Theta(1)\sigma^{d}(\ln k)^{-\alpha^{2}/2}(\sqrt{\ln\ln k})^{d-2}$. Again
recalling $\sigma^{d}=\Theta(1/k)$,

$\mathbb{E}[\mathbbm{1}_{(x,y)}\mid y\notin B_{r}(x)]\leq p=O(1/k)(\ln
k)^{-\alpha^{2}/2}(\alpha\sqrt{\ln\ln k})^{d-2}$

. We can bound the distribution of $F_{0}(x)$ by a binomial with probability
$p$. In particular, $\mathbb{P}(F_{0}(x)>C_{0})$ is bounded above by
$\mathbb{P}\left(B>\frac{\ln k}{4\ln\ln k}\right)$, where $B\sim Bin(k,p)$.
This quantity can be tightly bounded using Lemma 5.0.5.

$\mathbb{P}\left(B>\frac{\ln k}{4\ln\ln
k}\right)\leq\exp\left(-kD\left(\frac{\ln k}{4k\ln\ln k}\mid\mid
p\right)\right)$

Bounding the divergence term:

$\displaystyle D\left(\frac{\ln k}{4k\ln\ln k}\mid\mid p\right)$
$\displaystyle=\frac{\ln k}{4k\ln\ln k}\ln\frac{\ln k}{4kp\ln\ln
k}+(1-\frac{\ln k}{4k\ln\ln k})\ln\frac{1-\frac{\ln k}{4k\ln\ln k}}{1-p}$
$\displaystyle\geq\frac{\ln k}{4k\ln\ln k}\ln\frac{\ln k}{4kp\ln\ln
k}+p-\frac{\ln k}{4k\ln\ln k}\text{ using }\ln x\geq 1-1/x\;\forall x>0$
$\displaystyle=\frac{\ln k}{4k\ln\ln k}\ln\frac{\ln
k^{1+\alpha^{2}/2}}{O(1)(\ln\ln k)^{1+(d-2)/2}}+\Theta(\frac{1}{k})(\ln
k)^{-\alpha^{2}/2}(\alpha\sqrt{\ln\ln k})^{d-2}-\frac{\ln k}{4k\ln\ln k}$
$\displaystyle\geq\frac{\ln
k}{k}\left[\frac{1+\alpha^{2}/2}{4}-\frac{1+(d-2)/2}{4}\frac{\ln^{(3)}k}{\ln\ln
k}-\frac{O(1)}{\ln\ln k}\right]$

Plugging this into the original bound, $\mathbb{P}\left(B>\frac{\ln k}{4\ln\ln
k}\right)\leq k^{-\frac{1+\alpha^{2}/2}{4}+o(1)}$

Since $n=k^{\beta}$ by definition, we can choose $\alpha=\sqrt{24\beta}$.
Then, $\mathbb{P}(F_{0}(x)>C_{0})\leq\mathbb{P}\left(B>\frac{\ln k}{4\ln\ln
k}\right)\leq 1/n^{3}$ ∎

See 1.3

###### Proof of Theorem 1.3.

We apply Lemma 2.0.2 and take the union bound over all $x$ in the graph to
conclude the following: with probability, $1-1/n^{2}$, $x\in A_{1}$ only if
the ball $B_{r}(x)$, where $r=\sigma\sqrt{24\beta\ln\ln k}$, contains more
than $\frac{3\ln k}{4\ln\ln k}$ points. Since $1/n^{2}$ is summable, this is
true almost surely.

Since the expected number of points of $A_{0}$ in $B_{r}(x)$ is
$k*\text{Vol}(B_{r}(x))=O((\ln\ln k)^{d/2})$, the number of such high density
regions will be relatively small.

To argue this, we consider $d+1$ overlapping partitions of $[0,1]^{d}$ into
boxes. Let $L=2\sigma\sqrt{24\beta\ln\ln k}$. First, tile $[0,1]^{d}$ with
boxes of width $L$. Then, shift each interval by half its width in each
dimension, leading to $d$ alternate partitions of $[0,1]^{d}$.

For any $x$, the ball $B_{\sigma\sqrt{24\beta\ln\ln k}}(x)$ must be fully
contained in a box $I_{i}$ in at least one partition for some index $i$.
Consider the probability that a given box $I_{i}$ contains $\frac{3\ln
k}{4\ln\ln k}$ points of $A_{0}$.

For each point in $A_{0}$, the probability that it lands in $I_{i}$ is
$\text{Vol}(I_{i})=(2\sigma\sqrt{24\beta\ln\ln k})^{d}=\Theta(1)(\ln\ln
k)^{d/2}/k$. Therefore, the number of points in $I_{i}$ is $|A_{0}\cap
I_{i}|\sim Bin(k,\text{Vol}(I_{i}))$.

Using the binomial bound in Lemma 5.0.5, the probability that $|I_{i}\cap
A_{0}|$ exceeds $3\ln k/4\ln\ln k$ is at most:

$\mathbb{P}\left(|I_{i}\cap A_{0}|>\frac{3\ln k}{4\ln\ln
k}\right)\leq\exp\left(-kD\left(\frac{3\ln k}{4k\ln\ln
k}\mid\mid\text{Vol}(I_{i})\right)\right)$ (2)

Bounding the divergence term (Using the inequality $\ln x\geq 1-1/x$):

$\displaystyle D$ $\displaystyle\left(\frac{3\ln k}{4k\ln\ln
k}\mid\mid\text{Vol}(I_{i})\right)=\frac{3\ln k}{4k\ln\ln
k}\ln\frac{\Theta(1)\ln k}{(\ln\ln k)^{1+d/2}}+\left(1-\frac{3\ln k}{4k\ln\ln
k}\right)\ln\frac{1-\frac{3\ln k}{4k\ln\ln k}}{1-\Theta(1)(\ln\ln k)^{d/2}/k}$
$\displaystyle\geq\frac{3\ln k}{4k}-\frac{O(1)\ln k\ln^{(3)}k}{k\ln\ln
k}+\left(1-\frac{3\ln k}{4k\ln\ln k}\right)\left(1-\frac{1-\Theta(1)(\ln\ln
k)^{d/2}/k}{1-\frac{3\ln k}{4k\ln\ln k}}\right)$ $\displaystyle\geq\frac{3\ln
k}{4k}-\frac{O(1)\ln k\ln^{(3)}k}{k\ln\ln k}-\frac{3\ln k}{4k\ln\ln
k}+\Theta(1/k)(\ln\ln k)^{d/2}$ $\displaystyle=\frac{1}{k}\left[\frac{3}{4}\ln
k-\frac{O(1)\ln k\ln^{(3)}k}{\ln\ln k}\right]$

Substituting back into equation 2:

$\mathbb{P}\left(|I_{i}\cap A_{0}|>\ln k/\ln\ln
k\right)\leq\exp\left(-\frac{3}{4}\ln k+\frac{O(1)\ln k\ln^{(3)}k}{\ln\ln
k}\right)=k^{-\frac{3}{4}+\frac{O(1)\ln^{(3)}k}{\ln\ln k}}$

There are $\frac{d+1}{\text{Vol}(I_{i})}=\Theta\left(\frac{k}{(\ln\ln
k)^{d/2}}\right)$ such intervals. The size of $|B_{i}\cap A_{0}|$ for each
partition can be thought of as the loads in a ‘balls into bins’ problem; thus,
the number of points in non-overlapping boxes are negatively correlated.

With high probability, the number of such intervals with enough points is
$k^{1/4+o(1)}$.

The loads of the bins $I_{i}$ are invariant to permutation; therefore, the
probability that two intervals within a distance of $2\sigma\sqrt{\ln n}$ have
a large enough load is $o(1)$.

The same can be said for each shifted partition. Therefore, the bins which
achieve high input are of size $\Theta(L)=\Theta(\sigma\sqrt{\ln\ln k})$ and
separated by a distance of $2\sigma\sqrt{\ln n}$. ∎

###  2.2 Convergence of $A_{t}$

In this section, we will prove the main Lemma 1.4, which will lead to the
proof of Theorem 1.2. In Theorem 1.3, we have proved that $A_{1}$ can be
covered by $k^{1/4+o(1)}$ balls of radius $O(\sigma\sqrt{\ln\ln k})$, and
separated by at least $2\sigma\sqrt{\ln n}$. There are two key properties of
this system which make the analysis tractable. First, the separation condition
allows us to analyze each interval as a separate system. If $x\in I_{a}$ and
$y\in I_{b}$, $g(x,y)<\exp\left(-\frac{4\sigma^{2}\ln
n}{2\sigma^{2}}\right)=n^{-2(1-o(1))}$. Therefore, with high probability, the
subgraphs defined by $I_{a}$ and $I_{b}$ are independent; this means that all
$x\in A_{t}$ will not receive input from outside its interval. Second, since
the graph is directed, the edge $\mathbbm{1}_{(x,y)}$ is independent of
$\mathbbm{1}_{(y,x)}$. Additionally we prove in Lemma 2.0.4 that for any
$t=\text{polylog}(k)$, all points which fire at $t$ are ‘new’ (i.e., they have
not fired at a previous step) with high probability. This lets us make the
simplifying assumption that $F_{t}(x)$ is a sum of independent indicators.
Using these two key simplifications, we prove that with high probability, each
separated interval shrinks to a size of $O(\sigma\sqrt{\ln k/k})$.

We will suppose that the hypothesis of Theorem 1.3 holds for a step $t\geq 1$;
$A_{t}$ can be covered by $O(k^{1/4+o(1)})$ sufficiently separated balls.
Then, we will prove that the separation and coverage continue to hold by
induction.

Define $A_{t}\subset I_{1}\cup I_{2}\cup\dots\cup I_{i}$, where each $I_{j}$
is a ball of radius $O(\sigma\sqrt{\ln\ln k})$, and all pairs $I_{a}$, $I_{b}$
are separated by a gap of at least $2(1-o(1))\sigma\sqrt{\ln n}$. Also define
$E[x]=\mathbb{E}F_{t}(x)=\sum_{z\in A_{t}}g(x,z)$, and
$V[x]^{2}=\operatorname{Var}F_{t}(x)=\sum_{z\in A_{t}}g(x,z)(1-g(x,z))$. Note
that $E[x]$ and $V[x]$ depend implicitly on $t$.

The following lemmas will be used to bound $C_{t}$ at each time step. Using
this, we can get precise bounds on $\mathbb{P}(F_{t}(x)>C_{t})$.

######  Lemma 2.0.3.

For any vector direction v and point $x\in[0,1]^{d}$,
$\left|\nabla_{v}E[x]\right|<\frac{k}{\sigma}\sqrt{d/e}$.

###### Proof of Lemma 2.0.3.

For any $i\in\\{0,1,\dots,d-1\\}$:

$\frac{\partial}{\partial x_{i}}E[x]=\sum_{z\in A_{t}}\frac{\partial}{\partial
x_{i}}g(x,z)=\sum_{z\in
A_{t}}-\frac{x_{i}-z_{i}}{\sigma^{2}}\exp\left(\frac{-\lVert
x-z\rVert^{2}}{2\sigma^{2}}\right)$

Let $\hat{x}=\frac{x-z}{\sigma}$. The maximum of
$\left|\hat{x}\exp\left(\frac{-\hat{x}^{2}}{2}\right)\right|$ occurs at
$e^{-1/2}$. Thus, we have

$\left|\frac{\partial}{\partial x_{i}}E[x]\right|\leq\sum_{z\in
A_{t}}\frac{|x_{i}-z_{i}|}{\sigma^{2}}\exp\left(\frac{-\lVert
x-z\rVert^{2}}{2\sigma^{2}}\right)<\sum_{z\in
A_{t}}\frac{1}{\sigma}e^{-1/2}=\frac{k}{\sigma}e^{-1/2}$

For any unit vector $v$:

$\left|\nabla_{v}E[x]\right|<\frac{k}{\sigma}e^{-1/2}v\cdot\mathbf{1}=\sqrt{d}e^{-1/2}\frac{k}{\sigma}$

∎

For this proof to be viable, we will need to show that $F_{t}(x)$ is the sum
of independent indicators. By definition of the graph structure, each edge
$\mathbbm{1}_{(y,x)}$ is drawn independently. However, we will also need to
show that, for each $y\in A_{t}$, its edges $\mathbbm{1}_{(y,x)}$ have not
been used in previous computations. This follows from the next lemma.

######  Lemma 2.0.4.

Suppose $t=O((\ln k)^{c})$ for a constant $c$. Then, with probability at least
$1-\frac{1}{k^{1/2-o(1)}}$

$A_{0}\cap A_{1}\cap\dots\cap A_{t}=\emptyset$

###### Proof.

Suppose at time $s$, $\\{A_{0},A_{1}\dots A_{s}\\}$ are pairwise disjoint.
Therefore, at time $s$, the edges $\\{\mathbbm{1}_{(y,x)}:y\in
A_{s},x\in[n]\\}$ have not been examined by the $k$-cap function, and they are
conditionally independent.

Now, we will compute the probability that $|A_{s+1}\cap A_{i}|>0$ for some
$i\leq s$. By Lemma 5.0.1, there are at least
$\Theta(1)\sigma^{d}k^{-d/2}n/\log n=\Theta(k^{\beta-d/2-1}/\log n)$ points
within $\sigma k^{-1/2}$ of $x$. By Lemma 2.0.3, for all $z\in B_{\sigma
k^{-1/2}}(x)$, $\mathbb{E}F_{s}(z)>\mathbb{E}F_{s}(x)-(ek)^{1/2}$. For such a
$z$, $\mathbb{P}(F_{s}(z)>C_{s+1})$ differs from
$\mathbb{P}(F_{s}(z)>C_{s+1})$ by at most a constant factor. Thus, the
probability that any given $x$ is chosen is
$p_{s}(x)<k^{-\beta+d/2+1+o(1)}<k^{-3/2+o(1)}$ by the definition of $\beta$.
There are $sk$ points in $A_{0}\cup A_{1}\cup\dots\cup A_{s}$, so the
probability that any given $y\in A_{0}\cup A_{1}\cup\dots\cup A_{s}$ is in
$A_{s+1}$ is at most $sk*k^{-3/2+o(1)}=O(k^{-1/2+o(1)})$. Therefore, the
probability that $(A_{0}\cup A_{1}\cup\dots\cup A_{s})\cap A_{s+1}=\emptyset$
is at least $1-\frac{1}{k^{1/2-o(1)}}$.

The probability that this holds for all $s<t$ is
$(1-\frac{1}{k^{1/2-o(1)}})^{t}\approx 1-\frac{t}{k^{1/2-o(1)}}$. Since $t$ is
$\text{polylog}(k)$, this is at least $1-\frac{1}{k^{1/2-o(1)}}$. ∎

Lemma 2.0.4 implies that, conditioned on the set $A_{t}$, $F_{t}(x)=\sum_{z\in
A_{t}}\mathbbm{1}_{(z,x)}$ is a sum of independent indicators (with no
dependence on previous time steps). Therefore, $C_{t}$ can be bounded using
standard concentration bounds as follows:

######  Lemma 2.0.5.

At any step $t=O((\log k)^{c})$, assuming the conditions of Lemma 1.4, with
high probability, $C_{t}\geq\max_{x}E[x]$

###### Proof of Lemma 2.0.5.

By Lemma 5.0.1, for any point $x$, there are $\Omega(n\cdot(\sigma k^{-1}\log
n)^{d})$ points of $V$ in a radius of $\sigma k^{-1}\log n$ of $x$. By the
assumption that $n\geq k^{2+d}$, this is $\Omega(k\log n)$.

For any $y\in B_{\sigma k^{-1}}\log n(x)$, Lemma 2.0.3 implies:

$E[y]>E[x]-\sqrt{d/e}\log n$

Therefore, if $C_{t}=E[x]$, then there are $\tilde{\Omega}(k)$ points where
$E[y]>C_{t}-O(\log n)$. Here we will use Lemma 2.0.4, which tells us that each
$F_{t}(y)$ is independent conditioned on $A_{t}$. Hence, Chernoff type bounds
apply; if $\mathbb{P}\left(F_{t}(y)>E[y]+O(\log n)\right)=\Theta(1)$, then
with high probability there are $k$ points that exceed $C_{t}$.

Using the loose bound given in [Vol96], we can bound
$\mathbb{P}(F_{t}(x)>C_{t})$ using the CDF of the normal distribution. For any
sum of independent indicators $S$ with mean $\mu$ and variance $\sigma$, the
CDF can be approximated as follows:

$\sup_{m}\left|\mathbb{P}(S\leq
m)-G\left(\frac{m+1/2-\mu}{\sigma}\right)\right|\leq\frac{\sigma+3}{4\sigma^{3}}<\frac{1}{\sigma^{2}}$

Where
$G(x)=\Phi(x)-\frac{\gamma}{6\sigma^{3}}(x^{2}-1)\frac{e^{-x^{2}/2}}{\sqrt{2\pi}}$,
and $\gamma=\mathbb{E}[(S-\mu)^{3}]$ is the skewness. This holds for any
$\sigma\geq 10$.

We can assume that the variance of $y$, $V[y]^{2}$, exceeds $(\log k)^{2}$;
otherwise, $E[y]=\sum_{y\in A_{t}}=k(1-o(1/k))$, so we can assume that
$C_{t}=k$.

Fix $y\in B_{\sigma k^{-1}\log n}(x)$. From the above equation, we find that
for any $t>0$:

$\mathbb{P}\left(F_{t}(y)>E[y]+tV[y]-1/2\right)>1-\left[G(t)+\frac{1}{V[y]^{2}}\right]$

Substituting the value of $G$:

$\mathbb{P}\left(F_{t}(y)>E[y]+tV[y]-1/2\right)>1-\Phi(t)+\frac{\gamma(t^{2}-1)}{6\sqrt{2\pi}V[y]^{3}}e^{-t^{2}/2}-\frac{1}{V[y]^{2}}$

Here, we will make two approximations. First, the exact value of $\gamma$ is
$\sum_{z\in A_{t}}g(y,z)(1-g(y,z))(1-2g(y,z))$. Therefore, $\gamma>-V[y]^{2}$,
so $\gamma(t^{2}-1)>-V[y]^{2}t^{2}$. Second, we will substitute the lower tail
bound for
$1-\Phi(t)\geq\frac{1}{\sqrt{2\pi}}\left(t^{-1}-t^{-3}\right)e^{-t^{2}/2}\geq\frac{1}{t\sqrt{8\pi}}e^{-t^{2}/2}$
for $t\geq 2$.

This leaves us with:

$\mathbb{P}\left(F_{t}(y)>C_{t}=E[y]+tV[y]-1/2\right)>\frac{1}{t\sqrt{8\pi}}e^{-t^{2}/2}-\frac{t^{2}}{6\sqrt{2\pi}V[x]}e^{-t^{2}/2}-\frac{1}{V[y]^{2}}$

Setting $t=O(1)$, this occurs with constant positive probability. ∎

Finally, we can use the above lemma to relate the probability that a point
fires at time $t+1$ to its expected value at time $t$.

######  Lemma 2.0.6.

Let $y\in I_{j}$, and $\hat{k}=|I_{j}\cap A_{t}|$. If there exists an $x\in
I_{j}$ such that
$\mathbb{E}F_{t}(x)>\mathbb{E}F_{t}(y)+\sqrt{6\beta(\hat{k}-\mathbb{E}F_{t}(y))\ln
k}$, then $\mathbb{P}(F_{t}(y)>C_{t})<\frac{1}{n^{3}}$

###### Proof.

Let $X=\hat{k}-F_{t}(y)$. By Lemma 5.0.4,
$\mathbb{P}(X<(1-\epsilon)\mathbb{E}X)\leq\exp\left(-\epsilon^{2}\mathbb{E}X/2\right)$.

Thus, setting $\epsilon=\frac{C-F_{t}(y)}{\mathbb{E}X}$, we have

$\mathbb{P}(F_{t}(y)>C)=\mathbb{P}(X<\mathbb{E}X-(C-\mathbb{E}F_{t}(y))\leq\mathbb{P}(X<\mathbb{E}X(1-\epsilon))\leq\exp\left(-\frac{\epsilon^{2}\mathbb{E}X}{2}\right)$

By Lemma 2.0.5, $C_{t}\geq\mathbb{E}F_{t}(x)$ for all $x$. Hence, by the
assumption,
$C-\mathbb{E}F_{t}(y)\geq\mathbb{E}F_{t}(x)-\mathbb{E}F_{t}(y)>\sqrt{6\beta\mathbb{E}X\ln
k}$. Substituting this value for $\epsilon\mathbb{E}X$,

$\mathbb{P}(F_{t}(y)>C)\leq\exp\left(-\frac{6\beta\ln
k}{2}\right)=k^{-3\beta}=n^{-3}$

∎

Now, we are ready to prove Lemma 1.4. This lemma will show that the radius of
each ball shrinks at each step; that is $A_{t}$ is contained within a union of
balls of radius $r_{t}$, where $r_{t}$ is a decreasing function of $t$. The
main idea of the proof is to show that, regardless of the actual positions of
points in $A_{t}\cap I$, vertices toward the center of $I$ have a small
advantage over vertices toward the edge. Thus, either (1) the position of
points in $A_{t}\cap I$ is particularly unbalanced, and $A_{t+1}$ shifts
toward one side, or (2), the radius of $I$ shrinks in all directions.

###### Proof of Lemma 1.4.

(a) Case 1

(b) Case 2

Figure 3: The division of the ball $I$ into two subregions. In case 1, there
exists a division of $I$ into two sub regions $R_{1}$ and $R_{2}$ such that
$R_{2}\cap A_{t}<\hat{k}/(\ln k)^{\alpha}$. We bound the gradient of $E[z]$
for all $z$ in the region enclosed by the dotted line. In case 2, no such
division exists. We prove that for $y$ between the outer and inner circles,
$\mathbb{P}(y<1/n^{3})$. In both cases, we prove that $A_{t+1}$ falls in the
orange circle with high probability.

Fix one ball $I=B_{r}(p)$. Let $r$ be the radius of $I$ and $p$ be its center.

To assist with the proof, we will define the following values. Let
$\hat{k}=|A_{t}\cap I|$; we can assume that $\hat{k}>k^{3/4-o(1)}$, since an
interval with asymptotically fewer points will be eliminated at the next step.
Define $dist(I,z)=\min_{y\in I}\lVert y-z\rVert$. Finally, for any set
$S\subset[0,1]^{d}$, let $F_{t}(z;S)=\sum_{y\in A_{t}\cap
S}\mathbbm{1}_{(y,z)}$.

We will prove that with high probability, $\\{x\in[0,1]^{d}:F_{t}(x;I)\geq
C_{t}\\}$ can be covered by $I^{\prime}=B_{r^{\prime}}(p^{\prime})$, where
$r^{\prime}=(1-1/(\log k)^{c})r$ and $\max_{z\in
I^{\prime}}dist(I,z)<5(r(I)-r(I^{\prime}))$. Call this statement (*).

If statement (*) holds for each $I=I_{i}$, the lemma is proven. This holds by
the separation assumption; if $dist(I,x)<\sigma\sqrt{\ln n}$, then for all
$y\in A_{t}\setminus I$, $g(x,y)<1/n^{2(1-o(1))}$. Therefore,
$F_{t}(x;I)=F_{t}(x)-o(1)$ with high probability.

To prove this statement, we will consider two cases. In case 1, we suppose
that the distribution of $A_{t}\cap I$ is imbalanced. In particular, there
exists a half space dividing $I$ into two spherical caps, with heights $r/4$
and $7r/4$, such that the larger segment contains only $\hat{k}/(\ln
k)^{\alpha}$ points of $A_{t+1}$ (for an $\alpha\geq 1$). See Figure 3. We
will show that given this imbalance, statement (*) holds.

In case 2, no such division exists. We will show that for any point $z$ near
the boundary of $I$ is disadvantaged compared to a point near the center.
Thus, $I^{\prime}=B_{r^{\prime}}(p)$ for an $r^{\prime}=(1-1/(\log k)^{c})r$.
See Figure 3.

For both cases, the argument will use a bound on the gradient of $E[z]$. With
this, we will construct a point $w$ such that $E[w]-E[z]$ is large, and use
Lemma 2.0.6 to argue that $\mathbb{P}(z\in A_{t+1})<1/n^{3}$.

Consider two cases:

Case 1: there exists a half space dividing $I$ into two spherical caps,
$R_{1}$ and $R_{2}$, with heights $r/4$ and $7r/4$, such that $|R_{2}\cap
A_{t}|\leq\hat{k}/(\ln k)^{\alpha}$, where
$\alpha=1+\max(2r^{2}/(\sigma^{2}\ln\ln k),1)$. In this case, the ball is
“imbalanced” in the sense that one portion of of the ball contains the vast
majority of the points.

Without loss of generality, let $p=[r,0,0,\dots,0]$, $R_{1}=\\{y\in
I:y_{1}\leq r/4\\}$, and $R_{2}=\\{y\in I:y_{1}>r/4\\}$ (as illustrated in
Figure 3). Let $z=[z_{1},z_{2},\dots,z_{n}]$ where $z_{1}\geq 3r/8$ and
$dist(I,z)=O(\min\\{r,\sigma\hat{k}^{-1/5}\\})$.

Then we can bound the derivative with respect to the first coordinate:

$\displaystyle\frac{\partial}{\partial z_{1}}\mathbb{E}F_{t}(z;I)$
$\displaystyle=\sum_{y\in A_{t}\cap I}\frac{\partial}{\partial
z_{1}}g(y,z)=\sum_{y\in A_{t}\cap I}-\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)$ (3)
$\displaystyle=\sum_{y\in R_{1}\cap
A_{t}}-\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)+\sum_{y\in R_{2}\cap
A_{t}}-\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)$ (4)

The partial derivative $\frac{\partial}{\partial z_{1}}g(y,z)$ is minimized at
$z_{1}-y_{1}=\sigma$ and maximized at $z_{1}-y_{1}=-\sigma$. The lower bound
on the derivative depends on $r$ as follows:

  * •

If $2r\geq\sigma$:

$\min_{y\in
R_{2}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)>-\frac{1}{\sigma}e^{-1/2}$, and

$\min_{y\in
R_{1}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)>\frac{r}{8\sigma^{2}}\exp\left(\frac{-(2r+\min\\{r,\sigma\hat{k}^{-1/5}\\})^{2}}{2\sigma^{2}}\right)=\frac{r}{8\sigma^{2}}\exp\left(\frac{-2r^{2}-o(\sigma^{2})}{\sigma^{2}}\right)$

  * •

If $2r<\sigma$,

$\min_{y\in
R_{2}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)>-\frac{2r}{\sigma^{2}}\exp\left(-2r^{2}/\sigma^{2}\right)$,
and

$\min_{y\in
R_{1}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)>\frac{r}{8\sigma^{2}}\exp\left(\frac{-(2r+O(\min\\{r,\sigma\hat{k}^{-1/5}\\})^{2}}{2\sigma^{2}}\right)=\frac{r}{8\sigma^{2}}\exp\left(\frac{-O(1)r^{2}}{2\sigma^{2}}\right)$

Returning to Equation 9,

$\frac{\partial}{\partial z_{1}}\mathbb{E}F_{t}(z;I)\leq-|A_{t}\cap
R_{1}|\min_{y\in R_{1}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)+|A_{t}\cap
R_{2}|\max_{y\in R_{2}}\frac{y_{1}-z_{1}}{\sigma^{2}}g(y,z)$ (5)

By assumption, $|A_{t}\cap R_{2}|\leq\hat{k}/(\ln k)^{\alpha}$. Replacing
this:

  * •

If $2r\geq\sigma$:

$\frac{\partial}{\partial
z_{1}}\mathbb{E}F_{t}(z;I)\leq-\hat{k}(1-o(1))\frac{r}{8\sigma^{2}}\exp\left(\frac{-2r^{2}}{\sigma^{2}}-o(1)\right)+\frac{\hat{k}}{(\ln
k)^{\alpha}}\frac{1}{\sigma}e^{-1/2}$

By the definition of $\alpha$, $(\ln k)^{-\alpha}=e^{-\alpha\ln\ln
k}\leq\frac{1}{\ln k}e^{-2r^{2}/\sigma^{2}}$. Hence,

$\frac{\partial}{\partial
z_{1}}E[z]\leq-\frac{\hat{k}}{\sigma}\left[(1-o(1))\frac{r}{8\sigma}\exp\left(\frac{-2r^{2}}{\sigma^{2}}\right)-\frac{1}{\ln
k}\exp\left(\frac{-2r^{2}}{\sigma^{2}}\right)e^{-1/2}\right]$

$\frac{\partial}{\partial
z_{1}}\mathbb{E}F_{t}(z;I)\leq-\frac{\hat{k}r}{8\sigma^{2}}\exp\left(\frac{-2r^{2}}{\sigma^{2}}\right)(1-o(1))$

  * •

If $2r<\sigma$,

$\frac{\partial}{\partial
z_{1}}\mathbb{E}F_{t}(z;I)\leq-\frac{r}{8\sigma^{2}}e^{-O(1)r^{2}/\sigma^{2}}\hat{k}+\frac{2r}{\sigma^{2}}\frac{\hat{k}}{\ln
k}=-\Theta(1)\frac{\hat{k}r}{\sigma^{2}}$

Let $z^{\prime}=[z_{1}^{\prime},z_{2}^{\prime},\dots,z_{n}^{\prime}]$ where
$z_{1}^{\prime}\geq r/2$ and
$dist(I,z^{\prime})<\min\\{r/8,\sigma\hat{k}^{-1/5}\\}$. Consider the point
$w=z^{\prime}-[\min\\{r/8,\sigma\hat{k}^{-1/5}\\},0,0,\dots,0]$. By
definition, the derivative bounds above apply for all points on the line
between $w$ and $z^{\prime}$. This gives us a lower bound on
$E[w]-E[z^{\prime}]$. While $w\notin V$ almost surely, by Lemma 5.0.1 there
exists a point $w^{\prime}\in V$ within a radius of $O((\log n/n)^{1/d})$ of
$w$. Applying 2.0.3, $E[w^{\prime}]-E[z^{\prime}]>E[w]-E[z^{\prime}]-o(1)$.
Then, we will apply Lemma 2.0.6 to show that $\mathbb{P}(z^{\prime}\in
A_{t+1})<1/n^{3}$.

The condition of Lemma 2.0.6 holds if

$E[w]-E[z^{\prime}]\geq\sqrt{6\beta(\hat{k}-E[z])\ln k}$ (6)

  * •

If $2r\geq\sigma$:

$E[w]\geq
E[z^{\prime}]+\sigma\hat{k}^{-1/5}\cdot\frac{\hat{k}r}{8\sigma^{2}}\exp\left(\frac{-2r^{2}}{\sigma^{2}}\right)(1-o(1))$

Since $r=O(\sigma\sqrt{\ln\ln k})$,
$\exp\left(2r^{2}/\sigma^{2}\right)=\tilde{O}(1)$. Thus,
$E[w]-E[z]=\tilde{\Omega}(\hat{k}^{4/5})$. Clearly this exceeds
$\sqrt{6\beta\hat{k}\ln k}$, so by Lemma 2.0.6, $\mathbb{P}(z^{\prime}\in
A_{t+1})<1/n^{3}$.

  * •

If $20\sigma\hat{k}^{-1/5}<2r<\sigma$:

For the same reasons as above, we can obtain a similar bound:

$E[w]\geq
E[z^{\prime}]+\sigma\hat{k}^{-1/5}\cdot\hat{k}\frac{r}{6\sigma^{2}}e^{-2r^{2}/\sigma^{2}}(1-o(1))=E[z]+\hat{k}^{4/5-o(1)}\frac{r}{\sigma}$

Since $r=\Omega(\sigma\hat{k}^{-1/5})$, this exceeds $\sqrt{6\beta\hat{k}\ln
k}$, so by Lemma 2.0.6, $\mathbb{P}(z^{\prime}\in A_{t+1})<1/n^{3}$.

  * •

If $2r\leq 20\sigma\hat{k}^{-1/5}$:

$E[w]\geq
E[z^{\prime}]+\frac{r}{8}\cdot\hat{k}\frac{r}{8\sigma^{2}}e^{-2r^{2}/\sigma^{2}}(1-o(1))=E[z]+\Theta(1)\hat{k}\frac{r^{2}}{\sigma^{2}}$

In this case, we can bound $\hat{k}-E[z]$;

$\hat{k}-E[z]\leq\hat{k}(1-e^{-2r^{2}/\sigma^{2}})\leq\hat{k}\frac{2r^{2}}{\sigma^{2}}$

Therefore, the condition can be bounded: $\sqrt{6\beta(\hat{k}-E[z])\ln
k}\leq\frac{r}{\sigma}\sqrt{12\beta\hat{k}\ln k}$.

There exists a constant $C$ such that for
$10\sigma\hat{k}^{-1/5}>r>C\sigma\sqrt{\ln k/\hat{k}}$,
$E[w]-E[z]=\Theta(1)\hat{k}\frac{r^{2}}{\sigma^{2}}>\frac{r}{\sigma}\sqrt{12\beta\hat{k}\ln
k}$. By Lemma 2.0.6, $\mathbb{P}(z^{\prime}\in A_{t+1})<1/n^{3}$.

Finally, we will argue that for any $z$ with $dist(I,z)>r/20$,
$\mathbb{P}(z\in A_{t+1})<1/n^{3}$. Let $u$ be the unit vector parallel to
$z-p$:

$\displaystyle\nabla_{u}E[z]$ $\displaystyle=\sum_{y\in
A_{t}}\nabla_{u}g(y,z)=\sum_{y\in
A_{t}}\left(u\cdot\frac{y-z}{\sigma^{2}}\right)g(y,z)$
$\displaystyle\geq\frac{dist(I,z)}{\sigma^{2}}\sum_{y\in A_{t}}g(y,z)$
$\displaystyle=\frac{dist(I,z)}{\sigma^{2}}E[z]$

Let $w$ be a point along the line $z-p$, with $dist(I,w)=dist(I,z)/2$. Again,
while $w\notin V$ almost surely, by Lemma 5.0.1 there exists a point
$w^{\prime}\in V$ within a radius of $O((\log n/n)^{1/d})$ of $w$. Applying
2.0.3, $E[w^{\prime}]-E[z^{\prime}]>E[w]-E[z^{\prime}]-o(1)$. Dividing this
again into two cases:

  * •

If $r\geq 2\sigma$:

There exists a point $y$ in $I$ with $E[y]=\Omega(\hat{k}/(\ln\ln k)^{d/2})$.
This is due to the pigeonhole principle; the volume of $I$ is
$\Theta(r^{d})=O((\ln\ln k)^{d/2}/\hat{k})$. Therefore, there exists a smaller
ball of radius $\sigma$ in $I$ with $\hat{k}/(\ln\ln k)^{d/2}$ points. For $y$
in this smaller ball, $E[y]=\Omega(\hat{k}/(\ln\ln k)^{d/2})$.

If $E[z]=\tilde{\Omega}(\hat{k})$, then
$E[w]-E[z]>dist(I,z)^{2}/(2\sigma)^{2}E[z]=\tilde{\Omega}(\hat{k})$, and by
Lemma 2.0.6, $\mathbb{P}(z\in A_{t+1})<1/n^{3}$. Otherwise,
$E[y]-E[z]=\tilde{\Omega}(\hat{k})$, and again by Lemma 2.0.6,
$\mathbb{P}(z\in A_{t+1})<1/n^{3}$.

  * •

If $r<2\sigma$:

There exists a point $y$ in $R_{1}$ with $E[y]\geq
e^{-r^{2}/8\sigma^{2}}\hat{k}\geq\hat{k}(1-r^{2}/8\sigma^{2})$.

If $E[z]=\hat{k}(1-\gamma r^{2}/\sigma^{2})$, the bound for Lemma 2.0.6 is:

$\sqrt{6\beta(\hat{k}-E[z])\ln k}=\frac{r}{\sigma}\sqrt{6\beta\gamma\ln k}$

For any $r=\Omega(\sigma\sqrt{\ln k/\hat{k}})$,
$E[w]-E[z]\geq\Theta(r^{2}/\sigma^{2}\hat{k})=\Omega(\ln k)$. There exists a
constant $C$ such that for any $r>C\sigma\sqrt{\ln k/\hat{k}}$, this exceeds
the bound of Lemma 2.0.6, and $\mathbb{P}(z\in A_{t+1})<1/n^{3}$.

In conclusion, we have determined that the set of points $z\in I$ such that
$\mathbb{P}(z\in A_{t+1})>1/n^{3}$ are contained within a region
$R=\\{z:z_{1}\leq r/2,dist(I,z)<r/20\\}$. The radius of $R$ is $r/20$ plus the
width of $\\{z\in I:z_{1}\leq r/2\\}$. Using a geometric argument, this set
has width $\sqrt{R^{2}-(R/2)^{2}}=R\sqrt{3}/2$. This region can be enclosed by
a ball $I^{\prime}$ defined as follows (illustrated as an orange circle in
Figure 3):

Let $I^{\prime}=B_{19r/20}(p^{\prime})$ for $p^{\prime}=[3r/4,0,0,\dots,0]$
and $r(I^{\prime})=\frac{19}{20}r(I)$. It is simple to check that
$B_{19r/20}(p^{\prime})$ contains $R$;

$\max_{z\in R}\lVert p-z\rVert=r\sqrt{(\sqrt{3}/2+1/20)^{2}+1/4^{2}}<19r/20$

Additionally, $\max_{z\in B_{19r/20}(p^{\prime})}dist(z,I)<\max_{z\in
B_{r}(p^{\prime})}dist(z,I)<r/4$. Therefore,
$d(I,I^{\prime})<r/4<5(r(I)-r(I^{\prime}))$.

Case 2: In this section, we assume that no such imbalanced partition of $I$
exists. For all $x\in\partial I$, denoting $R_{2}=\\{z\in
I:(x-z)\cdot\frac{x-p}{\lVert x-p\rVert}>r/4\\}$, $|R_{2}\cap
A_{t}|\geq\hat{k}/(\ln k)^{\alpha}$, where
$\alpha=1+\max\\{2r^{2}/(\sigma^{2}\ln\ln k),1\\}$. We will show that for any
$z$ within $\Delta r$ of the boundary of $I$, $\mathbb{P}(z\in
A_{t+1}<1/n^{3})$.

Fix $x$, and assume without loss of generality that $p=[r,0,0,\dots,0]$ and
$x=[0,0,\dots,0]$

Let $z=[z_{1},0,0,\dots,0]$ where $-\sigma\log n<z_{1}<\Delta r=O(r/\ln k)$.
Then, $\max_{y\in
R_{1}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)=\frac{z_{1}}{\sigma^{2}}\exp\left(\frac{-z_{1}^{2}}{2\sigma^{2}}\right)<\frac{\Delta
r}{\sigma^{2}}\exp\left(\frac{-(\Delta r)^{2}}{2\sigma^{2}}\right)$ (Note that
by construction $\Delta r<\sigma$). Also, separately taking the minima of
$y_{1}-z_{1}$ and $g(y,z)$, $\min_{y\in
R_{2}}\frac{y_{1}-z_{1}}{\sigma^{2}}g(y,z)>\frac{r/4-z_{1}}{\sigma^{2}}\exp\left(\frac{-2r^{2}}{\sigma^{2}}\right)$.
Returning to Equation 9:

$\frac{\partial}{\partial z_{1}}E[z]\geq-|A_{t}\cap R_{1}|\frac{\Delta
r}{\sigma^{2}}\exp\left(\frac{-(\Delta r)^{2}}{2\sigma^{2}}\right)+|A_{t}\cap
R_{2}|\frac{r/4-z_{1}}{\sigma^{2}}\exp\left(\frac{-2r^{2}}{\sigma^{2}}\right)$
(7)

By assumption, $|A_{t}\cap R_{2}|\geq\hat{k}/(\ln k)^{\alpha}$. Replacing
this:

$\frac{\partial}{\partial z_{1}}E[z]\geq-\hat{k}\left[1-\frac{1}{(\ln
k)^{\alpha}}\right]\frac{\Delta r}{\sigma^{2}}\exp\left(\frac{-(\Delta
r)^{2}}{2\sigma^{2}}\right)+\frac{\hat{k}}{(\ln k)^{\alpha}}\frac{r/4-\Delta
r}{\sigma^{2}}\exp\left(\frac{-2r^{2}}{\sigma^{2}}\right)$

Define $\Delta r=r/(\ln k)^{2\alpha}$. Again, note that $(\ln
k)^{-\alpha}=e^{-\alpha\ln\ln k}\leq\frac{1}{\ln k}e^{-2r^{2}/\sigma^{2}}$.
So, $e^{-2r^{2}/\sigma^{2}}\geq(\ln k)^{1-\alpha}$

$\frac{\partial}{\partial z_{1}}E[z]\geq-\hat{k}\left[1-\frac{1}{(\ln
k)^{\alpha}}\right]\frac{r}{\sigma^{2}(\ln
k)^{2\alpha}}\exp\left(\frac{-(\Delta
r)^{2}}{2\sigma^{2}}\right)+\frac{\hat{k}}{(\ln
k)^{2\alpha-1}}\frac{r}{5\sigma^{2}}$ $\frac{\partial}{\partial
z_{1}}E[z]\geq\frac{\hat{k}r}{\sigma^{2}(\ln k)^{2\alpha}}\left[1-o(1)+\ln
k\right]$

Suppose $z=[z_{1},0,0,\dots,0]$ where $z_{1}<\Delta r/2$. Let $w=z_{1}+[\Delta
r/2,0,0,\dots,0]$. Using the lower bound on the derivative,

$E[w]\geq E[z]+\frac{\Delta r}{2}\cdot\frac{\hat{k}r}{\sigma^{2}(\ln
k)^{2\alpha}}\left[1-o(1)+\ln k\right]\geq
E[z]+\frac{1}{2}\frac{\hat{k}r^{2}}{\sigma^{2}}\ln k$

For $r=\Omega(\sigma\hat{k}^{-1/4})$, this exceeds $\sqrt{6\beta\hat{k}\ln
k}$, so by Lemma 2.0.6, $\mathbb{P}(z\in A_{t+1})<1/n^{3}$.

For $r=o(\sigma\hat{k}^{-1/4})$, we can bound $\hat{k}-E[z]$;

$\hat{k}-E[z]\leq\hat{k}(1-e^{-2r^{2}/\sigma^{2}})\leq\hat{k}\frac{2r^{2}}{\sigma^{2}}$

Therefore, the condition can be bounded: $\sqrt{6\beta(\hat{k}-E[z])\ln
k}\leq\frac{r}{\sigma}\sqrt{12\beta\hat{k}\ln k}$.

Then, for $\sigma\hat{k}^{-1/4}\ln k>r>\sigma\sqrt{\ln k/\hat{k}}$,
$E[w]-E[z]=\frac{1}{2}\frac{\hat{k}r^{2}}{\sigma^{2}}\ln
k>\frac{r}{\sigma}\sqrt{12\beta\hat{k}\ln k}$. By Lemma 2.0.6,
$\mathbb{P}(z^{\prime}\in A_{t+1})<1/n^{3}$.

In summary, there are two cases: in case 1, there exists a partition of $I$
such that the vast majority of $A_{t}$ is located in $R_{1}$. In this case, we
have shown that $\\{z:\mathbb{P}(z\in A_{t+1})>1/n^{3}\\}\subset\\{z:z_{1}\leq
r/2\\}$. A symmetric argument showed that for any $z$ such that the distance
from $z$ to $I$ is at most $r/20$, $\mathbb{P}(z\in A_{t+1})<1/n^{3}$
Therefore, $A_{t+1}$ is contained within a ball
$I^{\prime}=B_{19r/20}(p^{\prime})$, where $d(I,I^{\prime})<r/4$

In case 2, for all $x\in\partial I$, $|A_{t}\cap R_{2}|$ is sufficiently
large. In this case, We have shown that for all $z=x+\lambda\frac{p-x}{\lVert
p-x\rVert}$ where $\lambda<r/\text{polylog}(k)$, $\mathbb{P}(z\in
A_{t+1})<1/n^{3}$. This applies for all $x\in\delta I$. Therefore,
$I^{\prime}\subset B_{r(1-1/(\ln k)^{c})}(p)$.

By the assumption that each ball is sufficiently separated, we can conclude
that, with high probability, $A_{t+1}\subset I_{1}^{\prime}\cup
I_{2}^{\prime}\cup\dots\cup I_{i}^{\prime}$, where the radius of
$I_{j}^{\prime}$ is smaller than the radius of $I_{j}$ by at least a factor of
$1/\text{polylog}(k)$.

∎

Now, we are ready to prove Theorem 1.2.

###### Proof of Theorem 1.2.

By Theorem 1.3, the conditions of Lemma 1.4 hold at step 1. Additionally, by
the condition that each ball does not shift by more than
$5(r(I)-r(I^{\prime}))$ at each step, the separation condition holds
inductively for any $t=\text{polylog}(k)$. The maximum distance moved by a
single ball by time $t$ is
$5(r(I^{(0)}_{j})-r(I^{(t)}_{j}))=O(\sigma\sqrt{\ln\ln k})$, which maintains
the separation of $2(1-o(1))\sigma\sqrt{\ln n})$. Thus, we can apply the Lemma
inductively.

By Lemma 1.4, the radius of $I$ is reduced by a factor of
$1-\frac{1}{\text{polylog}(k)}$ in a single step; thus, to reach
$O(\sigma\hat{k}^{-1/2}\sqrt{\ln k})$, the number of steps required is
$\text{polylog}(k)$.

This shows that in $\text{polylog}(k)$ time, the radius of each sufficiently
separated ball will be reduced to at most $\hat{k}^{-1/2}\sqrt{\ln k}$. Recall
that there are $k^{1/4+o(1)}$ separated balls; a similar method will allow us
to eliminate balls that are $\sigma\hat{k}^{-1/2}\sqrt{\ln k}$ in size.

If the number of balls is greater than 1, $|I_{1}\cap A_{t}|$ can fall
anywhere in the range $M\pm\sqrt{M}$ with constant probability, where
$M=\mathbb{E}|I_{1}\cap A_{t}|$. By the pigeonhole principle, at least one
ball receives $k^{3/4-o(1)}$ points. Since the size of the balls are at most
$\sigma\hat{k}^{-1/2}\sqrt{\ln k}<\sigma\hat{k}^{-3/8}\sqrt{\ln k}$,
$C_{t}\geq\left(k^{3/4-o(1)}\right)$. Therefore, for each $j$, if $I_{j}$ is
not eliminated, there exists an $x\in I_{j}$ such that $\mathbb{E}F_{t}(x)\geq
k^{3/4-o(1)}$. Consider two alternative scenarios, which can each occur with
constant probability.

$\begin{cases}(1)&\max_{x\in I_{1}}\mathbb{E}F_{t}(x)=X-\Theta(\sqrt{X})\\\
(2)&\max_{x\in I_{1}}\mathbb{E}F_{t}(x)=X+\Theta(\sqrt{X})\end{cases}$

Let $y=\operatorname*{argmax}_{y\in I_{2}}\mathbb{E}F_{t}(y)$. So, it is clear
that in either scenario (1) or (2), the inputs to $x$ and $y$ differ by the
number of points added to $I_{1}$.

$\left|\max_{x\in I_{1}}\mathbb{E}F_{t}(x)-\max_{y\in
I_{2}}\mathbb{E}F_{t}(y)\right|=k^{3/8-o(1)}$

In scenario 2, $x$ receives an extra input of $\Theta\left(\sqrt{X}\right)$.
The increased input in this scenario could affect $C_{t}$; however, either
$\mathbb{E}F_{t}(x)$ becomes closer to $C_{t}$ by $k^{3/8-o(1)}$, or
$\mathbb{E}F_{t}(y)$ becomes further from $C_{t}$ by the same amount.

By Lemma 5.0.6, between the two scenarios, either $p_{t+1}(z)$ increases by a
constant factor for all $z\in I_{1}$, or $p_{t+1}(w)$ decreases by a constant
factor for all $w\in I_{2}$. Again, $I_{1}$ and $I_{2}$ either have at least
$k^{3/4-o(1)}$ points, or they are eliminated. So, this implies that
$|\mathbb{E}F_{t+1}(x)-\mathbb{E}F_{t+1}(y)|$ varies by $O(1)k^{3/4-o(1)}$
between the two scenarios.

This is a significant variation; as in Lemma 2.0.5, for any $x\in[n]$,
$C_{t}\geq\mathbb{E}F_{t+1}(x)$. So, in the case where
$\mathbb{E}F_{t+1}(y)<\mathbb{E}F_{t+1}(x)$:

$\mathbb{E}F_{t+1}(y)<\mathbb{E}F_{t+1}(x)-\Omega\left(k^{3/4-o(1)}\right)$

By the Chernoff bound, the probability that $F_{t+1}(y)$ will exceed $C_{t+1}$
is exponentially small. A similar argument applies if
$\mathbb{E}F_{t+1}(y)>\mathbb{E}F_{t+1}(x)$. Therefore, since there is a
constant probability that the two balls will deviate from each other, either
$I_{1}$ or $I_{2}$ will be eliminated in a constant number of steps.

The same argument applies to any pair of balls $(I_{i},I_{j})$. Therefore, the
number of balls reduces by a constant factor within a constant number of
steps. This leads to convergence to a single ball within $O(\ln k)$ steps.

At this point, $\hat{k}=k$, so applying Lemma 1.4 again, we can conclude that
$A_{t}$ converges to a single ball of size $O(\sigma k^{-1/2}\sqrt{\ln k})$ in
$O((\log k)^{c})$ steps. ∎

Finally, we prove that the set $A_{t}$, with high probability, remains within
a small subset for all $t\geq t^{*}$.

###### Proof of Theorem 1.5.

Let $A\subset V$ with $|A|=k$, and let $I$ be a ball surrounding $k-k^{2/3}$
points of $A$. Assume that $r=r(I)=\sigma k^{-1/3+\epsilon}$ and $I=B_{r}(p)$.

We consider 2 cases, identically to the proof of Lemma 1.4:

Case 1: There exists a half space dividing $I$ into two spherical caps,
$R_{1}$ and $R_{2}$, with heights $r/4$ and $7r/4$, such that $|R_{2}\cap
A_{t}|\leq k/(\ln k)^{2}$. In this case, the ball is “imbalanced” in the sense
that one portion of of the ball contains the vast majority of the points.

Without loss of generality, let $p=[r,0,0,\dots,0]$, $R_{1}=\\{y\in
I:y_{1}\leq r/4\\}$, and $R_{2}=\\{y\in I:y_{1}>r/4\\}$ (as illustrated in
Figure 3). We define $E[z]=F(z;A)=\sum_{y\in A}g(y,z)$.

Then we can bound the derivative with respect to the first coordinate:

$\displaystyle\frac{\partial}{\partial z_{1}}E[z]$ $\displaystyle=\sum_{y\in
A\cap I}\frac{\partial}{\partial z_{1}}g(y,z)=\sum_{y\in A\cap
I}-\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)+\sum_{y\in A\setminus
I}-\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)$ (8) $\displaystyle=\sum_{y\in
R_{1}\cap A}-\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)+\sum_{y\in R_{2}\cap
A}-\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)+\sum_{y\in A\setminus
I}-\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)$ (9)

Let $z=[z_{1},z_{2},\dots,z_{n}]$ where $z_{1}\geq 3r/8$ and $dist(I,z)=O(r)$.
This implies:

$\min_{y\in
R_{2}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)>-\frac{2r}{\sigma^{2}}\exp\left(-2r^{2}/\sigma^{2}\right)$

$\min_{y\in
R_{1}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)>\frac{r}{8\sigma^{2}}\exp\left(\frac{-O(1)r^{2}}{2\sigma^{2}}\right)$,
and

$\min_{y\in[0,1]^{d}\setminus
I}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)>-\frac{1}{\sigma}e^{-1/2}$
Returning to Equation 9:

$\frac{\partial}{\partial z_{1}}E[z]\leq-|A_{t}\cap R_{1}|\min_{y\in
R_{1}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)-|A_{t}\cap R_{2}|\min_{y\in
R_{2}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)-|A_{t}\setminus
I|\min_{y\in[0,1]^{d}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)$ (10)

By assumption, $|A_{t}\cap R_{2}|\leq k/(\ln k)^{2}$ and $|A_{t}\setminus
I|=k^{2/3}$. Replacing this:

$\frac{\partial}{\partial
z_{1}}E[z]\leq-\frac{r}{8\sigma^{2}}e^{-O(1)r^{2}/\sigma^{2}}k+\frac{2r}{\sigma^{2}}\frac{k}{\ln
k^{2}}+\frac{\Theta(1)k^{2/3}}{\sigma}=-\Theta(1)\frac{kr}{\sigma^{2}}$

Let $z^{\prime}=[z_{1}^{\prime},z_{2}^{\prime},\dots,z_{n}^{\prime}]$ where
$z_{1}^{\prime}\geq r/2$ and $dist(I,z^{\prime})<r/8$. Consider the point
$w=z^{\prime}-r/8$. By definition, the derivative bounds above apply for all
points on the line between $w$ and $z^{\prime}$. This gives us a lower bound
on $E[w]-E[z^{\prime}]$. While $w\notin V$ almost surely, by Lemma 5.0.1 there
exists a point $w^{\prime}\in V$ within a radius of $O((\log n/n)^{1/d})$ of
$w$. Applying 2.0.3, $E[w^{\prime}]-E[z^{\prime}]>E[w]-E[z^{\prime}]-o(1)$.

We will prove an analogous result to Lemma 2.0.5 for sets $A$ contained mostly
within a ball of radius $r$.

######  Lemma 2.0.7.

Let $I$ be a ball of radius $r=\sigma k^{-1/3+\epsilon}$, for some constant
$\epsilon>0$, surrounding $k-k^{2/3}$ points of $A$. Let $C$ be the threshold
when the $k$-cap function is applied to $A$. With high probability, for all
such sets $A\subset V$ with $|A|=k$, $C\geq\max_{x}E[x]$.

###### Proof of Lemma 2.0.5.

The derivative of $E[x]$ is, for any dimension $i$:

$\frac{\partial}{\partial x_{i}}E[x]=\sum_{z\in A_{t}}\frac{\partial}{\partial
x_{i}}g(x,z)=\sum_{z\in
A_{t}}-\frac{x_{i}-z_{i}}{\sigma^{2}}\exp\left(\frac{-\lVert
x-z\rVert^{2}}{2\sigma^{2}}\right)$

Let $\hat{x}=\frac{x-z}{\sigma}$. The maximum of
$\left|\hat{x}\exp\left(\frac{-\hat{x}^{2}}{2}\right)\right|$ occurs at
$e^{-1/2}$. For $y\in I$, this is maximized at $\hat{x}=\frac{2r}{\sigma}$.
Thus, we have

$\left|\frac{\partial}{\partial x_{i}}E[x]\right|\leq\sum_{z\in
A_{t}}\frac{|x_{i}-z_{i}|}{\sigma^{2}}\exp\left(\frac{-\lVert
x-z\rVert^{2}}{2\sigma^{2}}\right)<\frac{e^{-1/2}k^{2/3}}{\sigma}+k\frac{2r}{\sigma^{2}}=\frac{2k^{2/3+\epsilon}}{\sigma}(1+o(1))$

Therefore, the directional derivative, as in Lemma 2.0.3, is at most this
value, times a factor of $\sqrt{d}$. For any $y\in B_{\sigma
k^{-1+\epsilon}}(x)$, the difference between $E[y]$ and $E[x]$ can be bounded:

$E[y]=E[x]-o(1)$

By Lemma 5.0.1, for any point $x$, there are $\Omega((n/\log
n)\cdot\sigma^{d}k^{-d+d\epsilon})$ points in a radius of $\sigma
k^{-1+\epsilon}$ of $x$. By the assumption that $n\geq k^{2+d}$, this is
$\tilde{\Omega}(k^{1+d\epsilon})$.

Therefore, if $C=E[x]$, then there are $\tilde{\Omega}(k^{1+d\epsilon})$
points where $E[y]>C_{t}-O(1)$. Since each edge is chosen independently,
Chernoff type bounds apply; if
$\mathbb{P}\left(F_{t}(y)>E[y]+O(1)\right)=\Theta(1)$, then with high
probability there are $k$ points that exceed $C_{t}$.

Using the loose bound given in [Vol96], we can bound
$\mathbb{P}(F_{t}(x)>C_{t})$ using the CDF of the normal distribution. For any
sum of independent indicators $S$ with mean $\mu$ and variance $\sigma$, the
CDF can be approximated as follows:

$\sup_{m}\left|\mathbb{P}(S\leq
m)-G\left(\frac{m+1/2-\mu}{\sigma}\right)\right|\leq\frac{\sigma+3}{4\sigma^{3}}<\frac{1}{\sigma^{2}}$

Where
$G(x)=\Phi(x)-\frac{\gamma}{6\sigma^{3}}(x^{2}-1)\frac{e^{-x^{2}/2}}{\sqrt{2\pi}}$,
and $\gamma=\mathbb{E}[(S-\mu)^{3}]$ is the skewness. This holds for any
$\sigma\geq 10$.

We can assume that $V[y]>10$; otherwise, $E[y]=\sum_{y\in A_{t}}=k(1-o(1/k))$,
so we can assume that $C=k$.

Fix $x\in[n]$. From the above equation, we find that for any $t>0$:

$\mathbb{P}\left(F_{t}(x)>E[x]+tV[x]-1/2\right)>1-\left[G(t)+\frac{1}{V[x]^{2}}\right]$

Substituting the value of $G$:

$\mathbb{P}\left(F_{t}(x)>E[x]+tV[x]-1/2\right)>1-\Phi(t)+\frac{\gamma(t^{2}-1)}{6\sqrt{2\pi}V[x]^{3}}e^{-t^{2}/2}-\frac{1}{V[x]^{2}}$

Here, we will make two approximations. First, the exact value of $\gamma$ is
$\sum_{z\in A_{t}}g(x,z)(1-g(x,z))(1-2g(x,z))$. Therefore, $\gamma>-V[x]^{2}$,
so $\gamma(t^{2}-1)>-V[x]^{2}t^{2}$

Second, we will substitute the lower tail bound for
$1-\Phi(t)\geq\frac{1}{\sqrt{2\pi}}\left(t^{-1}-t^{-3}\right)e^{-t^{2}/2}\geq\frac{1}{t\sqrt{8\pi}}e^{-t^{2}/2}$
for $t\geq 2$.

This leaves us with:

$\mathbb{P}\left(F_{t}(x)>E[x]+tV[x]-1/2\right)>\frac{1}{t\sqrt{8\pi}}e^{-t^{2}/2}-\frac{t^{2}}{6\sqrt{2\pi}V[x]}e^{-t^{2}/2}-\frac{1}{V[x]^{2}}$

Setting $t=\Theta(1)/V[x]$, this occurs with constant positive probability
$p$.

The probability that there are not $k$ points which exceed $C=E[x]$ is at
least ${k^{1+d\epsilon}\choose
k}(1-p)^{k^{1+d/2}-k}=(1-p)^{k^{1+d\epsilon}(1-o(1))}$.

The number of possible subsets $A$ is at most ${n\choose k}<n^{k}=e^{k\log
n}$.

By the union bound, this holds for all subsets $A$ with high probability. ∎

Returning to the proof of the original theorem, we recall that there exists a
point $w$ such that:

$E[w]\geq E[z^{\prime}]+\frac{r}{8}\cdot
k\frac{r}{8\sigma^{2}}e^{-2r^{2}/\sigma^{2}}(1-o(1))=E[z]+\Theta(1)k\frac{r^{2}}{\sigma^{2}}=E[z^{\prime}]+\Theta(k^{1/3+2\epsilon})$

Comparing this to $k-E[z^{\prime}]$

$k-E[z^{\prime}]\leq k(1-e^{-2r^{2}/\sigma^{2}})\leq
k\frac{2r^{2}}{\sigma^{2}}=2k^{1/3+2\epsilon}$

We can apply Lemma 5.0.4 to $k-E[z^{\prime}]$; let $Z=k-F(z^{\prime};A)$.
Then, $\mathbb{P}(Z<(1-\delta)\mathbb{E}Z])\leq e^{-\delta^{2}\mathbb{E}Z/2}$.
So,

$\mathbb{P}(Z<\mathbb{E}Z-\Theta(1)\mathbb{E}Z)<e^{-\Theta(1)k^{1/3+2\epsilon}}$

The probability that there exist $k^{2/3}$ points which violate the condition
is at most:

${n\choose k^{2/3}}(e^{-\Theta(1)k^{1/3+2\epsilon}})^{k^{2/3}}<e^{k^{2/3}\log
n}e^{-\Theta(1)k^{1+2\epsilon}\log n}$

Since there are at most ${n\choose k}=O(e^{k\log n})$ possible $k$-subsets of
$V$, this is true by the union bound for all subsets $A$ with high
probability.

Case 2: In this section, we assume that no such imbalanced partition of $I$
exists. For all $x\in\partial I$, denoting $R_{2}=\\{z\in
I:x-z\cdot(\frac{x-p}{\lVert x-p\rVert}>r/4)$, $|R_{2}\cap A|\geq k/(\ln
k)^{2}$. We will show that for any $z$ within $\Delta r$ of the boundary of
$I$, $\mathbb{P}(F(z;A)>C)<1/n^{3}$.

Fix $x$, and assume without loss of generality that $p=[r,0,0,\dots,0]$ and
$x=[0,0,\dots,0]$

Let $z=[z_{1},0,0,\dots,0]$ where $-\sigma\log n<z_{1}<\Delta r=O(r/\ln k)$.
Then, $\max_{y\in
R_{1}}\frac{z_{1}-y_{1}}{\sigma^{2}}g(y,z)=\frac{z_{1}}{\sigma^{2}}\exp\left(\frac{-z_{1}^{2}}{2\sigma^{2}}\right)<\frac{\Delta
r}{\sigma^{2}}\exp\left(\frac{-(\Delta
r)^{2}}{2\sigma^{2}}\right)=\frac{\Delta r}{\sigma^{2}}(1-o(1))$ Also,
separately taking the minima of $y_{1}-z_{1}$ and $g(y,z)$, $\min_{y\in
R_{2}}\frac{y_{1}-z_{1}}{\sigma^{2}}g(y,z)=\frac{r}{4\sigma^{2}}(1-o(1))$.
Bounding the derivative again:

$\frac{\partial}{\partial z_{1}}E[z]\geq-|A\cap R_{1}|\frac{\Delta
r}{\sigma^{2}}(1-o(1))+|A\cap R_{2}|\frac{r}{4\sigma^{2}}(1-o(1))-|A\setminus
I|\frac{O(1)}{\sigma}$ (11)

By the assumption of the case, $|A\cap R_{2}|\geq k/(\ln k)^{2}$. Also, by the
assumption of the theorem $|A\setminus I|=O(k^{2/3})$. Replacing this:

$\frac{\partial}{\partial z_{1}}E[z]\geq-k\frac{\Delta
r}{\sigma^{2}}(1-o(1))+\frac{kr}{4\sigma^{2}(\ln
k)^{2}}(1-o(1))-\frac{O(k^{2/3})}{\sigma}$

Define $\Delta r=r/(\ln k)^{3}$.

$\frac{\partial}{\partial z_{1}}E[z]\geq-k(1-o(1))\frac{r}{\sigma^{2}(\ln
k)^{3}}+\frac{\Theta(k)r}{\sigma^{2}(\ln
k)^{2}}-\frac{O(k^{2/3})}{\sigma}=\frac{kr}{\sigma^{2}(\ln
k)^{3}}\left[1-o(1)+\Theta(\ln k)\right]$

Suppose $z=[z_{1},0,0,\dots,0]$ where $z_{1}<\Delta r/2$. Let $w=z_{1}+[\Delta
r/2,0,0,\dots,0]$. Using the lower bound on the derivative,

$E[w]\geq E[z]+\frac{\Delta r}{2}\cdot\frac{kr}{\sigma^{2}(\ln
k)^{3}}\left[1-o(1)+\ln k\right]\geq
E[z]+\frac{1}{4}\frac{kr^{2}}{\sigma^{2}}\ln k$

Using the same bound as above for $k-E[z]$:

$\hat{k}-E[z]\leq\hat{k}(1-e^{-2r^{2}/\sigma^{2}})\leq
k\frac{2r^{2}}{\sigma^{2}}$

We can apply Lemma 5.0.4 to $k-E[z^{\prime}]$; let $Z=k-F(z^{\prime};A)$.
Then, $\mathbb{P}(Z<(1-\delta)\mathbb{E}Z])\leq e^{-\delta^{2}\mathbb{E}Z/2}$.
So,

$\mathbb{P}(Z<\mathbb{E}Z-\Theta(1)\mathbb{E}Z)<e^{-\Theta(1)k^{1/3+2\epsilon}}$

The probability that there exist $k^{2/3}$ points which violate the condition
is at most:

${n\choose k^{2/3}}(e^{-\Theta(1)k^{1/3+2\epsilon}})^{k^{2/3}}<e^{k^{2/3}\log
n}e^{-\Theta(1)k^{1+2\epsilon}}$

Since there are at most ${n\choose k}=O(e^{k\log n})$ possible $k$-subsets of
$V$, this is true by the union bound for all subsets $A$ with high
probability.

∎

##  3 Continuous $\alpha$-cap process

This section considers a continuous analog of the $k$-cap process. To
understand the connection, one can imagine a graph with infinite nodes whose
hidden variables span a subspace of $\mathbb{R}$. Rather than choosing a fixed
$k$ vertices to fire, a constant fraction $\alpha$ of this subspace is
activated.

For clarity, the definition for the $\alpha$-cap process in one dimension is
restate below. We assume that the hidden variables are drawn from $[0,1]$;
however, the analysis will be similar for any finite interval.

######  Definition 3.1 ($\alpha$-cap Process in 1-D).

Let $A_{0}$ be a finite union of intervals on [0,1]. Let $\alpha=|A_{0}|$ and
for an integrable function $g:[0,1]\rightarrow\mathbb{R}$, let

$F_{t}(x)=\int_{0}^{1}A_{t}(y)g(y-x)\,dy$ (12)

Then, define the next step

$A_{t+1}(x)=\begin{cases}0&F_{t}(x)<C_{t}\\\ 1&F_{t}(x)\geq C_{t}\\\
\end{cases}$

where $C_{t}\in[0,1]$ is the solution to $\int_{0}^{1}A_{t+1}(x)dx=\alpha$.

The goal of this section will be to show that this process converges to a
single interval, and that the convergence time depends on properties of $g$
and $g^{\prime}$.

Two motivating examples of the function $g$ are (proportional to) the Gaussian
density with variance $\sigma^{2}$, $g(x)=\exp(\frac{-x^{2}}{2\sigma^{2}})$
and the inverse square distance $g(x)=1/(1+x^{2})$.

First, we will prove that single intervals of width $\alpha$ are the only
possible fixed points.

######  Theorem 3.1 (Fixed Points).

For any even, nonnegative, integrable function $g:[0,1]\rightarrow\Re_{+}$
with $g^{\prime}(x)<0$ for all $x>0$, the only fixed points ($A_{t+1}=A_{t}$)
of the $\alpha$-cap Process are single intervals of width $\alpha$.

The next lemma follows from the properties of $g$.

######  Lemma 3.1.1.

The following holds for all $b>a$:

$\int_{a}^{b}g(y-a)\,dy=\int_{a}^{b}g(y-b)\,dy\\\ $

We proceed to the proof of the fixed point characterization.

###### Proof of Theorem 3.1.

First, we show that if $A_{t}=[a,b]$ is a single interval, then it is a fixed
point. Since $A_{t}$ is 1 on the interval and 0 elsewhere, we can rewrite
$F_{t}(x)$:

$F_{t}(x)=\int_{a}^{b}g(y-x)\,dy$ (13)

Let $C_{t}=F_{t}(a)=F_{t}(b)=\int_{a}^{b}g(y-a)\,dy$. If $x\in[a,b]$,

$F_{t}(x)=\int_{a}^{b}g(y-x)\,dy\geq\int_{a}^{b}g(y-a)\,dy=C_{t}$

It’s easiest to see this by breaking it into two integrals. The first is

$\int_{a}^{x}g(y-x)\,dy=\int_{a}^{x}g(y-a)\,dy\\\ $

which holds by Lemma 3.1.1, and the second is

$\int_{x}^{b}g(y-x)\,dy\geq\int_{x}^{b}g(y-a)\,dy$

which holds because $a<x$, which means $g(y-x)>g(y-a)$ for all $y\in[x,b]$.
Therefore, $F_{t}(x)\geq F_{t}(a)=C_{t}$ for all $x\in[a,b]$.
Similarly, if $x<a$ or $x>b$,

$F_{t}(x)=\int_{a}^{b}g(y-x)\,dy<\int_{a}^{b}g(y-a)\,dy=C_{t}$

This implies that if $C_{t}$ is chosen in this way, then
$A_{t+1}=[a,b]=A_{t}$.

Next, let $A_{t}$ be the union of finite intervals. Let
$A_{t}=\bigcup_{j=1}^{n}[a_{j},b_{j}]$ where for all $j<n$,
$a_{j}<b_{j}<a_{j+1}<b_{j+1}$, and $n>1$. We will show that this is not fixed.

$F_{t}(x)$ can be expressed as the following:

$F_{t}(x)=\sum_{j=1}^{n}\int_{a_{j}}^{b_{j}}g(y-x)\,dy$

Consider $F_{t}(a_{n})$ and $F_{t}(b_{n})$.

$F_{t}(a_{n})=\int_{a_{n}}^{b_{n}}g(y-a_{n})\,dy+\sum_{j=1}^{n-1}\int_{a_{j}}^{b_{j}}g(y-a_{n})\,dy$
$F_{t}(b_{n})=\int_{a_{n}}^{b_{n}}g(y-b_{n})\,dy+\sum_{j=1}^{n-1}\int_{a_{j}}^{b_{j}}g(y-b_{n})\,dy$

By Lemma 3.1.1,
$\int_{a_{n}}^{b_{n}}g(y-a_{n})\,dy=\int_{a_{n}}^{b_{n}}g(y-b_{n})\,dy$. Also,
since $a_{n}<b_{n}$,
$\int_{a_{j}}^{b_{j}}g(y-a_{n})\,dy>\int_{a_{j}}^{b_{j}}g(y-b_{n})\,dy$ for
all $j<n$. Therefore, $F_{t}(a_{n})>F_{t}(b_{n})$.
Given this, there is no value of $C_{t}$ where $F_{t}(x)$ is greater for all
$x\in[a_{j},b_{j}]$ and less for all $x\notin A_{t}$. Notice that by
definition, if $A_{t+1}=A_{t}$, $C_{t}\leq F_{t}(x)$ for all $x\in A_{t+1}$.
In particular, $C_{t}\leq F_{t}(b_{n})<F_{t}(a_{n})$. However, since
$F_{t}(x)$ is a continuous function, $C_{t}<F_{t}(x)$ in some small window
$[a_{n}-\epsilon,a_{n}]$. By definition, $a_{n}-\epsilon\in A_{t+1}$, but
$a_{n}-\epsilon\notin A_{t}$ for small enough $\epsilon$. This implies
$A_{t}\neq A_{t+1}$. ∎

Now, we will prove the main convergence theorem, which we originally
introduced in Section 3. See 1.1

###### Proof of Theorem 1.1.

At a given step $t\geq 0$, $A_{t}$ is a union of finite intervals on [0,1]. We
will show that if the number of intervals is greater than 1, the distance
between the midpoints of the first and last intervals decreases at each step,
and this decrease is not diminishing.
Let $A_{t}=\bigcup_{j=1}^{n}[a_{j},b_{j}]$ where the intervals are disjoint
and increasing; for all $j<n$, $0\leq a_{j}<b_{j}<a_{j+1}<b_{j+1}\leq 1$.
Define the midpoint of the kth interval $m_{k}=\frac{a_{k}+b_{k}}{2}$.
By 3.1, if $n=1$, then the process has converged (i.e. $A_{t+1}=A_{t}$). If
$n>1$, $[a_{1},b_{1}]$ and $[a_{n},b_{n}]$ are the first and last intervals in
$A_{t}$, respectively. We will show that the distance between the midpoints,
$m_{n}-m_{1}$, decreases by at least a constant.

Suppose the first local maximum of $F_{t}$ occurs at a value $m_{1}+\delta$.
This proof will show that the shift in the midpoint $m_{1}$ is bounded from
below by a constant depending on $\delta$. Then, it will show that if
$[a_{1},b_{1}]$ is not large ($b_{1}-a_{1}<\frac{\alpha}{2}$), $\delta$ is
also bounded from below. If $[a_{1},b_{1}]$ is large, a symmetric argument
shows that $m_{n}$ must shift.

Recall the definition of $F_{t}$ and write its derivative:

$\displaystyle F_{t}(x)$
$\displaystyle=\sum_{k=1}^{n}\int_{a_{k}}^{b_{k}}g(y-x)\,dy$
$\displaystyle\frac{dF_{t}}{dx}$
$\displaystyle=\sum_{k=1}^{n}g(a_{k}-x)-g(b_{k}-x)$

Since $g(x)$ decreases with $|x|$, if $x<m_{k}$, $g(a_{k}-x)>g(b_{k}-x)$. This
implies $F_{t}$ is increasing on [0,$m_{1}$), so the first local maximum must
occur at $m_{1}+\delta>m_{1}$.
Let $z$ be the minimum value where $F_{t}(x)\geq C_{t}$. If $z\geq m_{1}$, it
is simple to show that the shift in $m_{1}$ depends on $\delta$.

  * •

If $z\geq m_{1}+\delta$, then $A_{t+1}\cap[0,m_{1}+\delta]=\emptyset$.
Therefore, the midpoint of the first interval is greater than $m_{1}+\delta$.

  * •

If $m_{1}\leq z<m_{1}+\delta$, then $[z,m_{1}+\delta]\subset A_{t+1}$. The
midpoint of the first interval is greater than $\frac{z+m_{1}+\delta}{2}\geq
m_{1}+\frac{\delta}{2}$.

  * •

If $z<m_{1}$, the proof is more involved. Let $z=m_{1}-\epsilon$ for an
$\epsilon>0$.

Note that it is possible that $z=m_{1}-\epsilon<a_{1}$, such that the left end
of the interval decreases. However, the midpoint of the interval will always
increase. The influence of $F_{t}$ from the first interval is the same for
$m_{1}-\epsilon$ and $m_{1}+\epsilon$.

$\displaystyle\int_{a_{1}}^{b_{1}}g(y-(m_{1}-\epsilon))\,dy$
$\displaystyle=\int_{-m_{1}+\epsilon}^{m_{1}+\epsilon}g(z)\,dz$
$\displaystyle=-\int_{m_{1}-\epsilon}^{-m_{1}-\epsilon}g(-z)\,dz$
$\displaystyle=\int_{-m_{1}-\epsilon}^{m_{1}-\epsilon}g(z)\,dz=\int_{a_{1}}^{b_{1}}g(y-(m_{1}+\epsilon))\,dy$

For any $[a_{k},b_{k}]$ where $m_{1}<a_{k}<b_{k}$,

$\displaystyle\int_{a_{k}}^{b_{k}}g(y-(m_{1}+\epsilon))\,dy$
$\displaystyle=\int_{a_{k}-m_{1}-\epsilon}^{b_{k}-m_{1}-\epsilon}g(z)\,dz$
$\displaystyle>\int_{a_{k}-m_{1}+\epsilon}^{b_{k}-m_{1}+\epsilon}g(z)\,dz$
$\displaystyle=\int_{a_{k}}^{b_{k}}g(y-(m_{1}-\epsilon))\,dy$

This implies that $F_{t}(m_{1}+\epsilon)>F_{t}(m_{1}-\epsilon)$ for any
$\epsilon>0$. Since $F_{t}$ is continuous, there is a small value
$\epsilon^{\prime}>0$ such that
$F_{t}(m_{1}+\epsilon+\epsilon^{\prime})=C_{t}$, and $F_{t}(x)>C_{t}$ in
between. At $A_{t+1}$, the first interval becomes
$[m_{1}-\epsilon,m_{1}+\epsilon+\epsilon^{\prime}]$, which has the midpoint
$m_{1}+\frac{\epsilon^{\prime}}{2}$. Therefore, the midpoint of the first
interval increases.

Figure 4: An illustration of the terms defined in this proof. The grey box
represents the first interval, $[a_{1},b_{1}]$. The curve is $F_{t}$.

Next, we will show that the $\epsilon^{\prime}$ is bounded below by a constant
factor of $\delta$. Either $[a_{1},b_{1}]$ or $[a_{n},b_{n}]$ must be smaller
than $\frac{\alpha}{2}$. Assume that $b_{1}-a_{1}\leq\frac{\alpha}{2}$; if
not, a symmetric argument applies to the last interval.

######  Claim 3.1.1.

Assume that $b_{1}-a_{1}<\frac{\alpha}{2}$. Then,

$F_{t}(m_{1}+\epsilon)-F_{t}(m_{1}-\epsilon)\geq\frac{\alpha}{2}\min\\{\frac{\alpha}{4},\epsilon\\}\min_{y\in\\{\frac{\alpha}{4},2\\}}|g^{\prime}(y)|$

###### Proof.

Let $m$ be the median of $A_{t}$; by the assumption, $m\notin[a_{1},b_{1}]$,
so $m\geq a_{2}$.

$\displaystyle F_{t}(m_{1}+\epsilon)-F_{t}(m_{1}-\epsilon)$
$\displaystyle=\sum_{k=1}^{n}\int_{a_{k}}^{b_{k}}g(y-(m_{1}+\epsilon))\,dy-\sum_{k=1}^{n}\int_{a_{k}}^{b_{k}}g(y-(m_{1}-\epsilon))\,dy$
$\displaystyle=\sum_{k=2}^{n}\int_{a_{k}}^{b_{k}}g(y-(m_{1}+\epsilon))-g(y-(m_{1}-\epsilon))\,dy$
$\displaystyle\geq\sum_{k=2}^{n}(b_{k}-a_{k})[\min_{y\in[a_{k},b_{k}]}g(y-(m_{1}+\epsilon))-g(y-(m_{1}-\epsilon))]$
$\displaystyle\geq\frac{\alpha}{2}[\min_{y\in[m,b_{n}]}g(y-(m_{1}+\epsilon))-g(y-(m_{1}-\epsilon))]$

By definition, $y-m_{1}\geq m-m_{1}>\frac{\alpha}{4}$; in the case where
$m-(m_{1}+\epsilon)>0$,

$g(y-m_{1}-\epsilon)-g(y-m_{1}+\epsilon)>g(y-m_{1})-g(y-m_{1}+\epsilon)\geq\epsilon\min_{z\in[0,\epsilon]}|g^{\prime}(y-m_{1}+z)|$

If $\epsilon$ is large enough such that $y-m_{1}-\epsilon<0$ for some $y$,
then by the symmetry of $g$, $g(y-m_{1}-\epsilon)=g(m_{1}+\epsilon-y)$.
Therefore,

$\displaystyle g(y-m_{1}-\epsilon)-g(y-m_{1}+\epsilon)$
$\displaystyle=g(m_{1}+\epsilon-y)-g(y-m_{1}+\epsilon)\geq
g(\epsilon)-g(y-m_{1}+\epsilon)$
$\displaystyle\geq[y-m_{1}]\min_{z\in[0,y-m_{1}]}|g^{\prime}(\epsilon+z)|$

In both cases, $F_{t}(m_{1}+\epsilon)-F_{t}(m_{1}-\epsilon)$ by restricting
$g^{\prime}$. Let
$c_{1}=\min_{y\in[\frac{\alpha}{4},2]}|g^{\prime}(y)|\leq\min_{y\in[m-m_{1},b_{n}+\epsilon-
m_{1}]}|g^{\prime}(y)|$. Since $g^{\prime}$ is strictly decreasing, Therefore,
for $\epsilon$ small ($\epsilon<m-m_{1}$):

$\displaystyle F_{t}(m_{1}+\epsilon)-F_{t}(m_{1}-\epsilon)$
$\displaystyle\geq\frac{\alpha}{2}[\min_{y\in[m,b_{n}]}g(y-(m_{1}+\epsilon))-g(y-(m_{1}-\epsilon))]$
$\displaystyle\geq\frac{\alpha\epsilon}{2}\min_{y\in[m,b_{n}]}\min_{z\in[0,\epsilon]}g^{\prime}(y-m_{1}+z)$
$\displaystyle\geq\frac{\alpha\epsilon}{2}\min_{y\in[m,b_{n}+\epsilon]}g^{\prime}(y-m_{1})$
$\displaystyle\geq\frac{\alpha}{2}\epsilon c_{1}$

For $\epsilon$ large ($\epsilon\geq m-m_{1}$):

$\displaystyle F_{t}(m_{1}+\epsilon)-F_{t}(m_{1}-\epsilon)$
$\displaystyle\geq\frac{\alpha}{2}[\min_{y\in[a_{2},b_{n}]}g(y-(m_{1}+\epsilon))-g(y-(m_{1}-\epsilon))]$
$\displaystyle\geq\frac{\alpha}{2}\min_{y\in[m,b_{n}]}[y-m_{1}]\min_{z\in[0,y-m_{1}]}|g^{\prime}(\epsilon+z)|$
$\displaystyle\geq\frac{\alpha}{2}\frac{\alpha}{4}\min_{z\in[0,b_{n}-m_{1}]}|g^{\prime}(\epsilon+z)|$
$\displaystyle\geq\frac{\alpha}{2}\frac{\alpha}{4}c_{1}$

In this case,
$F_{t}(m_{1}+\epsilon)-F_{t}(m_{1}-\epsilon)\geq\frac{\alpha}{2}\min\\{\frac{\alpha}{4},\epsilon\\}c_{1}$.
∎

Let $c_{2}=g(0)-g(1)$. Since $g$ is continuous and decreasing, $c_{2}>0$ and
$|\frac{dF_{t}}{dx}|=|\sum_{k=1}^{n}g(a_{k}-x)-g(b_{k}-x)|\leq c_{2}$ . By
3.1.1,

$F_{t}(m_{1}+\epsilon)-F_{t}(m_{1}+\epsilon+\epsilon^{\prime})\geq\frac{\alpha}{2}\min\\{\frac{\alpha}{4},\epsilon\\}c_{1}$

and

$F_{t}(m_{1}+\epsilon)-F_{t}(m_{1}+\epsilon+\epsilon^{\prime})\leq
c_{2}\epsilon^{\prime}$

Combining these two equations implies,

$\epsilon^{\prime}\geq\frac{\alpha}{2}\min\\{\frac{\alpha}{4},\epsilon\\}\frac{c_{1}}{c_{2}}$

The only unbounded value in this equation is $\epsilon$. Recall that
$m_{1}+\delta$ is defined to be the earliest local maximum of $F_{t}$; in the
case of small $\epsilon$, $[m_{1}-\epsilon,m_{1}+\delta]$ is a subset of the
first interval. If $\epsilon\leq\frac{\delta}{2}$, then the midpoint is at
least $m_{1}+\frac{\delta}{4}$.

Therefore, the shift of the midpoint of the first interval depends on the
location of the first local maximum of $F_{t}$. We will show that this is also
bounded from below by a constant value.

######  Claim 3.1.2.

$\delta\geq\frac{\min_{y\in[\frac{\alpha}{8},1]}|g^{\prime}(y)|}{\max_{z\in[0,1]}|g^{\prime}(z)|}\cdot\frac{\alpha}{8}$

###### Proof.

By assumption, at $m_{1}+\delta$, $\frac{dF_{t}}{dx}=0$.

$\displaystyle\sum_{j=1}^{n}g(a_{j}-(m_{1}+\delta))-g(b_{j}-(m_{1}+\delta))=0$

Since $g$ is decreasing and symmetric, the sign of
$g(a_{j}-(m_{1}+\delta))-g(b_{j}-(m_{1}+\delta))$ depends on whether
$m_{1}+\delta$ is closer to $a_{j}$ or $b_{j}$. Suppose this term is negative
for $j=1,...,k$ and positive for $j=k+1,...,n$. Additionally, assume that
$\delta<\frac{\alpha}{8}$; since $b_{1}-a_{1}<\frac{\alpha}{2}$,
$m_{1}+\delta<a_{1}+\frac{\alpha}{4}+\frac{\alpha}{8}<m$. (Recall that $m$ is
defined as the median of $A_{t}$). Using this, we can assume that $a_{k+1}\leq
m$.

Again, since $g$ is decreasing,
$g(a_{j}-x)-g(b_{j}-x)\geq(b_{j}-a_{j})\min_{y\in[a_{j},b_{j}]}|g^{\prime}(y-x)|$.

$\displaystyle\sum_{j=k+1}^{n}g(a_{j}-(m_{1}+\delta))-g(b_{j}-(m_{1}+\delta))$
$\displaystyle\geq\sum_{j=k+1}^{n}\min_{y\in[a_{j},b_{j}]}|g^{\prime}(y-(m_{1}+\delta)|(b_{j}-a_{j})$
$\displaystyle\geq\min_{y\in[m,1]}|g^{\prime}(y-(m_{1}+\delta)|\frac{\alpha}{2}$
$\displaystyle\geq\min_{y\in[\frac{\alpha}{8},1]}|g^{\prime}(y)|\frac{\alpha}{2}$

For $j=1...k$, $g(a_{j}-(m_{1}+\delta))-g(b_{j}-(m_{1}+\delta))<0$.

$\displaystyle\sum_{j=1}^{k}g(b_{j}-(m_{1}+\delta))-g(a_{j}-(m_{1}+\delta))$
$\displaystyle\leq g(b_{k}-(m_{1}+\delta))-g(a_{1}-(m_{1}+\delta))$
$\displaystyle\leq g(b_{k}-(m_{1}+\delta))-g(a_{1}-(m_{1}+\delta))$
$\displaystyle\leq(|a_{1}-(m_{1}+\delta)|-|b_{k}-(m_{1}+\delta)|)\max_{z\in[0,1]}|g^{\prime}(z)|$
$\displaystyle\leq(2(m_{1}+\delta)-b_{k}-a_{1}))\max_{z\in[0,1]}|g^{\prime}(z)|$

Recall that since $\frac{dF_{t}}{dx}=0$, we have:

$\sum_{j=1}^{k}g(b_{j}-(m_{1}+\delta))-g(a_{j}-(m_{1}+\delta))=\sum_{j=k+1}^{n}g(a_{j}-(m_{1}+\delta))-g(b_{j}-(m_{1}+\delta))$

Combining the two equations above:

$(2(m_{1}+\delta)-b_{k}-a_{1}))\max_{z\in[0,1]}|g^{\prime}(z)|\geq\min_{y\in[\frac{\alpha}{8},1]}|g^{\prime}(y)|\frac{\alpha}{2}$

Therefore, $\delta$ is bounded:

$\delta\geq\frac{\min_{y\in[\frac{\alpha}{8},1]}|g^{\prime}(y)|}{\max_{z\in[0,1]}|g^{\prime}(z)|}\cdot\frac{\alpha}{4}+\frac{a_{1}+b_{k}}{2}-m_{1}$

Since $b_{k}\geq b_{1}$, the midpoint of $a_{1}$ and $b_{k}$ is greater than
$m_{1}$. Combining this fact with the earlier assumption that
$\delta<\frac{\alpha}{8}$, we have

$\delta\geq\frac{\min_{y\in[\frac{\alpha}{8},1]}|g^{\prime}(y)|}{\max_{z\in[0,1]}|g^{\prime}(z)|}\cdot\frac{\alpha}{8}$

∎

This implies that in the case where $b_{1}-a_{1}\leq\frac{\alpha}{2}$, the
midpoint of the first interval increases by a constant value. By a symmetric
argument, if $b_{1}-a_{1}>\frac{\alpha}{2}$, then
$b_{n}-a_{n}<\frac{\alpha}{2}$, and the midpoint of the last interval shifts
decreases by a constant value. Since $m_{n}-m_{1}$ decreases at each step, the
process must converge to a single interval in finite steps.

∎

This theorem indicates that the speed of convergence depends on the function
$g$ and the size of $A_{0}$ $(\alpha)$. This process converges to a fixed
point in at most

$O\left(\frac{\max_{[0,1]}|g^{\prime}(x)|}{\min_{[\frac{\alpha}{8},1]}|g^{\prime}(x)|}\right)$

steps. For example, consider the Gaussian function
$g(x)=\exp(\frac{-x^{2}}{2\sigma^{2}})$. We have
$g^{\prime}(x)=-\frac{x}{\sigma^{2}}\exp(\frac{-x^{2}}{2\sigma^{2}})$. The
maximum is:

$\max_{[0,1]}|g^{\prime}(x)|=|g^{\prime}(\sigma)|=\frac{1}{\sigma}\exp(-1/2)\\\
$

The minimum can occur at either endpoint depending on $\alpha$ and $\sigma$:

$\min_{[\frac{\alpha}{8},1]}|g^{\prime}(x)|=\min\left(\left|g^{\prime}\left(\frac{\alpha}{8}\right)\right|,\left|g^{\prime}(1)\right|\right)\approx\min\left(\frac{\alpha}{8\sigma^{2}},\frac{1}{\sigma^{2}}\exp\left(\frac{-1}{2\sigma^{2}}\right)\right)$

If $\alpha<8\left(\frac{-1}{2\sigma^{2}}\right)$, the lower bound on the
number of convergence steps is

$O\left(\frac{\frac{1}{\sigma}\exp(-1/2)}{\frac{1}{\sigma^{2}}\exp\left(\frac{-1}{2\sigma^{2}}\right)}\right)\approx
O(\sigma)$

Otherwise, the bound is

$O\left(\frac{\frac{1}{\sigma}\exp(-1/2)}{\frac{\alpha}{8\sigma^{2}}}\right)\approx
O(\frac{\sigma}{\alpha})$

Another example is the inverse square distance $g(x)=\frac{1}{c+x^{2}}$ for a
value $c>0$. We have $g^{\prime}(x)=\frac{-2x}{(c+x)^{2}}$. The maximum occurs
at $\max_{[0,1]}|g^{\prime}(x)|=\frac{-3\sqrt{3}}{8}c^{-3/2}$. The minimum
occurs at one of the endpoints:

$\min_{[\frac{\alpha}{8},1]}|g^{\prime}(x)|=\min\\{|g^{\prime}(\alpha/8)|,|g^{\prime}(1)|\\}\approx\min\left(\frac{\alpha}{4c^{2}+c\alpha},\frac{2}{(c+1)^{2}}\right)$

Therefore, the lower bound on the number of convergence steps when $c$ is not
small is approximately:

$O\left(\frac{c^{-3/2}(c^{2}+c\alpha)}{\alpha}\right)=O\left(\frac{c^{1/2}}{\alpha}+c^{-1/2}\right)$

For sufficiently small $c$, this gives:

$O\left(c^{-3/2}(c+1)^{2}\right)=O(c^{-3/2})$

##  4 Conclusion and further questions

#### Plasticity.

Our proof shows that plasticity is not necessary for the convergence of the
$k$-cap mechanism. Previous analysis of this process on random graphs studied
a variant of the problem where edges were given a weight, initially set to 1.
If two neighboring vertices fired consecutively, the weight of their edge was
boosted by a factor of $1+\beta$. In Erdős–Rényi random graphs, this weight
proved to be vital for convergence; it allowed a set of vertices to become
associated over time, causing them to fire together [Pap+20, DPV21]. We have
shown that, given sufficiently local graph structure, it is possible for the
process without plasticity to converge to a subset which is small compared to
$n$.

#### Parameter range.

As mentioned in the introduction, $\sigma=O(1/k^{1/d})$ is the parameter range
where the concentration behavior in step $t=0$ seems to emerge. However, it is
unclear whether this is a true ’threshold’; it would be interesting to
determine whether $\sigma=k^{-1/d-\epsilon}$ or $\sigma=k^{-1/d+\epsilon}$
behaves like a pure random graph, or whether some weaker convergence behavior
emerges.

#### General edge probability functions.

In this paper, we have focused our attention on graphs whose edge probability
is proportional to the Gaussian function,
$g(x;\sigma)=e^{-x^{2}/2\sigma^{2}}$. Our proof exploits the structure of this
function; it is important that the edge probability drops off exponentially
after a certain distance. One possible direction for future research is to
consider alternate edge probability functions, and see if the behavior of the
model deviates significantly.

#### Further motivation from Neuroscience.

As discussed above, the geometric model embeds the nodes of the graph as
points in space, and it strongly prefers to connect nodes which are close to
each other. Many real-world graphs have a spatial component and a cost
associated with long-range connections, so the geometric graph model has
theoretical guarantees which match empirical properties of graphs in many
domains. One such property is the clustering coefficient, which measures the
prevalence of cliques between the immediate neighborhood of the vertex [BP03].
In the graph model we have discussed thus far, the clustering coefficient is
quite high; in fact, within a small neighborhood of any vertex the probability
that the vertices form a clique is exponentially likely. In particular, high
clustering between neurons has been observed in the brain [Son+05]. Of course,
the model we have studied is simplified, and it lacks many graph-theoretic
structures which have been observed in the brain. There may be interesting
algorithmic insights which can be gleaned by mimicking empirically observed
structures. Two relevant properties are the power-law degree distribution and
the small world property [BS09]. The first property implies that their are a
small set of ’hub’ neurons with very high degree (in the geometric random
graph, the degree distribution is fairly uniform). The second implies that for
any two neurons, the length of the shortest path between them is not very
large. Both of these properties could have interesting implications for the
$k$-cap mechanism. One concrete question is whether, in a graph with a power-
law degree distribution, the $k$-cap mechanism is likely to converge to a set
of vertices with high degree.

#### The continuous model in higher dimension.

An interesting extension of our continuous model and analysis would be to
consider the process in a higher dimensional vector space. Even in
$\mathbb{R}^{2}$, where $g$ is inversely proportional to the euclidean
distance between two points, the behavior seems significantly more complicated
than the case in $\mathbb{R}$. One open question is to characterize the fixed
points (i.e., the sets where $A_{t+1}=A_{t}$) in higher dimensional vector
spaces.

#### Simulations.

A simulation of the discrete $k$-cap process can be accessed through our
GitHub repository [Rei22].

#### Acknowledgements.

The authors are deeply grateful to Christos Papadimitriou, Max Dabagia,
Debankur Mukherjee and Jai Moondra for helpful comments and discussions. This
work was supported in part by NSF awards CCF-1909756, CCF-2007443 and
CCF-2134105.

## References

  * [Ald13] David Aldous  “Probability approximations via the Poisson clumping heuristic”  Springer Science & Business Media, 2013
  * [Bar11] Marc Barthélemy  “Spatial networks”  In _Physics reports_ 499.1-3 Elsevier, 2011, pp. 1–101
  * [Bog+04] Marián Boguná, Romualdo Pastor-Satorras, Albert Díaz-Guilera and Alex Arenas  “Models of social networks based on social distance attachment”  In _Physical review E_ 70.5 APS, 2004, pp. 056122
  * [BP03] Marián Boguná and Romualdo Pastor-Satorras  “Class of correlated random networks with hidden variables”  In _Physical Review E_ 68.3 APS, 2003, pp. 036112
  * [BS09] Ed Bullmore and Olaf Sporns  “Complex brain networks: graph theoretical analysis of structural and functional systems”  In _Nature reviews neuroscience_ 10.3 Nature Publishing Group, 2009, pp. 186–198
  * [Buz19] György Buzsáki  “The Brain from Inside Out”  Oxford University Press, 2019
  * [Cun+10] Hermann Cuntz, Friedrich Forstner, Alexander Borst and Michael Häusser  “One rule to grow them all: a general theory of neuronal branching and its practical application”  In _PLoS computational biology_ 6.8 Public Library of Science San Francisco, USA, 2010, pp. e1000877
  * [Dar64] John N Darroch  “On the distribution of the number of successes in independent trials”  In _The Annals of Mathematical Statistics_ 35.3 Institute of Mathematical Statistics, 1964, pp. 1317–1321
  * [DPV21] Max Dabagia, Christos H Papadimitriou and Santosh S Vempala  “Assemblies of neurons can learn to classify well-separated distributions”  In _arXiv preprint arXiv:2110.03171_ , 2021
  * [DSS00] Daniel Durstewitz, Jeremy K Seamans and Terrence J Sejnowski  “Neurocomputational models of working memory”  In _Nature neuroscience_ 3.11 Nature Publishing Group, 2000, pp. 1184–1191
  * [DW20] Lutz Dümbgen and Jon A Wellner  “The density ratio of Poisson binomial versus Poisson distributions”  In _Statistics & probability letters_ 165 Elsevier, 2020, pp. 108862
  * [Maa00] Wolfgang Maass  “On the computational power of winner-take-all”  In _Neural computation_ 12.11 MIT Press, 2000, pp. 2519–2535
  * [Pap+20] Christos H Papadimitriou, Santosh S Vempala, Daniel Mitropolsky, Michael Collins and Wolfgang Maass  “Brain computation by assemblies of neurons”  In _Proceedings of the National Academy of Sciences_ 117.25 National Acad Sciences, 2020, pp. 14464–14472
  * [Pen03] Mathew Penrose  “Random geometric graphs”  OUP Oxford, 2003
  * [Ram11] S Ramón y Cajal  “Histology of the nervous system of man and vertebrates (Vols. 1, 2).(N. Swanson & LW Swanson, Trans. 1995)”  New York: Oxford University Press, 1911
  * [Rei22] Mirabel Reid  “Simulations for the k-cap process on geometric random graphs”, 2022  URL: https://github.com/mirabelreid/Assemblies-Simulations
  * [RS98] Martin Raab and Angelika Steger  ““Balls into bins”—A simple and tight analysis”  In _International Workshop on Randomization and Approximation Techniques in Computer Science_ , 1998, pp. 159–170  Springer
  * [Son+05] S. Song, P.. Sjöström, M. Reigl, S. Nelson and D.. Chklovskii  “Highly nonrandom features of synaptic connectivity in local cortical circuits”  In _PLoS Biology_ 3.3, 2005, pp. e68
  * [Vol96] A Yu Volkova  “A refinement of the central limit theorem for sums of independent random indicators”  In _Theory of Probability & Its Applications_ 40.4 SIAM, 1996, pp. 791–794
  * [Wan10] Jun Wang  “Analysis and design of a $k$-winners-take-all model with a single state variable and the heaviside step activation function”  In _IEEE Transactions on Neural Networks_ 21.9 IEEE, 2010, pp. 1496–1506
  * [XZZ19] Chang Xiao, Peilin Zhong and Changxi Zheng  “Enhancing Adversarial Defense by k-Winners-Take-All”  In _International Conference on Learning Representations_ , 2019

##  5 Appendix

###  5.1 Probability Preliminaries

The following lemma relates to the distribution of uniform random points in
$[0,1]$. It will be referred to frequently throughout the proof.

######  Lemma 5.0.1.

All balls of radius $\sqrt{d/2}\left[\frac{6\log n}{n}\right]^{1/d}$ contain
at least one vertex of $G$ almost surely.

###### Proof.

Consider dividing $[0,1]^{d}$ into $n/(3\log n)$ boxes with side length
$[(3\log n)/n]^{1/d}$.

For any box, the probability that it receives no points of $G$ is $(1-(3\log
n)/n)^{n}\leq e^{-3\log n}=n^{-3}$. There are $n/3\log n$ boxes, so by the
union bound, the probability that all boxes have at least one point of $G$ is
$(2n^{2}\log n)^{-1}$.

A ball of radius $\sqrt{d/2}\left[\frac{6\log n}{n}\right]^{1/d}$ contains a
box of side length $\frac{6\log n}{n}$. Any such box contains at least one box
of the partition of $[0,1]^{d}$. Thus, all balls of this radius contains a
vertex of $G$ almost surely. ∎

######  Lemma 5.0.2 (Balls into Bins).

Suppose $m$ balls are assigned uniformly at random to $n$ bins, where
$\frac{n}{polylog(n)}\leq m<<n\log n$. Then, with probability $1-o(1)$, the
maximum load is at least:

$\frac{\ln n}{\ln\gamma}\left[1+0.9\frac{\ln^{(2)}\gamma}{\ln\gamma}\right]$

where $\gamma=\frac{n\log n}{m}$.

###### Proof.

See [RS98] ∎

######  Lemma 5.0.3 (Maximum Degree of Geometric Graph).

Let $X=\\{x_{1},\dots,x_{n}\\}$ be a set of $n$ points chosen uniformly at
random on $[0,1]^{d}$. Define a graph $G(X;r)$ such that there exists an edge
between $x_{i}$ and $x_{j}$ if $\lVert x_{i}-x_{j}\rVert\leq r$.

Define a sequence of radii $(r_{n})_{n}$. Let $\Delta_{n}$ be the maximum
degree of $G$. Define $k_{n}=\frac{\log n}{\log(\log n/(nr_{n}^{d}))}$.

If $nr_{n}^{d}/\log n\rightarrow 0$ and
$\log(1/(nr_{n}^{d}))/\log(n)\rightarrow 0$ as $n\rightarrow\infty$. Then:

$\lim_{n\rightarrow\infty}\frac{\Delta_{n}}{k_{n}}=1\text{ in probability}$

and

$\liminf_{n\rightarrow\infty}\frac{\Delta_{n}}{k_{n}}\geq 1\text{ Almost
surely}$

###### Proof.

See Theorem 6.10 from [Pen03] ∎

Next, the following three lemmas contain different tail bounds for the sums of
independent indicators.

######  Lemma 5.0.4 (Chernoff Bound).

Let $X$ be a sum of independent random indicators with mean $\mu$. Then, for
any $\delta\geq 0$:

$\mathbb{P}(X>(1+\delta)\mu)\leq\exp\left(-\frac{\mu\delta^{2}}{2+\delta}\right)$
$\mathbb{P}(X<(1-\delta)\mu)\leq\exp\left(-\frac{\mu\delta^{2}}{2}\right)$

######  Lemma 5.0.5.

For any binomial random variable $X$ with parameters $k,p$, we can bound the
probability that it exceeds $M$ for any $M>kp$:

$\mathbb{P}(X>M)\leq\exp\left(-kD\left(\frac{M}{k}\mid\mid p\right)\right)$

where $D\left(a\mid\mid p\right)=a\log\frac{a}{p}+(1-a)\log\frac{1-a}{1-p}$.

######  Lemma 5.0.6.

Let $X=\sum_{i=1}^{k}I_{i}$ be the sum of $k$ independent indicators with
probabilities $\mathbb{P}(I_{i})=p_{i}\in(0,1)$. Let $\mu=\mathbb{E}X$, and
let $t_{1},t_{2}$ be integer values such that $t_{1}\geq\lceil\mu\rceil$ and
$t_{2}>t_{1}$. Then,

$\frac{\mathbb{P}(X\geq t_{1})}{\mathbb{P}(X\geq
t_{2})}>\exp\left(\frac{(t_{2}-\lceil\mu\rceil)^{2}-(t_{1}-\lfloor\mu\rfloor)^{2}}{2t_{2}}\right)>\exp\left(\frac{(t_{2}-t_{1})^{2}}{t_{2}}\right)$

###### Proof.

Duembgen et al [DW20] gives a bound on the ratio of two consecutive
probabilities. For any $c$ with $\mathbb{P}(X=c-1)>0$,

$\frac{\mathbb{P}(X=c+1)}{\mathbb{P}(X=c)}<\frac{c}{c+1}\frac{\mathbb{P}(X=c)}{\mathbb{P}(X=c-1)}$
(14)

The mode of $X$ is either at $\lfloor\mathbb{\mu}\rfloor$, $\lceil\mu\rceil$,
or is equally attained at both [Dar64]. The probablity increases monotonically
from $X=0$ up to the mode(s) and then decreases montonically up to $X=k$.

So, we have for any integer $m>\mu$:

$\frac{\mathbb{P}(X=m+1)}{\mathbb{P}(X=m)}<1$ (15)

Using Equation 14 and 15, for any integer $s\geq\lceil\mu\rceil$

$\displaystyle\frac{\mathbb{P}(X=s+1)}{\mathbb{P}(X=s)}$
$\displaystyle<\frac{s}{s+1}\frac{\mathbb{P}(X=s)}{\mathbb{P}(X=s-1)}$
$\displaystyle<\dots$
$\displaystyle<\frac{\lceil\mu\rceil+1}{s+1}\frac{\mathbb{P}(X=\lceil\mu\rceil+1)}{\mathbb{P}(X=\lceil\mu\rceil)}<\frac{\lceil\mu\rceil+1}{s+1}$

We can rewrite the ratio of $\mathbb{P}(X=t_{2})$ and $\mathbb{P}(X=t_{1})$ as
the product of ratios with a difference of 1:

$\frac{\mathbb{P}(X=t_{2})}{\mathbb{P}(X=t_{1})}=\frac{\mathbb{P}(X=t_{2})}{\mathbb{P}(X=t_{2}-1)}\frac{\mathbb{P}(X=t_{2}-1)}{\mathbb{P}(X=t_{2}-2)}\cdots\frac{\mathbb{P}(X=t_{1}+1)}{\mathbb{P}(X=t_{1})}$

Substituting the bound above:

$\frac{\mathbb{P}(X=t_{2})}{\mathbb{P}(X=t_{1})}<\frac{\left(\lceil\mu\rceil+1\right)^{(t_{2}-t_{1})}}{t_{2}(t_{2}-1)(t_{2}-2)\dots(t_{1}+1)}=\prod_{s=t_{1}+1}^{t_{2}}\left(1-\frac{s-\lceil\mu\rceil-1}{s}\right)$

Using the approximation $1-x\leq e^{-x}$, this is at most:

$\leq\exp\left(-\sum_{s=t_{1}+1}^{t_{2}}\frac{s-\lceil\mu\rceil-1}{s}\right)\leq\exp\left(-\frac{\sum_{s=t_{1}}^{t_{2}}s-\lceil\mu\rceil-1}{t_{2}}\right)$

Expanding the sum in the numerator:

$\displaystyle=\exp\left(-\frac{\sum_{s=0}^{t_{2}-\lceil\mu\rceil-1}s-\sum_{s=0}^{t_{1}-\lceil\mu\rceil-1}s}{t_{2}}\right)$
$\displaystyle=\exp\left(-\frac{(t_{2}-\lceil\mu\rceil-1)(t_{2}-\lceil\mu\rceil)-(t_{1}-\lceil\mu\rceil-1)(t_{1}-\lceil\mu\rceil)}{2t_{2}}\right)$
$\displaystyle\leq\exp\left(-\frac{(t_{2}-\lceil\mu\rceil)^{2}-(t_{1}-\lfloor\mu\rfloor)^{2}}{2t_{2}}\right)$

This ratio decreases as $t_{1}$ increases and $t_{2}-t_{1}$ remains constant.
This means that, for any $i>t_{2}$, we have
$\mathbb{P}(X=i)<\exp\left(-\frac{(t_{2}-\lceil\mu\rceil)^{2}-(t_{1}-\lfloor\mu\rfloor)^{2}}{2t_{2}}\right)\mathbb{P}(X=i-(t_{2}-t_{1}))$

$\displaystyle\mathbb{P}(X\geq t_{2})$
$\displaystyle=\sum_{i=\mu+t_{2}\sqrt{\mu}}^{k}\mathbb{P}(X=i)$
$\displaystyle<\sum_{i=\mu+t_{2}\sqrt{\mu}}^{k}\exp\left(-\frac{(t_{2}-\lceil\mu\rceil)^{2}-(t_{1}-\lfloor\mu\rfloor)^{2}}{2t_{2}}\right)\mathbb{P}(X=i-(t_{2}-t_{1}))$
$\displaystyle\leq\exp\left(-\frac{(t_{2}-\lceil\mu\rceil)^{2}-(t_{1}-\lfloor\mu\rfloor)^{2}}{2t_{2}}\right)\mathbb{P}(X\geq
t_{1})$

Expanding $(t_{2}-\lceil\mu\rceil)^{2}-(t_{1}-\lfloor\mu\rfloor)^{2}$, we get
$t_{2}^{2}-t_{1}^{2}-2\lceil\mu\rceil(t_{2}-t_{1})=(t_{2}-t_{1})(t_{2}+t_{1}-2\lceil\mu\rceil)$.
Since $t_{2}>t_{1}\geq\lceil\mu\rceil$ by assumption, this exceeds
$2(t_{2}-t_{1})^{2}$.

∎