Local max-cut in smoothed polynomial time

Introduction

Let $G=(V,E)$ be a connected graph with $n$ vertices and $w:E\rightarrow$ be an edge weight function. The local max-cut problem asks to find a partition of the vertices $\sigma:V\rightarrow\{-1,1\}$ whose total cut weight

There is a natural algorithm to find a local maximum of (1), sometimes referred to as the FLIP algorithm: Start from some initial partition $\sigma$, and until reaching a local maximum, repeatedly find a vertex for which flipping the sign of $\sigma$ would increase the cut weight - and carry out this flip. (To be precise, this is a family of algorithms corresponding to different ways of selecting the improving change when there are multiple possibilities.) This algorithm also corresponds to a natural dynamics for the party affiliation game, and a specific implementation (random selection of an improving vertex) exactly corresponds to the asynchronous Hopfield network dynamics described above. However, it is easy to see that there exists weight functions such that FLIP takes an exponential number of steps before reaching a local maximum. As noted in (Johnson et al., 1988) (who introduced the PLS class), this seems at odd with empirical evidence suggesting that algorithms such as FLIP usually reach a local maximum in a reasonable time. This conflicting situation naturally motivates the study of the smoothed complexity of local max-cut: is it true that after adding a small amount of noise to the edge weights, the FLIP algorithm terminates in polynomial time with high probability? In this paper we answer this question affirmatively, provided that a small amount of noise is added to all vertex pairs (i.e., even to non-edges); in other words, we assume that $G$ is a complete graph. We note that a similar subtlety arises in the smoothed analysis of the simplex algorithm by (Spielman and Teng, 2004) where noise is added to every entry of the constraint matrix (in particular, the null entries are also smoothed).

Our objective is to find a local maximum of $\mathbf{H}$ with respect to the Hamming distance $d(\sigma,\sigma^{\prime})=\#\{v:\sigma(v)\neq\sigma^{\prime}(v)\}$. Equivalently, we are looking for a locally optimal cut in the weighted graph $(G,X)$ (since (1) and (2) differ by the half of the total weight of all edges).

We say that $\sigma^{\prime}$ is an improving move from $\sigma$ if $d(\sigma^{\prime},\sigma)=1$ and $\mathbf{H}(\sigma^{\prime})>\mathbf{H}(\sigma)$. We will sometimes refer to a sequence of improving moves as an improving sequence. The FLIP algorithm iteratively performs improving moves until reaching a configuration with no improving move. An implementation of FLIP specifies how to choose the initial configuration and how to choose among the improving moves available at each step. (Etscheid and Röglin, 2014) show that for any graph with smoothed weights, with high probability, any implementation of FLIP will terminate in at most $n^{C\log(n)}$ steps, for some universal constant $C>0$.

Our main result is that FLIP terminates in a polynomial number of steps for the complete graph. Since our results are asymptotic in $n$, in the rest of the paper we assume $n\geq n_{0}$ for some universal constant $n_{0}$.

Let $G$ be the complete graph on $n$ vertices, and assume the edge weights $X=(X_{e})_{e\in E}$ are independent random variables with $|X|\leq 1$ and density bounded above by $\phi$. For any $\eta>0$, with high probability any implementation of FLIP terminates in at most $O(\phi^{5}n^{15+\eta})$ steps, with implicit constant depending only on $\eta$.

Under the assumptions of Theorem 1.1, the expected number of steps of any implementation of FLIP is $O(n^{15})$, with implicit constant depending only on $\phi$.

Note that any implementation is a very broad category. It includes an implementation where an adversary with unbounded computational power chooses each improving step. Theorem 1.1 implies that even in this case the number of steps is polynomial with high probability.

In the the classical Sherrington-Kirkpatrick model (Sherrington and Kirkpatrick, 1975), a mean field model for a spin glass, the Hamiltonian is exactly a scaled version of the random map defined in (2) and when $X_{ij}$ are i.i.d. Gaussian random variables for all pairs $i,j$. Therefore our Theorem 1.1 implies that in the in the Sherrington-Kirkpatrick model, the maximal length of a monotone path (along which the energy is decreasing) in the random energy landscape is $O(n^{15+\eta})$.

Theorem 1.1 can be equivalently stated as follows.

Let $G$ be the complete graph. Assume the edge weights $X=(X_{e})_{e\in E}$ are independent random variables with $|X|\leq 1$ and density bounded above by $\phi$. The probability that there is an improving sequence of length $\Omega(\phi^{5}n^{15+\eta})$ is $o(1)$.

We say that a sequence $L$ is $\epsilon$-slowly improving from an initial state $\sigma_{0}$ if each step of $L$ increases $\mathbf{H}$ by at most $\epsilon$ (and more than ). Our main task will be to prove the following proposition:

Fix $\eta>0$ and let $\epsilon=n^{-(12+\eta)}\phi^{5}$. Then with high probability, there is no $\epsilon$-slowly improving sequence of length $2n$ from any $\sigma_{0}$.

Proposition 1.6 implies Theorem 1.5 as follows. Since $X_{e}\in$, the maximum total improvement for $\mathbf{H}$ is at most $n^{2}$. If there exists an improving sequence of length at least $\Omega(n^{15+\eta}\phi^{5})$ then there must exist an improving sequence of length $2n$ with total improvement less than $O(n^{-(12+\eta)}\phi^{-5})$. Apart from Section 5 the rest of the paper is dedicated to proving Proposition 1.6.

We believe that the exponent $15$ in Theorem 1.1 is far from tight. In fact we make the conjecture that local max-cut is in smoothed quasi-linear time:

Let $G$ be the complete graph on $n$ vertices, and assume the edge weights $X=(X_{e})_{e\in E}$ are independent random variables with $|X|\leq 1$ and density bounded above by $\phi$. With high probability any implementation of FLIP terminates in at most $n(\phi\log n)^{c}$ steps where $c>0$ is a universal constant.

This quasi-linear time behavior could quite possibly extend to an arbitrary graph $G$; however, the first step should be to show smoothed polynomial complexity in this setting (that is, to generalize Theorem 1.1 to an arbitrary graph). Some graphs are easier than others. E.g., (Elsässer and Tscheuschner, 2011) observed that for graphs with maximum degree $O(\log(n))$ endowed with Gaussian edge weights, with high probability, any implementation of FLIP terminates in a polynomial number of steps. (Since, with high probability, each improving move increases $\mathbf{H}$ significantly.) In the final section of the paper we show that a natural approach to generalize our result to arbitrary graphs cannot work; the proof relies on a new result on combinatorics of words, which is of independent interest.

Preliminaries

In this section we provide a high-level overview of the proof of Proposition 1.6. We also state and prove some lemmas which will be useful in our analysis.

Recall that we work in the state space $\{-1,1\}^{V}$ and that a move flips the sign of a single vertex. Each move can be viewed as a linear operator, which we define now. For any $\sigma\in\{-1,1\}^{V}$ and $v\in V$, we denote by $\sigma^{-v}$ the state equal to $\sigma$ except for the coordinate corresponding to $v$ which is flipped. For such $\sigma,v$ there exists a vector $\alpha=\alpha(\sigma,v)\in\{-1,0,1\}^{E}$ such that $\mathbf{H}(\sigma^{-v})=\mathbf{H}(\sigma)+\langle\alpha,X\rangle$. More specifically $\alpha=(\alpha_{uw})_{uw\in E}$ is defined by

Crucially, note that $\alpha$ does not depend on $X$. We say that $v$ is an improving move from a configuration $\sigma$ if $\langle\alpha,X\rangle>0$. It will be convenient to identify a move with the corresponding vector $\alpha$. Thus we may talk of improving vectors (meaning that $\langle\alpha,X\rangle>0$). Similarly, we say that certain moves are linearly independent if the corresponding vectors are.

A rigorous and more general statement in this direction is given in the following lemma.

This turns out not to be sufficient for our needs. However, if a sequence of moves $L$ is an improving sequence from some initial state, then every contiguous segment of $L$ is also improving from some (different) state. We use the term block to refer to a contiguous segment of some sequence of moves under consideration (we will formally define it in Section 3). Thus to bound the probability that $L$ is improving we can instead consider only a segment of our choice of $L$. Note that there are two competing effects in the choice of a segment: on the one hand the probability that a block is $\epsilon$-slowly improving is generally much larger than the probability that the full sequence is $\epsilon$-slowly improving; on the other hand any given block appears in many different sequences, which yields an improvement in the union bound.

Our proof will proceed in two key steps: (i) find a block of $L$ with relatively high rank (this is done in Section 3), and (ii) apply the union bound we alluded to above in a more efficient way so as to replace the term $2^{n}$ (counting possible initial configurations) by a smaller term (Section 4). To this end, we will want to find a block in $L$ which has a high rank and in which the number of distinct symbols is as small as possible.

2. Preliminary linear algebra

The vector $\alpha_{t}$ is supported precisely on the edges incident to $v_{t}$. The entry in $\alpha_{t}$ corresponding to the edge $\{v_{t},u\}$ is $-\sigma_{t}(v_{t})\sigma_{t}(u)$, which is also equal to $\sigma_{t-1}(v_{t})\sigma_{t-1}(u)$.

We now make the following simple observation.

The rank of $\mathcal{A}_{L}$ does not depend on the initial configuration $\sigma_{0}$.

Let $\mathcal{A}_{L}$ be obtained from some initial configuration $\sigma_{0}$ and let $\mathcal{A}^{\prime}_{L}$ be obtained from another initial configuration $\sigma^{\prime}_{0}$. Both matrices are derived from the same sequence $L$. For any vertex $u$ and time $t$ we have that $\sigma_{t}(u)\sigma^{\prime}_{t}(u)=\sigma_{0}(u)\sigma^{\prime}_{0}(u)$. Thus the row corresponding to an edge $\{u,v\}$ in $\mathcal{A}_{L}$ is $\sigma_{0}(u)\sigma_{0}(v)\sigma^{\prime}_{0}(u)\sigma^{\prime}_{0}(v)$ times the corresponding row in $\mathcal{A}^{\prime}_{L}$, and thus these two matrices have the same rank. ∎

Thus the $t$-th entry of the row corresponding to an edge $e=\{u,v\}$ is non-zero, if and only if $v_{t}\in\{u,v\}$. If $v_{t}=v$, then the $t$-th entry of the row ${\mathbf{A}}[\{u,v\}]$ is the spin of $u$ (the other endpoint of the edge) at time $t$, i.e., $\sigma_{t}(u)$ (which also equals $\sigma_{t-1}(u)$ since $u\neq v=v_{t}$).

Bounding the rank of L𝐿L

The goal of this section is to prove Lemma 3.1 which gives a lower bound on the rank of $L$ in terms of simple combinatorial properties of $L$. First we introduce some notation.

The next lemma is the main result of this section.

Furthermore, if $s(L)<n$ and $L$ does not visit any state more than once, then

$\text{rank}(L)\geq s_{1}(L)+\sum_{i}s(T_{i})=s(L)+\sum_{v}(b(v)-1)^{+}$, where the sum is over the transition blocks of $L$.

Note that $L$ visits a state more than once if $\sigma_{i}=\sigma_{j}$ for some $i<j$, or equivalently the block $L[i+1,j]$ contains every vertex an even number of times. (This clearly is a property of $L$, independent of $\sigma_{0}$). If a sequence is improving, then it cannot revisit any state. We can safely disregard any sequence which fails this condition in later analysis.

(i) Without loss of generality, suppose $1,2,\dots,s$ are the only vertices appearing in $L$, and suppose that $s<n$. Let $t_{i}$ be some time at which vertex $i$ appears in $L$; Consider the $s\times s$ sub-matrix of ${\mathbf{A}}$ restricted to the columns ${t_{i}}$’s and the rows corresponding to edges $\{i,n\}$ for $i=1,2,\dots,s$. By our choice of $t_{i}$, the column $t_{i}$ has a non-zero entry at the row corresponding to $\{i,n\}$, and no others, and thus has full rank $s$. If $s=n$ apply the above reasoning to the set of times $\{t_{1},\dots,t_{n-1}\}$.

(ii) We first make the following simple observation. Given a sequence $L$ which does not revisit any state, if vertex $v$ is moved at least twice, then the block between any two consecutive moves of $v$ contains some vertex $u$ an odd number of times in this block. This is clear, since any block in $L$ contains some vertex an odd number of times by an earlier argument.

We create an auxiliary directed graph $H$ as follows. The vertices of $H$ are the $n$ vertices of $G$. For each repeated vertex $v$, there must be a vertex $u$ that appears an odd number of times between the first two times $v$ appears. We pick one such $u$ arbitrarily, and add to $H$ a directed edge from $v$ to $u$. Note that $H$ might contain both an edge and its reverse (e.g. for the sequence $L=1,2,1,3,2$). Each repeated vertex has one out-going edge in $H$, and so $H$ has exactly $s_{2}$ directed edges. Moreover, directed cycles (including cycles of length $2$) in $H$ are vertex-disjoint, and their total length is at most $s_{2}$. Let us define a sub-graph of $H$ by removing one edge from each directed cycle of $H$. Since the cycles are vertex-disjoint (since the out-degree for each vertex is at most $1$), we remove at most $s_{2}/2$ edges, and obtain an acyclic sub-graph of $H$ with at least $s_{2}/2$ edges.

Since not all vertices appear in $L$, suppose without loss of generality that vertex $n$ does not appear in $L$. Part (ii) of the lemma now follows from the following.

For any acyclic sub-graph $H^{\prime}$ of $H$, the following edges correspond to linearly independent rows in ${\mathbf{A}}$: All edges of $H^{\prime}$, together with $\{v,n\}$ for vertices $v\in L$.

We prove this by induction on the number of edges in $H^{\prime}$. If $H^{\prime}$ is the empty subgraph, these are precisely the rows used to prove part (i). Now suppose $H^{\prime}$ is not empty. Since $H^{\prime}$ is acyclic, there must be a vertex $v$ with in-degree 0 and unique outgoing edge $e=\{v,u\}$. Suppose we have a linear combination $\sum_{i}\lambda_{i}{\mathbf{A}}[\{i,n\}]+\sum_{e\in H^{\prime}}\mu_{e}{\mathbf{A}}[e]=0$, where ${\mathbf{A}}[e]$ is the row corresponding to $e$ and the sum is over the edges of the claim. Let $t_{1},t_{2}$ be the first two times that $v$ moves. By the definition of ${\mathbf{A}}$ (see Definition 2.4), the $t_{1}$-th and $t_{2}$-th entry of ${\mathbf{A}}[\{v,n\}]$ are both $\sigma_{t_{1}}(n)=\sigma_{t_{2}}(n)$ (since $n$ does not move). Furthermore, since $u$ appears an odd number of times between the first two appearance of $v$ we have that the $t_{1}$-th entry and $t_{2}$-th entry of ${\mathbf{A}}[e]$ are of opposite signs. Furthermore, since $v$ has out-degree 1 in $H^{\prime}$ and in-degree 0, among the rows we have picked, only the rows ${\mathbf{A}}[\{v,n\}]$ and ${\mathbf{A}}[e]$ have non-zero entries in positions $t_{1},t_{2}$. We thus have $\lambda_{v}\pm\mu_{e}=0$, implying $\lambda_{v}=\mu_{e}=0$. Thus the linear combination involves only edges of $H^{\prime}\setminus e$ and edges to $n$. Applying the inductive hypothesis to $H^{\prime}\setminus e$ gives that the linear combination is trivial.

(iii) Suppose without loss of generality that $1,\dots,s_{2}$ are the repeated vertices in $L$. By the definition of $b(i)$, there exist times $t_{1}(i),t_{2}(i),\dots,t_{b(i)}(i)$ in different transition blocks at which $i$ moves, and for any $2\leq j\leq b(v_{i})$, there is a singleton vertex $w_{i,j}$ that appears in the block $L[t_{j-1}(i),t_{j}(i)]$.

We claim that the following rows are linearly independent. For each $v$ in $L$ the edge $\{v,n\}$, and for each repeated vertex $i$, the rows $e_{i,j}=\{i,w_{i,j}\}$ for $j=2,\dots,b(i)$.

For any repeated vertex $v_{i}$, among the rows we have picked, the ones which have non-zero entries at times $t_{1}(i),\dots,$ $t_{b(i)}(i)$ correspond to the rows of $\{i,n\}$, and $e_{i,j}$ for $j=2,\dots,b(v_{i})$. At those columns, by Lemma 2.3, we can assume the row ${\mathbf{A}}[\{i,n\}]$ has all ones. The row ${\mathbf{A}}[e_{i,j}]$ has entries $1$ before the (unique) appearance of $w_{i,j}$ and $-1$ after the appearance. Thus the minor for these rows and the sequence of times $\{t_{1}(i),\dots,t_{b(i)}(i)\}$ has the form

This clearly has full rank $b(i)$. For singleton vertices $v$ appearing at time $t=t_{v}$, the only selected row with no-zero $t$-th entry corresponds to edge $\{v,n\}$. Thus if we group together columns for the repeated vertices, the selected rows of ${\mathbf{A}}$ have a block structure, with blocks of the form above along the diagonal and zeros elsewhere. It follows that

Proof of Proposition 1.6

In this section we prove Proposition 1.6, and thus conclude the proof of our main result (Theorem 1.1). We first show in Subsection 4.1 that any improving sequence contains a certain special block which we can use to obtain high rank. Then we conclude the proof of Proposition 1.6 in Section 4.3 with an “improved” union bound argument.

Suppose $s(B)<n$. For a critical block $B$ as in Lemma 4.1, we have

For a critical block $B$ with $s(B)<n$, we have

The two bounds come from Lemmas 3.1 and 4.2. Since $s_{1}(B)+s_{2}(B)=s(B)$, the last bound is obtained by a convex combination of the two preceding bounds. ∎

2. A better bound on improving sequences

Lemma 2.1 implies that the probability that a sequence $L$ is $\epsilon$-slowly improving from any given $\sigma_{0}$ is at most $(\phi\epsilon)^{\text{rank}(L)}$, and therefore the probability that $L$ is $\epsilon$-slowly improving from some $\sigma_{0}$ is at most $2^{n}(\phi\epsilon)^{\text{rank}(L)}$. For sequences with large rank this is sufficiently small for our needs. However, for sequences with small rank and small $s$ a better bound is needed. The next novel ingredient of our proof is an improvement of this bound that reduces the factor of $2^{n}$, provided $s(L)$ is small.

Suppose the random weights $X_{e}$ a.s. have $|X_{e}|\leq 1$. Then

The key idea is that instead of taking a union over the initial state $\sigma_{0}$ for the non-moving vertices, we only consider the influence of the non-moving vertices on the moving vertices.

where $Q(v)=-\sum_{u=s+2}^{n}X_{v_{t},u}\sigma_{0}(u)$. One may think of $Q$ as a constant external field acting on the $s$ moving vertices. Finally, the increments of $\mathbf{H}_{2}$ are linear functionals of the weights on edges with both endpoints in $\{1,\dots,s,s+1\}$. We denote these functionals by $\bar{\alpha}_{t}$, so that

Note that $\bar{\alpha}_{t}$ is simply the restriction of $\alpha_{t}$ to edges with both endpoints in $\{1,\dots,s+1\}$. Observe that $\bar{\alpha}_{t}$ depends on the first $s+1$ coordinates of $\sigma_{0}$, but not on the other coordinates.

where $|\delta_{t}|\leq\epsilon$. If the sequence is $\epsilon$-slowly increasing, then

and thus $\langle\bar{\alpha}_{t},X\rangle$ lies in the union of two intervals of length $4\epsilon$ centered at $\pm d(v_{t})$. Note that $\text{rank}(\bar{\alpha}_{t})=\text{rank}(L)$, since we included in $\bar{\alpha}$ the contributions from the stationary vertex $s+1$. (This holds also if $s=n$.) By Lemma 2.1, the probability of this event is at most $(8\epsilon\phi)^{\text{rank}(L)}$. Crucially, if we know $(\sigma_{0}(i))_{i\leq s+1}$ and $d(v)$ for $v=1,\dots,s$, then the event under consideration is the same for all $2^{n-(s+1)}$ possible configurations $\sigma_{0}$.

The claim now follows by a union bound over the possible values of $(\sigma_{0}(i))_{i\leq s+1}$ and $d(v)$. ∎

3. Proof of Proposition 1.6

The summation is over all initial configurations $\sigma_{0}$ and all possible sequences of improving moves $L$ from $\sigma_{0}$ with $n$ moving vertices. There are $2^{n}$ initial configurations and at most $n^{2n}$ sequences of length $2n$. Since $s=n$, each such sequence has $\text{rank}(L)\geq n-1$ by Lemma 3.1(i). By Lemma 2.1, each term in (5) is bounded by $(\phi\epsilon)^{n-1}$, and so

We turn to the event $R_{1}$, that there exists an initial configuration $\sigma_{0}$ and an $\epsilon$-slowly improving sequence $L$ of length $2n$ such that $s(L)<n$. By Lemma 4.1, on the event $R_{1}$ for some $s<n$ there exists a critical block using precisely $s$ vertices and some initial configuration such that the block is $\epsilon$-slowly improving from that configuration. Thus

This sum tends to as $n\to\infty$ when $\epsilon=n^{-(12+\eta)}\phi^{-5}$ with $\eta>0$. ∎

Corollary 1.2 follows easily from the proof of Proposition 1.6:

Suppose an increasing sequence of length $L\geq 2n$ exists. Since the total weight of any cut is in $[-n^{2}/4,n^{2}/4$, there must be a block of size $2n$ in $L$ such that the total improvement along the block is at most $\epsilon=\frac{n^{2}}{2[L/2n]}\leq 2n^{3}/L$. Let $R(n,L)$ be the probability there is such a block using all $n$ letters ($R_{0}$ above), and $R(s,L)$ the probability there is a critical block of length $2s$ using $s$ letters.

Let $T$ be the number of steps before FLIP terminates. Then we have

and we need to show that the last sum is $O(n^{15})$. For $s=n$, by (6),

and the sum over $L>n^{15}$ is $o(n^{15})$.

For small $s$ the bound above is not sufficient, and we need a better rank bound. There are no critical blocks with $s=1$ or $s=2$. It is easy to check that critical blocks with $s=3$ all have rank $6$. A short exhaustive search yields that critical blocks with $s=4$ have rank $7$ or $8$. Since the number of sequences with $s=3$ or $s=4$ is $O(n^{s})$, for $s=3,4$ we get

A word that is sparse at every scale

Suppose $a>1$, and that $L$ is a sequence of length $an$ in an alphabet of $n$ letters. Then there exists a block $B$ in $L$ such that

Since $m(an)=an-s(L)\geq(a-1)n$, this shows that $\epsilon$ has to be greater than $\frac{a-1}{a\log_{2}(an)}$ which concludes the proof. ∎

It is easy to check that the proof of the rank lower bound given in Lemma 3.1(ii) (and (i)) applies to arbitrary graphs. By using Lemma 5.1 above together with the union bound argument from Section 4.3 one obtains an alternative proof to the quasi-polynomial complexity result of (Etscheid and Röglin, 2014). A tempting approach to prove a polynomial complexity result for any graph would be to “simply” replace the $\log(n)$ term in Lemma 5.1 by some constant. The main result of this section is to show that this cannot be done, and that the $\log(n)$ in Lemma 5.1 is tight up to possibly constant factors. As noted above, this can be interpreted as saying that there exist words which are sparse at every scale. In fact, we prove something stronger, as stated in the following theorem.

The construction proving Theorem 5.2 is probabilistic, and implies that there are many sequences with these properties. We do not optimize the constant $C$ here in order to keep the proof simple and clean. A more careful analysis will improve $C$.

We create a sequence as follows. In stage one of the construction we write down the (potentially) repeated letters. Each repeated letter is written in some random set of locations, possibly overwriting previous letters. Afterwards, in stage two, all positions where no repeated letters have been written are filled in with new and unique letters. Note that it is possible that a potentially repeated letter is overwritten, and consequently appears only once or even not at all in the final sequence.

2. Negative correlations

Negative correlation of the $(U_{t})$ will follow from the following more general statement.

Let $A_{1},\dots,A_{m}$ be some finite sets, and pick a uniform element from each set independently. Let $U_{x}$ be the event that element $x$ is never picked. Then the $U_{x}$ are negatively correlated.

This applies to our model, by taking the sets to be the intervals $[k\gamma i,(k+1)\gamma i)$ for $b_{0}\leq i<b_{1}$ and all $k$.

The effect of conditioning on $U_{s}\,\forall s\in S$ is simple: The element from $A_{i}$ is chosen uniformly from $A_{i}\setminus S$. Clearly this can only decrease the probability that an element $t$ is not selected from any $A_{i}$. Since selections are independent, this gives (10).

Now we prove (11). The claim is equivalent to proving

Let $a_{i}$ be the element picked from $A_{i}$. To obtain the law of $(a_{i})$ conditioned on $U_{t}$, start with the unconditioned selections, and resample each $a_{i}$ if $a_{i}=t$, until another element is chosen. If initially (in the unconditioned vector), every element of $S$ is selected from some $A_{i}$, then this is also true after the resampling, and so the probability of such full occupation is increased. ∎

We use the following generalized Chernoff bounds for negatively correlated events.

Suppose $U_{1},\dots,U_{k}$ are negatively correlated events, and let $Y=\sum_{i=1}^{k}1_{U_{i}}$ be the number of bad events occur. Then for any constant $\delta\in(0,1)$,

3. Analysis of the construction

Let $f(x)=\prod_{i=b_{0}}^{b_{1}-1}\left(\frac{i-1/\gamma+x}{i+x}\right)$. Then $f$ is increasing in $x$, and $d=f(0)$. We have that

as this is a telescoping product. Similarly,

With $a>1$ and $n$ given, we apply the probabilistic construction above with parameters

Note that $b_{0}/b_{1}=n^{-1/2+o(1)}$, and therefore $d$ tends to $\frac{1}{2a}$ as $n\to\infty$.

To estimate $s(B)$, we note that the number of letters in $B$ is at least the number of letters added to $B$ in stage two:

For blocks of length at least $\gamma b_{0}$ this is $e^{-c\log^{2}n}=o(n^{-2})$. By a union bound, with high probability every block of length at least $\gamma b_{0}$ has

and so $\frac{s_{2}(B)}{s(B)}\leq\frac{4}{d\gamma}$. (Shorter blocks have $s_{2}(B)=0$.)

As $n\to\infty$, this decays as $\frac{8a\log(2a)+o(1)}{\log(n)}$, implying the claim for $n$ large enough. By changing $C$ we can get the claim also for all smaller $n$. ∎

References