# A Tight $O(4^{k}/p_{c})$ Runtime Bound for a ($\mu$+1) GA on Jumpk for
Realistic Crossover Probabilities

Andre Opris
University of Passau
Passau, Germany  Johannes Lengler
ETH Zürich
Zürich, Switzerland  Dirk Sudholt
University of Passau
Passau, Germany

###### Abstract

The $\textsc{Jump}_{k}$ benchmark was the first problem for which crossover
was proven to give a speedup over mutation-only evolutionary algorithms.
Jansen and Wegener (2002) proved an upper bound of
$O(\mathrm{poly}(n)+4^{k}/p_{c})$ for the ($\mu$+1) Genetic Algorithm
(($\mu$+1) GA), but only for unrealistically small crossover probabilities
$p_{c}$. To this date, it remains an open problem to prove similar upper
bounds for realistic $p_{c}$; the best known runtime bound for
$p_{c}=\Omega(1)$ is $O((n/\chi)^{k-1})$, $\chi$ a positive constant.

Using recently developed techniques, we analyse the evolution of the
population diversity, measured as sum of pairwise Hamming distances, for a
variant of the ($\mu$+1) GA on $\textsc{Jump}_{k}$. We show that population
diversity converges to an equilibrium of near-perfect diversity. This yields
an improved and tight time bound of $O(\mu n\log(k)+4^{k}/p_{c})$ for a range
of $k$ under the mild assumptions $p_{c}=O(1/k)$ and $\mu\in\Omega(kn)$. For
all constant $k$ the restriction is satisfied for some $p_{c}=\Omega(1)$. Our
work partially solves a problem that has been open for more than 20 years.

Keywords: Runtime analysis, diversity, population dynamics

##  1 Introduction and Motivation

Since the invention of evolutionary algorithms (EAs), researchers have
wondered about the usefulness of the crossover operator. For decades, only
empirical evidence was available, suggesting that using crossover in addition
to mutation improves performance.

In a breakthrough result, Jansen and Wegener [9] presented the first proof
that the use of crossover can speed up the expected optimisation time of a
($\mu$+1) GA, for the $\textsc{Jump}_{k}$ benchmark (defined in Section 2) in
which a “jump” of changing $k$ bits is typically required to reach a global
optimum. However, their result had a severe limitation: the crossover
probability had to be chosen as $p_{c}=O(1/(kn))$, which for large problem
sizes $n$ is unrealistically small. Many researchers already succeeded to
improve on these results [10, 4, 3, 7] (see Table 1 and related work below),
and $\textsc{Jump}_{k}$ is by now the most intensely studied theoretical
benchmark for the benefits of crossover. However, despite intensive research,
the basic questions remained wide open. Excluding the addition of aggressive
diversity-enhancing mechanisms or voting mechanisms, the results fall into two
categories: one line of work could show strong effects of crossover, but as in
[9] had to restrict to unrealistically small $p_{c}$ that go to zero with $n$.
For constant $k$ no better asymptotic than $p_{c}=O(1/n)$ could be achieved in
this case. A second line of research made less artificial assumptions on
$p_{c}$, but could only show very moderate benefits from crossover. The best
known runtime bound in this range was $O((n/\chi)^{k-1})$ [7], where $\chi/n$
is the mutation rate. For the default choice $\chi=1$ and constant $k$, this
saves a moderate factor of $n$ compared to the runtime of $O(n^{k})$ for
mutation-only algorithms. All this was in strong contrast to empirical
evidence [3, 13], which suggests that the expected optimisation time is much
smaller than $O((n/\chi)^{k-1})$, also for large $p_{c}$.

#### Our contribution:

We give massively improved bounds in the regime of large $p_{c}$. We study a
variant of the ($\mu$+1) GA that we call ($\mu$+1) GA with competing
offspring, under a mild condition on $p_{c}$. In a generation executing
crossover, the ($\mu$+1) GA creates $\lambda$ offspring by crossing the same
parents, applying mutation and then continuing the replacement selection with
the best such offspring. In generations without crossover, it creates one
offspring as usual. We show an upper bound of

$O\big{(}\mu\lceil\lambda p_{c}\rceil n\log(k)+4^{k}/p_{c}\big{)}$

when $k=o(\sqrt{n})$ and for suitable $\lambda=\Omega(\sqrt{k}\ln(\mu))$,
$p_{c}=O(1/k)$ and polynomial $\mu=\Omega(kn)$. In an interesting range of $k$
where $k$ is super-logarithmic, but sub-square root this is dominated by the
term $4^{k}/p_{c}$, transferring the upper bound by Jansen and Wegener [9] to
large $p_{c}$. Our analysis applies to crossover probabilities that are larger
by a factor of $n$ compared to [9] and it holds for a larger range of gap
lengths, $k=o(\sqrt{n})$ as opposed to $k=O(\log n)$ from [9]. Another
interesting regime is $k=O(1)$, where our results hold for some constant
$p_{c}=\Omega(1)$ and where we show that, for optimal $\lambda$, the ($\mu$+1)
GA with competing offspring takes expected time $O(\mu n\log\mu)$. This is a
massive improvement over the previously mentioned best result of $O(n^{k-1})$
in this range.

The variant that we study is identical to a standard ($\mu$+1) GA, except that
in steps with crossover, the two parents create not only a single offspring,
but they create $\lambda$ offspring and the fittest of those may enter the
population if it is fit enough. This is a rather mild twist of the standard
algorithm, and we only require a weak condition of
$\lambda=\Omega(\sqrt{k}\log\mu)$. Also, $\lambda$ does not enter the
asymptotic runtime for super-logarithmic gaps as long as it is large enough,
but not excessively large. Apart from the competing offspring, the ($\mu$+1)
GA uses standard operators. We need this variation for our analytical approach
to go through, though we conjecture that our upper bounds also apply to the
original ($\mu$+1) GA algorithm without competing offspring.

Our analysis reveals insights into the evolutionary dynamics of the population
diversity. While previous analyses for large $p_{c}$ could only show that
crossover happens between parents of Hamming distance at least $1$ (see below
for details), we show that a constant fraction of all crossovers happens
between parents of Hamming distance $2k$, which is the largest possible
Hamming distance on the set of local optima of $\textsc{Jump}_{k}$, which we
call plateau. Our improved analyses build on our previous work [12] which
studied equilibrium states for population diversity on a flat (i e., constant)
fitness function. Here we translate this approach to the set plateau.
Diversity is measured as the pairwise Hamming distance between search points
in the population, and we show that this measure is well-suited to capture the
dynamic behaviour of the ($\mu$+1) GA.

#### Related work on crossover for $\textsc{Jump}_{k}$:

Jansen and Wegener [9] presented the first rigorous theoretical proof that
crossover can speed up optimisation. On the function $\textsc{Jump}_{k}$
(formally defined in Section 2) evolutionary algorithms typically get stuck on
plateau and then have to cross a fitness valley to “jump” to the optimum
$1^{n}$ by flipping the remaining $k$ zeros to one. For $k=O(\log n)$ they
proved that a ($\mu$+1) Genetic Algorithm (($\mu$+1) GA) using crossover
optimises the function in expected polynomial time, whereas the (1+1) EA using
only standard bit mutation requires expected time $\Theta(n^{k})$. This holds
for the standard ($\mu$+1) GA and a variant that prevents replicates from
entering the population in steps where no crossover is executed. The reason
for crossover’s superior performance is that, once the population only
contains individuals with $n-k$ ones, crossover can combine parents having
zeros at different positions to create the global optimum $1^{n}$. In the best
case, two parents have zeros at disjoint positions. This is called a
_complementary pair_ and then the probability of uniform crossover turning all
these $2k$ positions to 1 is $(1/2)^{2k}=4^{-k}$.

Jansen and Wegener [9] showed that the ($\mu$+1) GA typically evolves a
population in which at any fixed bit position at most $\mu/(2k)$ individuals
carry a zero. Then for any fixed parent $x$ and any of its 0-bits, there are
at most $\mu/(2k)$ other search points sharing a zero at this position, and
there are at most $k\cdot\mu/(2k)=1/2$ search points sharing any 0-bit with
$x$. Thus, the probability of selecting a complementary pair as parents is at
least $1/2$. This analysis, however, comes with two limitations. It only works
for small $k$, $k=O(\log n)$. More importantly, it requires the crossover
probability $p_{c}$ to be unrealistically small: $p_{c}=O(1/(kn))$. The reason
is that it was unclear how the use of crossover affects the diversity of the
population and this was handled using pessimistic arguments. It was left as an
open problem to analyse the ($\mu$+1) GA with more realistic crossover
probabilities.

The results were later refined by Kötzing et al. [10] using a different
analysis for the ($\mu$+1) GA avoiding replicates in mutation steps. By
showing a sequence of events that suffice to evolve one complementary pair,
they showed a time bound111The original proof in [10] only works for
$p_{c}=k/n$ as smaller $p_{c}$ are not considered when estimating the
probability of the event E6. We expand on this and show how to fix this issue
in the appendix. of $O(\mu n\log(n)+e^{6k}\mu^{k+2}k/p_{c})$ for all
$p_{c}\leq k/n$. Efficient performance could be shown for a larger range of
$k$, $k=o(\sqrt{n})$ and $p_{c}=O(k/n)$. However, this $p_{c}$ is still
unrealistically small as $n$ becomes large.

Dang et al. [4] showed that, when equipping the ($\mu$+1) GA with explicit
diversity-enhancing mechanisms such as fitness sharing, expected times of
$O(n\log(n)+\mu^{2}kn\log(\mu k)+4^{k}/p_{c})$ can be achieved. Since only the
dynamics on the plateau of search points with $n-k$ ones matters, it suffices
to use these diversity mechanisms in the ($\mu$+1) GA’s tie-breaking rule.
However, this does not answer the question why the standard ($\mu$+1) GA is
efficient.

Dang et al. [4] were the first to upper bound the expected time for the
standard ($\mu$+1) GA with crossover probability $p_{c}=1$, that is, always
using crossover. They measured diversity in terms of the size of the largest
species, where a species consists of copies of the same genotype. They showed
that the ($\mu$+1) GA efficiently evolves and keeps a good amount of
diversity, such that there is a probability of $\Omega(1)$ of selecting two
parents of different genotypes. This implies that not all bits must be flipped
by mutation since some bits can be more easily set to 1 by a uniform
crossover. They showed a time bound of $O(n^{k-1}\log n)$ for the best
possible population size, which improves to $O(n^{k-1})$ when increasing the
mutation probability from $1/n$ to $\chi/n$ for a constant $\chi>1$.

Very recently, Doerr et al. [7] improved the analysis from [4] and showed that
diversity, in terms of the largest species, remains for much longer, for a
time exponential in the population size. This yields an improved bound of
$O((n/\chi)^{k-1})$ for constant $\chi$ and $p_{c}=\Omega(1)$ and the best
possible choice of the population size $\mu$. An overview of all previous
runtime bounds222We simplify the bound stated in Doerr et al. [7] using simple
algebraic arguments. Details are shown in the appendix. (excluding those using
aggressive diversity mechanisms) is shown in Table 1.

$\begin{array}[]{lllccc}\text{Paper}&\text{algorithm}&\text{runtime
bound}&p_{c}&\mu&k\\\
\hline\cr\hline\cr\text{\cite[cite]{[\@@bibref{Number}{Jansen2002}{}{}]}}&\text{($\mu$+1)~{}GA
w/o replicates}&O(\mu n(k^{2}+\log(\mu
n))+4^{k}/p_{c})&\leq\frac{\varepsilon}{kn}&\mu\geq k\log^{2}n&O(\log n)\\\
\text{\cite[cite]{[\@@bibref{Number}{Jansen2002}{}{}]}}&\text{($\mu$+1)~{}GA}&O(\mu
n^{2}k^{3}+4^{k}/p_{c})&\leq\frac{\varepsilon}{kn}&\mu\geq k\log^{2}n&O(\log
n)\\\
\text{\cite[cite]{[\@@bibref{Number}{Koetzing2011a}{}{}]}}&\text{($\mu$+1)~{}GA
w/o replicates}&O(\mu n\log(n)+e^{6k}\mu^{k+2}k/p_{c})&\leq\frac{k}{n}&\mu\geq
2&o(\sqrt{n})\\\
\text{\cite[cite]{[\@@bibref{Number}{Dang2017}{}{}]}}&\text{($\mu$+1)~{}GA}&O(\mu
n\sqrt{k}\log(\mu)+n^{k}/\mu+n^{k-1}\log(\mu)))&1&\mu\leq\varepsilon n&o(n)\\\
\text{\cite[cite]{[\@@bibref{Number}{Dang2017}{}{}]}}&\text{($\mu$+1)~{}GA},\chi=1+\Theta(1)&O(\mu
n\sqrt{k}\log(\mu)+\mu^{2}+n^{k-1})&1&\mu\geq k\ln(n)/\varepsilon&o(n)\\\
\text{\cite[cite]{[\@@bibref{Number}{Doerr2024}{}{}]}}&\text{($\mu$+1)~{}GA},\chi=\Theta(1)&O\left(\mu
n\log(\mu)+n\log(n)+\left(\frac{n}{\chi}\right)^{k-1}\left(1+\frac{(n/k+\mu)\log(\mu)}{\exp(p_{c}\mu/(2048e))}\right)\right)&\Omega(1)&\mu\geq
2,\mu=o(n)&o(n)\\\ \text{this}&\text{($\mu$+1)~{}GA},\lambda\geq
6\sqrt{k}e^{\chi}\ln(\mu)&O\left(\mu\lceil\lambda
p_{c}\rceil\left(n\log\left(\frac{1}{\varepsilon}\right)+\log\mu\right)+4^{(1-8\varepsilon)k}\left(\frac{n}{\chi}\right)^{\lfloor
8\varepsilon
k\rfloor}/p_{c}\right)&O(\varepsilon)&\mu=\Omega(n/\varepsilon)&o({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}n})\\\
\text{this}&\text{($\mu$+1)~{}GA},\lambda\geq
6\sqrt{k}e^{\chi}\ln(\mu)&O\left(\mu
n\log(k)+4^{k}/p_{c}\right)&O(1/k)&\mu\geq 25kn/(3\chi^{2})&o(\sqrt{n})\\\
\text{this}&\text{all of the
above}&\Omega\left(\min\\{4^{k}/p_{c},\binom{n}{k}\\}\right)&>0&&o(\sqrt{n})\\\
\hline\cr\hline\cr\end{array}$ Table 1: Overview of runtime bounds for the
($\mu$+1) GA and restrictions on parameters. Here $\varepsilon>0$ is a small
enough positive constant. Standard bit mutation with mutation probability
$\chi/n$ is used, with a default of $\chi=1$. The parameter $\lambda$ refers
to the number of competing crossover offspring. The lower bound applies to all
unbiased mutation operators. Some algorithms exclude mutations where no bit
flips (“replicates”), in steps without crossover. Some results additionally
assume $\mu=n^{O(1)}$; this is omitted for brevity. Upper bounds from [10, 7]
are adapted from the original source. For bounds for the ($\mu$+1) GA equipped
with explicit diversity-enhancing mechanisms we refer to [4].

#### Outline:

We first give an exact formula for the equilibrium of population diversity for
the standard ($\mu$+1) EA without crossover in Section 3. These results are
formulated and proven for arbitrary unbiased mutation operators. In Section 4
we then bound the equilibrium for the ($\mu$+1) GA with crossover and
competing crossover offspring. Runtime bounds are derived from this in Section
5, including a lower bound showing that the dominant term $4^{k}/p_{c}$ is
necessary.

##  2 Preliminaries

#### Notation:

For $m\in\mathds{N}$ we write $[m]:=\\{1,2,\ldots,m\\}$. For
$x\in\\{0,1\\}^{n}$ we denote by $\left|x\right|_{1}$ the number of ones and
by $\left|x\right|_{0}$ the number of zeros in $x$, respectively. For
$x,y\in\\{0,1\\}^{n}$, the _Hamming distance_
$H(x,y):=\sum_{i=1}^{n}|x_{i}-y_{i}|$ is the number of positions in which $x$
and $y$ differ. For $r\in[n]$ and $x,y\in\\{0,1\\}^{n}$ we define
$H_{r}(x,y):=1$ if $x_{r}\neq y_{r}$ and $H_{r}(x,y)=0$ otherwise.

The fitness function $\textsc{Jump}_{k}$ is defined as

$\textsc{Jump}_{k}(x):=\begin{cases}\left|x\right|_{1}+k&\text{if
}\left|x\right|_{1}=n\text{ or }\left|x\right|_{1}\leq n-k,\\\
n-\left|x\right|_{1}&\text{otherwise}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
By plateau we mean the set of all search points with $n-k$ ones. We define
$\textsc{Jump}_{k}^{\prime}$ as a fitness function with
$\textsc{Jump}_{k}^{\prime}(x)=\textsc{Jump}(x)$ if ${x\neq 1^{n}}$ and
$\textsc{Jump}_{k}^{\prime}(x)=0$ otherwise. In $\textsc{Jump}_{k}^{\prime}$
jumps from plateau to $1^{n}$ are forbidden and this allows us to study
equilibria for population diversity on the plateau. Note that every
$x\in\textsc{plateau}$ optimises $\textsc{Jump}_{k}^{\prime}$. Let
$q:=\min(k,n-k)$. We write $\ln^{+}(z)\coloneqq\max\\{1,\ln z\\}$.

#### Algorithms:

For $t\in\mathbb{N}_{0}$ let a population $P_{t}$ of $\mu$ individuals be
defined as $P_{t}:=\\{x_{1},\ldots,x_{\mu}\\}$ where $x_{i}\in\\{0,1\\}^{n}$
for $i\in\\{1,\ldots,n\\}$. We define the $(\mu+1)$ EA without crossover and a
$(\mu+1)$ GA using crossover with crossover probability $p_{c}\in[0,1]$ on
such a population $P_{t}$.

The former starts with some initial population, selects a parent $x$ uniformly
at random and creates an offspring $y$ by using a mutation operator on $x$.
Then $y$ replaces a worst search point $z$ in the current population if its
fitness is no worse than $z$.

1 $t\leftarrow 0$

2 Let $P_{0}$ contain $\mu$ search points chosen uniformly at random

3 while  _termination criterion not met_ do

4 Select $x\in P_{t}$ uniformly at random

5 $y\leftarrow\mathrm{mutation}(x)$

6 Select $z\in P_{t}$ uniformly at random from all search points with minimum
fitness in $P_{t}$

7 if  _$f(y)\geq f(z)$_ then

8 $P_{t+1}\leftarrow(P_{t}\cup\\{y\\})\setminus\\{z\\}$

9 $t\leftarrow t+1$

Algorithm 1 (The $(\mu+1)$ EA maximising $f\colon\\{0,1\\}^{n}\to\mathbb{R}$).

With probability $p_{c}$ the $(\mu+1)$ GA picks two parents $x_{1},x_{2}$
uniformly at random with replacement, generates an offspring via crossover on
$x_{1}$ and $x_{2}$, followed by a mutation operator. With probability
$(1-p_{c})$ it applies $\mathrm{mutation}$ to one parent chosen uniformly at
random. The mutant $y^{\prime}$ replaces a worst search point $z$ from the
previous population if its fitness is no worse than $z$.

1 $t\leftarrow 0$

2 Let $P_{0}$ contain $\mu$ search points chosen uniformly at random

3 Choose $p_{c}\in[0,1]$ and $\chi\in\\{0,\ldots,n\\}$

4 while  _termination criterion not met_ do

5 Choose $b\in[0,1]$ uniformly at random

6 if  _$b\leq p_{c}$_ then

7 Choose $x_{1},x_{2}$ uniformly at random from $P_{t}$

8 for  _$i=1$ to $\lambda$_ do

9 $y_{i}\leftarrow\mathrm{crossover}(x_{1},x_{2})$

10 $y_{i}^{\prime}\leftarrow\mathrm{mutation}(y)$

11

12 Choose $y^{\prime}$ uniformly at random from all $y_{i}^{\prime}$ with
maximum fitness in $\\{y_{1}^{\prime},\dots,y_{\lambda}^{\prime}\\}$

13

14 else

15 Select $y\in P_{t}$ uniformly at random

16 $y^{\prime}\leftarrow\mathrm{mutation}(y)$

17

18 Select $z\in P_{t}$ uniformly at random from all search points with minimum
fitness in $P_{t}$

19 if  _$f(y^{\prime})\geq f(z)$_ then

20 $P_{t+1}\leftarrow(P_{t}\cup\\{y^{\prime}\\})\setminus\\{z\\}$

21 $t\leftarrow t+1$

Algorithm 2 (($\mu$+1) GA with $\lambda$ competing crossover offspring and
mutation probability $p_{c}\in[0,1]$ maximising
$f\colon\\{0,1\\}^{n}\to\mathbb{R}$ ).

Mutation operators will be chosen from the class of _unary unbiased variation
operators_ [11], or _unbiased mutation operators_ for short, that treat all
bit values and all bit positions symmetrically (see [11] for a formal
definition). A well-known implication is the following.

######  Lemma 2.1.

Consider an unbiased mutation operator that flips $\chi$ bits in expectation.
Then for any arbitrary but fixed bit $i$, the probability that it is being
flipped is $\chi/n$.

The operator flipping every bit _independently_ with probability $\chi/n$ is
called _standard bit mutation_. Note that in other mutation operators (e.g.
flipping exactly $\chi\in\mathbb{N}_{0}$ bits), each fixed bit is also flipped
with probability $\chi/n$, but these decisions may not be independent for all
bits. A well-known crossover operator which we use throughout this paper is
uniform crossover, in which every bit is taken from a parent chosen uniformly
at random.

#### Diversity Measure:

In this paper we use the sum of Hamming distances as a diversity measure which
is defined in the following.

######  Definition 2.2.

For a population $P_{t}=\\{x_{1},\dots,x_{\mu}\\}$ and a search point
$y\in\\{0,1\\}^{n}$ we define

$S_{P_{t}}(y)\coloneqq\sum\nolimits_{i=1}^{\mu}H(x_{i},y)\quad\text{and}\quad
S(P_{t})\coloneqq\sum\nolimits_{i=1}^{\mu}\sum\nolimits_{j=1}^{\mu}H(x_{i},x_{j}),$

and for $r\in[n]$ we write
$S_{r}(P_{t}):=\sum\nolimits_{i=1}^{\mu}\sum\nolimits_{j=1}^{\mu}H_{r}(x_{i},x_{j})$,
so that $S(P_{t})=\sum\nolimits_{r=1}^{n}S_{r}(P_{t})$.

The population diversity can be computed by considering each bit position
individually and counting how many population members have a zero or a one,
respectively.

######  Lemma 2.3 (Theorem 1a in [15]).

Let $P_{t}$ be a population of size $\mu$ and $m_{i}$ denote the number of
members of $P_{t}$ having a zero at position $i$, then
$S(P_{t})=\sum\nolimits_{i=1}^{n}2m_{i}(\mu-m_{i})$.

Note the symmetry of zeros and ones in the expression $m_{i}(\mu-m_{i})$. The
factor 2 accounts for the fact that every pair $(x_{i},x_{j})$ with $i\neq j$
is counted twice in
$\sum\nolimits_{i=1}^{\mu}\sum\nolimits_{j=1}^{\mu}H(x_{i},x_{j})$. According
to [12], $S(P_{t})$ is twice the sum of all Hamming distances of each pair
$x_{i},x_{j}$ with $i\neq j$, the average value of $S_{P_{t}}(y)$ over $y\in
P_{t}$ is $S(P_{t})/\mu$ and the average Hamming distance of two random points
in $P_{t}$ is $S(P_{t})/\mu^{2}$. The latter implies that if
$S(P_{t})>a\mu^{2}$ for $a\in\mathbb{R}$, there is at least one pair
$(x_{1},x_{2})$ of individuals with $H(x_{1},x_{2})>a$. Note that the average
Hamming distance of two _different_ random search points is
$S(P_{t})/(\mu^{2}-\mu)$. For populations $P_{t}\subseteq\textsc{plateau}$,
the maximum Hamming distance between two different search points is $2k$ and
thus by summing $H(x_{i},x_{j})$ of all search points we obtain ${S(P_{t})\leq
2k\mu(\mu-1)}$ since there are $\mu^{2}$ summands in total and the $\mu$
summands of the form $H(x_{i},x_{i})$ for $i\in[\mu]$ are zero. More
precisely, the maximum diversity is obtained if the zeros in the population
are spread across bit positions as evenly as possible, i.e. if every bit
position has a zero in $\lfloor k\mu/n\rfloor$ or $\lceil k\mu/n\rceil$
individuals.

We give an upper bound on the expected time for the whole population of the
($\mu$+1) GA to reach the plateau. It is similar to Lemma 2.1 in [4], but it
includes evaluations for $\lambda$ competing crossover offspring and allows
arbitrary unbiased mutation operators.

######  Theorem 2.4.

Consider the ($\mu$+1) GA applying uniform crossover with crossover
probability $p_{c}$ and an unbiased mutation operator flipping no bits with
probability $f_{0}$ and flipping a single bit with probability $f_{1}$ on
Jump. For all parameters $p_{c}<1$, $f_{0}>0$, $f_{1}>0$, $\mu\in\mathds{N}$
and every initial population, the expected time for reaching the global
optimum or creating a population on the plateau is

$O\left(\left(1+\frac{\lambda p_{c}}{1-p_{c}}\right)\left(\mu
n\left(\frac{1}{f_{0}}+\frac{1}{f_{1}}\right)+\frac{n\log
n}{f_{1}}+\frac{\mu\log\mu}{f_{0}}\right)\right){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
For standard bit mutation with mutation probability $\Theta(1/n)$ and
$p_{c}\leq 1-\Omega(1)$ this simplifies to $O(\lceil\lambda p_{c}\rceil(\mu
n+n\log(n)+\mu\log\mu))$.

###### Proof.

The proof is a generalisation of Witt’s analysis of the ($\mu$+1) EA on OneMax
[16] where we focus on steps not executing crossover.

We first prove the result for the special case $p_{c}=0$, where crossover is
turned off and the factor $1+\frac{\lambda p_{c}}{1-p_{c}}$ disappears.

Let $T_{i}$ denote the number of generations in which the best individual has
a fitness of $i$ and $s_{i}$ denote the probability of mutation creating an
offspring of fitness larger than $i$ from a parent with fitness $i$. Let
$j\in\\{1,\dots,\mu\\}$. We first bound the expected waiting time until the
population contains at least $j$ individuals of fitness $i$, or until it
contains an individual of fitness larger than $i$. Note that, if an individual
of fitness $i$ is cloned, an individual with smaller fitness is removed from
the population. If there are $\ell$ individuals of fitness $i$, a sufficient
condition for the former event is to not execute crossover, to select one of
$\ell$ fitness-$i$ individuals as parent and to not flip any bits. As these
events are independent, the probability of these events is
$(1-p_{c})\cdot\ell/\mu\cdot f_{0}$. The expected waiting time for increasing
the number of individuals with fitness at least $i$ is thus at most
$\mu/((1-p_{c})\ell f_{0})$. Summing up all times for
$\ell\in\\{1,\dots,j-1\\}$ yields an upper time bound of

$\frac{\mu}{(1-p_{c})f_{0}}\cdot
H(j-1)\leq\frac{\mu}{(1-p_{c})f_{0}}\cdot(\ln(j)+1)$ (1)

where $H(j):=\sum_{\ell=1}^{j}1/\ell$. Once the population contains at least
$j$ individuals of fitness $i$, the probability of creating an offspring with
fitness larger than $i$ is at least $(1-p_{c})\cdot j/\mu\cdot s_{i}$. The
expected waiting time for this event is at most $\mu/(js_{i}(1-p_{c}))$.
Together, we obtain the following family of upper bounds for all values of
$j\in\\{1,\dots,\mu\\}$:

$\mathrm{E}(T_{i})\leq\frac{\mu}{1-p_{c}}\left(\frac{\ln(j)+1}{f_{0}}+\frac{1}{js_{i}}\right).$

Now we choose $j\coloneqq\min\\{\lceil f_{1}/s_{i}\rceil,\mu\\}$, then we can
bound the expected time to first reach the plateau or the global optimum as
follows:

$\displaystyle\sum\nolimits_{i=0}^{n-1}\mathrm{E}(T_{i})\leq\frac{\mu}{1-p_{c}}\sum\nolimits_{i=0}^{n-1}\left(\frac{\ln(j)+1}{f_{0}}+\frac{1}{js_{i}}\right)$
$\displaystyle=\;$
$\displaystyle\frac{\mu}{1-p_{c}}\left(\frac{n}{f_{0}}+\frac{1}{f_{0}}\sum\nolimits_{i=0}^{n-1}\ln(\lceil
f_{1}/s_{i}\rceil)+\sum\nolimits_{i=0}^{n-1}\frac{1}{\min\\{\lceil
f_{1}/s_{i}\rceil,\mu\\}s_{i}}\right).$ (2)

Note that for $0\leq i\leq k-1$ we have $s_{i}\geq f_{1}(n-i)/n$ since a
parent with fitness $i$ has $n-i$ ones and it suffices to flip a single one to
obtain a fitness improvement. Similarly, for $k\leq i\leq n-1$ we have
$s_{i}\geq f_{1}(n+k-i)/n$ as all search points with fitness $i$ have $i-k$
ones and $n-(i-k)=n+k-i$ zeros and flipping a single zero is sufficient for a
fitness improvement. Note that every value $1/s_{j}$ is contained at most
twice in the sum $\sum\nolimits_{i=0}^{n-1}1/s_{i}$, thus
$\sum\nolimits_{i=0}^{n-1}1/s_{i}\leq(2/f_{1})\sum\nolimits_{i=0}^{n-1}n/(n-i)$.
If $f_{1}/s_{i}\leq 1$ then $\lceil f_{1}/s_{i}\rceil=1$ and
$\sum\nolimits_{i=0}^{n-1}\ln(\lceil f_{1}/s_{i}\rceil)=0$. Thus, we may
assume $f_{1}/s_{i}>1$ and use $\lceil f_{1}/s_{i}\rceil\leq 2f_{1}/s_{i}$:

$\displaystyle\sum\nolimits_{i=0}^{n-1}\ln(\lceil
f_{1}/s_{i}\rceil)\leq\sum\nolimits_{i=0}^{n-1}\ln(2f_{1}/s_{i})\leq\ln(2)n+\sum\nolimits_{i=0}^{n-1}\ln(f_{1}/s_{i})$
$\displaystyle\leq\;$
$\displaystyle\ln(2)n+2\sum\nolimits_{i=0}^{n-1}\ln(n/(n-i))=\ln(2)n+2\ln\left(\prod_{i=0}^{n-1}\frac{n}{n-i}\right)$
$\displaystyle=\;$
$\displaystyle\ln(2)n+2\ln\left(\frac{n^{n}}{n!}\right)\leq\ln(2)n+2\ln\left(\frac{n^{n}}{(n/e)^{n}}\right)=\ln(2)n+2\ln(e^{n})=(\ln(2)+2e)n.$

The second sum is bounded as follows.

$\displaystyle\sum\nolimits_{i=0}^{n-1}\frac{1}{\min\\{\lceil
f_{1}/s_{i}\rceil,\mu\\}s_{i}}\leq\sum\nolimits_{i=0}^{n-1}\frac{1}{\min\\{f_{1},\mu
s_{i}\\}}\leq\sum\nolimits_{i=0}^{n-1}\left(\frac{1}{f_{1}}+\frac{1}{\mu
s_{i}}\right)$ $\displaystyle=\;$
$\displaystyle\frac{n}{f_{1}}+\frac{1}{\mu}\sum\nolimits_{i=0}^{n-1}\frac{1}{s_{i}}\leq\frac{n}{f_{1}}+\frac{2}{f_{1}\mu}\sum\nolimits_{i=0}^{n-1}\frac{n}{n-i}=\frac{n}{f_{1}}+\frac{2nH(n)}{f_{1}\mu}.$

Plugging this back into (2), we obtain an upper bound of

$\displaystyle\frac{\mu}{1-p_{c}}\left(\frac{n}{f_{0}}+\frac{(\ln(2)+2e)n}{f_{0}}+\frac{n}{f_{1}}+\frac{2nH(n)}{f_{1}\mu}\right)=\;O\left(\frac{\mu
n}{1-p_{c}}\left(\frac{1}{f_{0}}+\frac{1}{f_{1}}\right)+\frac{n\log
n}{(1-p_{c})f_{1}}\right)$

for the expected time until the first point on the plateau (or a global
optimum) is created, that is, a fitness of at least $n$. Unless a global
optimum is reached, we still need to account for the expected time until _all_
individuals have reached the plateau (or a global optimum is reached). By (1),
the expected time until $j\coloneqq\mu$ individuals have fitness $n$ (or a
global optimum is reached) is at most

$\frac{\mu}{(1-p_{c})f_{0}}\cdot(\ln(\mu)+1)$

and together this yields the claimed time bound for $p_{c}=0$.

For $p_{c}>0$ we argue that, owing to elitism, if we were to add steps using
crossover at no cost, this cannot increase the time to reach the target
conditions. Hence we may re-use the above analyses based on mutation-only
steps and take into account the evaluations made in between two mutation-only
steps. Let $M$ be the random number of mutation steps in the scenario
$p_{c}=0$ and $L$ be the random number of evaluations made up to and including
the first mutation-only step. Note that $L$ does not depend on the current
population, and thus we have a sequence of iid random variables with the same
distribution as $L$. Thus, we can upper bound the expected number of
evaluations for the ($\mu$+1) GA by $\mathrm{E}(M)\cdot\mathrm{E}(L)$ using
Wald’s equation. It remains to work out $\mathrm{E}(L)$. If the first
mutation-only step happens in step $t$, the ($\mu$+1) GA makes
$(t-1)\lambda+1$ evaluations. The probability of this happening in step $t$ is
$p_{c}^{t-1}(1-p_{c})$. Together,

$\displaystyle\mathrm{E}(L)$
$\displaystyle=1+\sum\nolimits_{t=1}^{\infty}p_{c}^{t-1}(1-p_{c})\cdot(t-1)\lambda=1+(1-p_{c})\lambda\sum\nolimits_{t=0}^{\infty}p_{c}^{t}\cdot
t$
$\displaystyle=1+(1-p_{c})\lambda\cdot\frac{p_{c}}{(1-p_{c})^{2}}=1+\frac{p_{c}\lambda}{1-p_{c}}.$

The final statement follows easily using $1+x\leq 2=2\lceil x\rceil$ if
$0<x\leq 1$ and $1+x\leq 2x\leq 2\lceil x\rceil$ if $x>1$, thus $1+x\leq
2\lceil x\rceil$ and $1+p_{c}\lambda/(1-p_{c})=O(\lceil\lambda
p_{c}/(1-p_{c})\rceil)=O(\lceil\lambda p_{c}\rceil)$ since
$p_{c}=1-\Omega(1)$. ∎

One can easily get a similar upper bound for $p_{c}=1$ because when selecting
two identical parents for crossover, a standard bit mutation is performed.

##  3 Equilibrium State for $S(P_{t})$ on Plateau for the ($\mu$+1) EA

Now we will compute the expected change of $S(P_{t})$, i.e.,
$\mathrm{E}(S(P_{t+1})\mid S(P_{t}))$ if all individuals from $S(P_{t})$ are
in plateau. To this end we investigate the population dynamics of evolutionary
algorithms on the modification $\textsc{Jump}_{k}^{\prime}$ of the
$\textsc{Jump}_{k}$ benchmark where the global optimum is removed.

We break the process down into several steps. Even though our main goal is to
analyse the ($\mu$+1) GA with standard bit mutation as described in Algorithm
2, we make an effort to keep structural results as general as possible as they
might be of independent interest. In particular, we start by considering
arbitrary mutation operators, then focus on unbiased mutation and finally
arrive at standard bit mutation. For the same reason, we formulate many
statements for $q=\min\\{k,n-k\\}$, which considers jumps of size $k>n/2$,
even though our main result is limited to $k=o(\sqrt{n})$, that is, $q=k$.

We start with a lemma which describes, for given $x,y\in$ plateau, the effect
of flipping $\ell$ random $0$-bits and $\ell$ random $1$-bits of $y$ on the
distance from $x$. Note that this yields an offspring in plateau.

######  Lemma 3.1.

Suppose that $x,y\in\textsc{plateau}$ (i.e.
$\left|x\right|_{1}=\left|y\right|_{1}=n-k$) and let $z$ be generated from $y$
by flipping $\ell$ ones and $\ell$ zeros chosen uniformly at random for
$\ell\in\\{0,\dots,q\\}$. Then

$\displaystyle\mathrm{E}(H(x,z))$ $\displaystyle=2\ell+\big{(}1-\tfrac{\ell
n}{k(n-k)}\big{)}H(x,y).$

###### Proof.

Consider $z_{0},z_{1}$ where

  * •

$z_{0}$ be generated from $y$ by flipping $\ell$ zeros chosen uniformly at
random,

  * •

$z_{1}$ be generated from $y$ by flipping $\ell$ ones chosen uniformly at
random.

Then we show that

$\displaystyle\mathrm{E}(H(x,z_{0}))$
$\displaystyle=\ell+\left(1-\frac{\ell}{k}\right)H(x,y),$
$\displaystyle\mathrm{E}(H(x,z_{1}))$
$\displaystyle=\ell+\left(1-\frac{\ell}{n-k}\right)H(x,y),$

and conclude on $H(x,z)$. We start with $z_{0}$. We write $R:=\\{i\in[n]\mid
y_{i}=0\\}$ and $R^{c}:=[n]\setminus R$. Note that $|R|=k$ and $R^{c}=n-k$
since $y$ is in plateau. Moreover, for any $x_{1},x_{2}\in\\{0,1\\}^{n}$ we
write $H_{R}(x_{1},x_{2})$ for the number of bits _in $R$_ in which $x_{1}$
and $x_{2}$ differ, and similarly for $R^{c}$. In particular,
$H(x_{1},x_{2})=H_{R}(x_{1},x_{2})+H_{R^{c}}(x_{1},x_{2})$. Moreover, since
$x$ and $y$ are both in plateau we have $H_{R}(x,y)=H_{R^{c}}(x,y)=H(x,y)/2$.

Since $z_{0}$ is obtained from $y$ by only flipping zeros, the set $R^{c}$ is
untouched by the mutation, and hence
$H_{R^{c}}(x,z_{0})=H_{R^{c}}(x,y)=H(x,y)/2$. For the $k$ positions in $R$,
each of them is flipped with probability $\ell/k$. There are $H_{R}(x,y)$ bits
in $R$ in which $x$ and $y$ differ, and for any such bit the Hamming distance
decreases by one if the bit is flipped. Likewise, there are $|R|-H_{R}(x,y)$
bits in $R$ in which $x$ and $y$ coincide, and for any such bit the Hamming
distance increases by one if the bit is flipped. Combining these two cases
yields

$\displaystyle\mathrm{E}(H_{R}(x,z_{0}))=H_{R}(x,y)+\frac{\ell}{k}\cdot\left(-H_{R}(x,y)+(|R|-H_{R}(x,y))\right)$
$\displaystyle=H_{R}(x,y)+\frac{\ell}{k}\cdot\left(|R|-2H_{R}(x,y)\right).$

Plugging in $H_{R}(x,y)=H(x,y)/2$ and $|R|=k$ and simplifying yields

$\displaystyle\mathrm{E}(H_{R}(x,z_{0}))$
$\displaystyle=\ell+\left(\frac{1}{2}-\frac{\ell}{k}\right)H(x,y),$ (3)

and hence

$\displaystyle\mathrm{E}(H(x,z_{0}))$
$\displaystyle=H_{R^{c}}(x,z_{0})+\mathrm{E}(H_{R}(x,z_{0}))$
$\displaystyle=\frac{H(x,y)}{2}+\ell+\left(\frac{1}{2}-\frac{\ell}{k}\right)H(x,y)$
$\displaystyle=\ell+\left(1-\frac{\ell}{k}\right)H(x,y).$

For $z_{1}$, the roles of $R$ and $R^{c}$ are reversed, with the notable
difference that the probability of flipping each bit in $R^{c}$ is now
$\ell/|R^{c}|=\ell/(n-k)$. The formula

$\displaystyle\mathrm{E}(H_{R^{c}}(x,z_{1}))$
$\displaystyle=\ell+\left(\frac{1}{2}-\frac{\ell}{n-k}\right)H(x,y)$ (4)

and the final result follows analogously.

For $z$ we observe that flipping zeros of $y$ only affects $R$ and flipping
ones only affects $R^{c}$, and on those sets the process is identical to the
generation of $z_{0}$ and $z_{1}$ respectively. Hence, the formulas (3) and
(4) still hold with $z$ instead of $z_{0}$ and $z_{1}$. Thus,

$\displaystyle\mathrm{E}(H(x,z))$
$\displaystyle=\mathrm{E}(H_{R}(x,z))+\mathrm{E}(H_{R^{c}}(x,z))$
$\displaystyle=\ell+\left(\frac{1}{2}-\frac{\ell}{k}\right)H(x,y)+\ell+\left(\frac{1}{2}-\frac{\ell}{n-k}\right)H(x,y)$
$\displaystyle=2\ell+\left(1-\frac{\ell}{k}-\frac{\ell}{n-k}\right)H(x,y)$
$\displaystyle=2\ell+\left(1-\frac{\ell n}{k(n-k)}\right)H(x,y).\qed$

For further steps we need the following lemma from [12] to describe the
expected change of $S(P_{t})$ for a fixed offspring $y^{\prime}$. This result
works on all fitness functions.

######  Lemma 3.2 ([12], Lemma 3.1).

Consider a population $P_{t}=\\{x_{1},\dots,x_{\mu}\\}$ and a search point
$y^{\prime}\in\\{0,1\\}^{n}$. Let
$P_{t+1}\coloneq(P_{t}\cup\\{y^{\prime}\\})\setminus\\{x_{d}\\}$ for a uniform
random $d\in[\mu]$. Then

$\mathrm{E}(S(P_{t+1})\mid
S(P_{t}),y^{\prime})=\left(1-\tfrac{2}{\mu}\right)S(P_{t})+\tfrac{2(\mu-1)}{\mu}S_{P_{t}}(y^{\prime}).$

Now we combine Lemma 3.1 with Lemma 3.2 to describe the expected change of
$S(P_{t})$ if $y^{\prime}$ arises from another $y\in P_{t}$ by a mutation
operator which flips $\ell$ ones and zeros chosen uniformly at random and
every $x\in P_{t}$ is in plateau.

######  Lemma 3.3.

Let $P_{t}\subseteq\textsc{plateau}$ be a population of size $\mu$. Let $y\in
P_{t}$ be fixed and suppose that $y^{\prime}$ results from $y$ by a mutation
operator which flips $\ell$ ones and $\ell$ zeros chosen uniformly at random.
Let $P_{t+1}=(P_{t}\cup\\{y^{\prime}\\})\setminus\\{x_{d}\\}$ for a uniform
random $d\in[\mu]$. Then

$\displaystyle\mathrm{E}(S(P_{t+1})\mid
S(P_{t}))=\left(1-\tfrac{2}{\mu}\right)S(P_{t})+4\ell(\mu-1)+\tfrac{2(\mu-1)}{\mu}\Big{(}1-\tfrac{\ell
n}{k(n-k)}\Big{)}S_{P_{t}}(y).$

###### Proof.

For $z\in P_{t}$ we have
$S(z):=S_{P_{t}}(z)=\sum\nolimits_{i=1}^{\mu}H(x_{i},z)$. By Lemma 3.2 and the
law of total probability we obtain

$\mathrm{E}(S(P_{t+1})\mid
S(P_{t}))=\left(1-\frac{2}{\mu}\right)S(P_{t})+\frac{2(\mu-1)}{\mu}\mathrm{E}(S(y^{\prime})).$
(5)

By Lemma 3.1 we obtain for all $i\in[\mu]$

$\mathrm{E}(H(x_{i},y^{\prime}))=2\ell+\left(1-\frac{\ell}{k}-\frac{\ell}{n-k}\right)H(x_{i},y).$

Using $\frac{\ell}{k}+\frac{\ell}{n-k}=\frac{\ell n}{k(n-k)}$ and linearity of
expectation,

$\mathrm{E}(S(y^{\prime}))=\sum\nolimits_{i=1}^{\mu}\mathrm{E}(H(x_{i},y^{\prime}))=2\ell\mu+\left(1-\frac{\ell
n}{k(n-k)}\right)S(y)$

and plugging this into (5) yields the claim. ∎

Remarkably, the right-hand side only depends on $S_{P_{t}}(y)$, not on $y$
itself. This means that all $y$ with the same value of $S_{P_{t}}(y)$ yield
the same dynamics. The following corollary describes how the diversity evolves
in the case of a $(\mu+1)$ EA with a mutation operator which flips $\ell$ ones
and zeros chosen uniformly at random. This result transfers straightforwardly
to unbiased mutation operators if one knows the probability $p_{\ell}$ to flip
$\ell$ ones and $\ell$ zeros.

######  Corollary 3.4.

Let $\ell\in\\{0,\ldots,q\\}$ (where $q=\min(k,n-k)$). Consider the $(\mu+1)$
EA (see Algorithm 1) on $\textsc{Jump}_{k}$ with a mutation operator which
flips $\ell$ ones and $\ell$ zeros chosen uniformly at random. Suppose its
current population is $P_{t}\subseteq\textsc{plateau}$. Then

$\displaystyle\mathrm{E}(S(P_{t+1})\mid
S(P_{t}))=\left(1-\frac{2}{\mu^{2}}-\frac{2(\mu-1)\ell
n}{\mu^{2}k(n-k)}\right)S(P_{t})+4\ell(\mu-1).$

###### Proof.

By Lemma 3.3 and the law of total probability we have

$\displaystyle\mathrm{E}(S(P_{t+1})\mid S(P_{t}))$
$\displaystyle=\left(1-\tfrac{2}{\mu}\right)S(P_{t})+4\ell(\mu-1)+\tfrac{2(\mu-1)}{\mu}\Big{(}1-\tfrac{\ell
n}{k(n-k)}\Big{)}\mathrm{E}(S(y))$

where $y$ denotes the parent chosen uniformly at random. With

$\mathrm{E}(S(y))=\frac{1}{\mu}\sum\nolimits_{i=1}^{\mu}\sum\nolimits_{j=1}^{\mu}H(x_{i},x_{j})=S(P_{t})/\mu$

we obtain the result. ∎

Now we extend our analysis to arbitrary unbiased mutation operators.

######  Corollary 3.5.

Consider a $(\mu+1)$ EA (see Algorithm 1) on $\textsc{Jump}_{k}^{\prime}$ with
a current population $P_{t}\subseteq\textsc{plateau}$ and an unbiased mutation
operator $\mathrm{mut}$. Then

$\displaystyle\mathrm{E}(S(P_{t+1})\mid
S(P_{t}))=S(P_{t})-\sum\nolimits_{\ell=0}^{q}p_{\ell}\left(\frac{2}{\mu^{2}}+\frac{2(\mu-1)\ell
n}{\mu^{2}k(n-k)}\right)S(P_{t})+4(\mu-1)\sum\nolimits_{\ell=0}^{q}\ell
p_{\ell}$

where $p_{\ell}$ denotes the probability that $\mathrm{mut}$ flips $\ell$ ones
and $\ell$ zeros where $\ell\in\\{0,\ldots,q\\}$.

###### Proof.

For $\ell\in\\{0,\ldots,q\\}$ denote by $A_{\ell}$ the event that $\ell$ zeros
and $\ell$ ones are flipped. Since $\mathrm{mut}$ is unbiased, it flips $\ell$
ones and $\ell$ zeros chosen uniformly at random if $A_{\ell}$ occurs. Since
every individual $x\in P_{t}$ is in plateau (i.e. has $k$ zeros and $n-k$
ones), we see that the outcome $y$ is in plateau if and only if one of the
events $A_{0},A_{1},\ldots,A_{q}$ occurs. Let $B$ be the event that $y$ has a
worse fitness than every $x\in P_{t}$, i.e. $y$ is not in plateau. Then
$\mathrm{Pr}(B)+\sum\nolimits_{\ell=0}^{q}p_{\ell}=1$ and by the law of total
probability

$\displaystyle\mathrm{E}(S(P_{t+1})\mid S(P_{t}))=\mathrm{E}(S(P_{t+1})\mid
S(P_{t}),B)\cdot\mathrm{Pr}(B)+\sum\nolimits_{\ell=0}^{q}\mathrm{E}(S(P_{t+1}\mid
S(P_{t}),A_{\ell})\cdot p_{\ell}.$

If $B$ occurs, $S(P_{t})$ does not change, i.e. $\mathrm{E}(S(P_{t+1})\mid
S(P_{t}),B)=S(P_{t})$. Since

$\displaystyle\mathrm{E}(S(P_{t+1})\mid
S(P_{t}),A_{\ell})=\left(1-\frac{2}{\mu^{2}}-\frac{2(\mu-1)\ell
n}{\mu^{2}k(n-k)}\right)S(P_{t})+4\ell(\mu-1)$

by Corollary 3.4, we obtain the result. ∎

As for flat fitness landscapes in [12] (i.e. the fitness function is constant
over the whole search space), Corollary 3.5 shows that there is an equilibrium
state in plateau. We define

$\displaystyle\beta:=4(\mu-1)\sum\nolimits_{\ell=0}^{q}\ell p_{\ell}\text{ \
and \
}\gamma:=\sum\nolimits_{\ell=0}^{q}p_{\ell}\left(\frac{2}{\mu^{2}}+\frac{2(\mu-1)\ell
n}{\mu^{2}k(n-k)}\right).$ (6)

Then

$\displaystyle\mathrm{E}(S(P_{t+1})\mid S(P_{t}))=(1-\gamma)S(P_{t})+\beta.$
(7)

As in [12] this condition is a negative multiplicative drift with an additive
disturbance (this terminology stems from [6]). An equilibrium state for
$S(P_{t})$ with zero drift is attained for

$\displaystyle S_{0}:=\frac{\beta}{\gamma}$
$\displaystyle=\frac{4(\mu-1)\sum\nolimits_{\ell=0}^{q}\ell
p_{\ell}}{\frac{2}{\mu^{2}}\sum\nolimits_{\ell=0}^{q}p_{\ell}+\frac{2(\mu-1)n}{\mu^{2}k(n-k)}\sum\nolimits_{\ell=0}^{q}\ell
p_{\ell}}=\frac{2(\mu-1)\mu^{2}}{\frac{\sum\nolimits_{\ell=0}^{q}p_{\ell}}{\sum\nolimits_{\ell=0}^{q}\ell
p_{\ell}}+\frac{(\mu-1)n}{k(n-k)}}$ (8)

if $(p_{1},\ldots,p_{q})\neq 0$ and $S_{0}=S(P_{0})$ otherwise. The major
difference to [12] is that this equilibrium depends not only on the number of
bits flipped in expectation, but also on the probabilities $p_{\ell}$ to flip
exactly $\ell$ ones and $\ell$ zeros. For random local search we obtain
$(p_{1},\ldots,p_{q})=(1,0,\ldots,0)$ and for bitwise mutation with mutation
probability $\chi\in\\{1,\ldots,n\\}$

$\displaystyle p_{\ell}$
$\displaystyle=\binom{k}{\ell}\cdot\binom{n-k}{\ell}\cdot\left(\frac{\chi}{n}\right)^{2\ell}\cdot\left(1-\frac{\chi}{n}\right)^{n-2\ell}.$
(9)

The following lemma gives the equilibrium state for standard bit mutation with
mutation probability $\chi/n$ if $\chi\in\Theta(1)$. Recall that
$q=\min(k,n-k)$.

######  Lemma 3.6.

Consider standard bit mutation with a mutation probability $\chi/n$ with
$\chi\in O(1)$. Then $\sum\nolimits_{\ell=0}^{q}p_{\ell}=e^{-\chi}(1+\nu_{1})$
and $\sum\nolimits_{\ell=0}^{q}\ell p_{\ell}=k(n-k)(\chi/n)^{2}\cdot
e^{-\chi}(1+\nu_{2})$ for $|\nu_{1}|,|\nu_{2}|\in O(q/n)$ and hence

$\frac{\sum\nolimits_{\ell=0}^{q}p_{\ell}}{\sum\nolimits_{\ell=0}^{q}\ell
p_{\ell}}=\frac{n^{2}}{k\chi^{2}(n-k)}(1+\xi)$

for $|\xi|\in O(q/n)$.

###### Proof.

We have

$\displaystyle\sum\nolimits_{\ell=0}^{q}\ell
p_{\ell}=\frac{\chi^{2}}{n^{2}}\Big{(}1-\frac{\chi}{n}\Big{)}^{n-2}\sum\nolimits_{\ell=1}^{q}\Big{(}\ell\binom{k}{\ell}\binom{n-k}{\ell}\cdot\Big{(}\frac{\chi}{n-\chi}\Big{)}^{2\ell-2}\Big{)}$
$\displaystyle=\frac{k(n-k)\chi^{2}}{n^{2}}\Big{(}1-\frac{\chi}{n}\Big{)}^{n-2}\sum\nolimits_{\ell=1}^{q}\Big{(}\frac{\chi^{2\ell-2}\prod_{j=1}^{\ell-1}(k-j)(n-k-j)}{(n-\chi)^{2\ell-2}(\ell-1)!\ell!}\Big{)}$
$\displaystyle=\frac{k(n-k)\chi^{2}}{n^{2}}\Big{(}1-\frac{\chi}{n}\Big{)}^{n-2}\Big{(}1+\frac{q}{n}\sum\nolimits_{\ell=2}^{q}\frac{n\chi^{2\ell-2}\prod_{j=1}^{\ell-1}(k-j)(n-k-j)}{q(n-\chi)^{2\ell-2}(\ell-1)!\ell!}\Big{)}.$

We may bound $(1-\chi/n)^{n-2}=e^{-\chi}(1+O(\chi/n))$ by [5, Corollary 1.4.6]
and swallow the latter factor in $\nu_{2}$. To bound the remaining terms, we
use

$\sum\nolimits_{\ell=2}^{q}\frac{\chi^{2\ell-2}}{(\ell-1)!\ell!}=\sum\nolimits_{\ell=1}^{q-1}\frac{\chi^{2\ell}}{\ell!(\ell+1)!}\leq\sum\nolimits_{\ell=0}^{q-1}\frac{\chi^{2\ell}}{\ell!}\leq
e^{\chi^{2}}\in O(1)$

and for every $\ell\in\\{2,\dots,q\\}$

$\frac{n\prod_{j=1}^{\ell-1}(k-j)(n-k-j)}{q(n-\chi)^{2\ell-2}}\leq\frac{n(k-1)^{\ell-1}(n-k-1)^{\ell-1}}{q(n-\chi)^{2\ell-2}}.$

Since $(k-1)(n-k-1)=(q-1)(n-q-1)\leq qn$, we may bound the latter as

$\displaystyle\leq\frac{n^{2}q(k-1)^{\ell-2}(n-k-1)^{\ell-2}}{q(n-\chi)^{2\ell-2}}\leq\Big{(}\frac{n}{n-\chi}\Big{)}^{2\ell-2}$
$\displaystyle=\Big{(}1+\frac{\chi}{n-\chi}\Big{)}^{2\ell}\leq
e^{\frac{\chi}{n-\chi}\cdot 2\ell}\leq e^{\frac{\chi}{n-\chi}\cdot 2k}\in
O(1).$

In an analogous way we obtain the result for
$\sum\nolimits_{\ell=0}^{q}p_{\ell}$. We have

$\displaystyle\sum\nolimits_{\ell=0}^{q}p_{\ell}$
$\displaystyle=\left(1-\frac{\chi}{n}\right)^{n}\sum\nolimits_{\ell=0}^{q}\binom{k}{\ell}\cdot\binom{n-k}{\ell}\cdot\left(\frac{\chi}{n-\chi}\right)^{2\ell}$
$\displaystyle=\Big{(}1-\frac{\chi}{n}\Big{)}^{n}\sum\nolimits_{\ell=0}^{q}\Big{(}\frac{\chi^{2\ell}\prod_{j=0}^{\ell-1}(k-j)(n-k-j)}{(n-\chi)^{2\ell}\ell!\ell!}\Big{)}.$
$\displaystyle=\Big{(}1-\frac{\chi}{n}\Big{)}^{n}\left(1+\frac{q}{n}\sum\nolimits_{\ell=1}^{q}\Big{(}\frac{n\chi^{2\ell}\prod_{j=0}^{\ell-1}(k-j)(n-k-j)}{q(n-\chi)^{2\ell}\ell!\ell!}\Big{)}\right).$

As before, we may estimate $(1-\chi/n)^{n}=e^{-\chi}(1-O(\chi/n))$. Moreover,

$\sum\nolimits_{\ell=1}^{q}\frac{\chi^{2\ell}}{\ell!\ell!}\leq\sum\nolimits_{\ell=1}^{q}\frac{\chi^{2\ell}}{\ell!}\leq
e^{\chi^{2}}\in O(1)$

and for every $\ell\in\\{1\ldots,q\\}$

$\displaystyle\frac{n\prod_{j=0}^{\ell-1}(k-j)(n-k-j)}{q(n-\chi)^{2\ell}}$
$\displaystyle=\frac{nq(n-q)\prod_{j=1}^{\ell-1}(k-j)(n-k-j)}{q(n-\chi)^{2\ell}}$
$\displaystyle\leq\frac{n^{2\ell}}{(n-\chi)^{2\ell}}\leq
e^{\frac{\chi}{n-\chi}\cdot 2k}\in O(1).\qed$

Now we can state the equilibrium for standard bit mutation. Plugging the
simplifications from Lemma 3.6 into (8),

$\displaystyle S_{0}=\;$
$\displaystyle\frac{2(\mu-1)\mu^{2}}{\frac{n^{2}}{k\chi^{2}(n-k)}(1+\xi)+\frac{(\mu-1)n}{k(n-k)}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
Thus, we get the following.

######  Corollary 3.7.

For the ($\mu$+1) EA on Jump ${}_{k}^{\prime}$ with standard bit mutation and
mutation rate $\chi/n$ with $\chi\in O(1)$, starting with an arbitrary
population $P_{t}\subseteq\textsc{plateau}$, the equilibrium state for
population diversity is

$S_{0}\coloneqq\frac{\beta}{\gamma}=\frac{2\mu^{2}\frac{k(n-k)}{n}}{\frac{n}{(\mu-1)\chi^{2}}(1+\xi)+1}.$

To obtain the average Hamming distance in the population, we need to divide
$S_{0}$ by $\mu^{2}$. If $k=o(n)$ the numerator in $S_{0}/\mu^{2}$ is
$2k-o(1)$ and if $\mu\chi^{2}=\omega(n)$, the denominator is $1+o(1)$. Then
the average Hamming distance is $2k-o(1)$, that is, converging to its maximum
value $2k$.

##  4 Analysing Population Diversity on plateau for the ($\mu$+1) GA

Now we turn to the $(\mu+1)$ GA that performs crossover with probability
$p_{c}$ and for $\lambda$ crossover offspring, as described in Algorithm 2.

We will make use of the following notion of _diversity-neutral_ crossover as
defined in [12]. In the context of [12] (that is, on flat fitness landscapes)
a diversity-neutral crossover guaranteed that the equilibrium of a mutation-
only EA was not affected when introducing such a crossover operator.

######  Definition 4.1 ([12]).

We call a crossover operator $\mathrm{c}$ _diversity-neutral_ if it has the
following property. For all $x_{1},x_{2},z\in\\{0,1\\}^{n}$,

$\mathrm{E}(H(\mathrm{c}(x_{1},x_{2}),z)+H(\mathrm{c}(x_{2},x_{1}),z))=H(x_{1},z)+H(x_{2},z).$
(10)

Many well-known operators were shown to be diversity-neutral in [12],
including uniform crossover, $k$-point crossover and balanced uniform
crossover [8]. The latter copies bit values on which both parents agree. If
the parents differ in $k$ positions, it then chooses values for these bits
uniformly at random from all sub-strings that have exactly $\lfloor
k/2\rfloor$ ones at these positions. Hence, it guarantees that amongst those
$k$ positions there will be exactly $\lfloor{k/2}\rfloor$ ones. Balanced
uniform crossover will appear as a vehicle in some proofs.

We start our analysis with the following statement from [12], which holds for
arbitrary diversity-neutral crossover operators. The result [12, Theorem 5.2]
additionally allowed for an arbitrary mutation operator, but we use it only
for the trivial “mutation” operator which flips $\chi=0$ bits. It considers a
population $Q_{t}$ that results from creating an offspring and always
accepting, hence simulating one step on a flat landscape. Note that $Q_{t}$ is
in general not the same as $P_{t+1}$; they are equal only in steps in which
the offspring is accepted.

######  Lemma 4.2.

([12, Theorem 5.2] for $\chi=0$.) For every population $P_{t}$ of size $\mu$
the following holds. Suppose that $y\in\\{0,1\\}^{n}$ is the outcome of a
diversity-neutral crossover $c$ on two parents chosen uniformly at random from
$P_{t}$. Let $Q_{t}:=(P_{t}\cup\\{y\\})\setminus\\{x_{d}\\}$ for a uniform
random $d\in[\mu]$. Then

$\mathrm{E}(S(Q_{t})\mid
S(P_{t}))=\big{(}1-\tfrac{2}{\mu^{2}}\big{)}S(P_{t}).$

As preparation, we give an easy computational lemma. Recall that
$S_{i}(P)=\sum\nolimits_{x\in P}\sum\nolimits_{x^{\prime}\in
P}H_{i}(x,x^{\prime})$, where $H_{i}(x,x^{\prime})$ is the indicator for the
event $x_{i}\neq x_{i}^{\prime}$.

######  Lemma 4.3.

Let $i\in[n]$, let $P_{t}\subseteq\textsc{plateau}$ be a population of size
$\mu$ and let $y,z\in\\{0,1\\}^{n}$ with $y_{i}\neq z_{i}$. Let
$P_{1}:=(P_{t}\cup\\{y\\})\setminus\\{x_{d}\\}$ and
$P_{2}:=(P_{t}\cup\\{z\\})\setminus\\{x_{d}\\}$ where $d\in[\mu]$ is chosen
uniformly at random. Let $m$ be the number of bits with value $z_{i}$ at
position $i$ in $P_{t}$. Then

$\displaystyle\mathrm{E}(S_{i}(P_{2}))=\mathrm{E}(S_{i}(P_{1}))+2\mu-4m(1-1/\mu)-2\geq\mathrm{E}(S_{i}(P_{1}))-2(\mu-1).$

###### Proof.

The quantity of $z_{i}$ bits at position $i$ in $P_{t}\cup\\{z\\}$ is by one
larger than in $P_{t}\cup\\{y\\}$. Since $S_{i}(P_{t})=2m(\mu-m)$, we obtain
$S_{i}(P_{1})=2(m-1)(\mu-m+1)$ and $S_{i}(P_{2})=2m(\mu-m)$ if
$(x_{d})_{i}=z_{i}$ (which happens with probability $m/\mu$), and
$S_{i}(P_{1})=2m(\mu-m)$ and $S_{i}(P_{2})=2(m+1)(\mu-m-1)$ if
$(x_{d})_{i}=y_{i}\neq z_{i}$ (which happens with probability $(\mu-m)/\mu$).
This yields

$\mathrm{E}(S_{i}(P_{1}))=\frac{\mu-m}{\mu}2m(\mu-m)+\frac{m}{\mu}2(m-1)(\mu-m+1)$

and

$\mathrm{E}(S_{i}(P_{2}))=\frac{\mu-m}{\mu}2(m+1)(\mu-m-1)+\frac{m}{\mu}2m(\mu-m).$

Thus

$\displaystyle\mathrm{E}(S_{i}(P_{2}))-\mathrm{E}(S_{i}(P_{1}))$
$\displaystyle=\frac{\mu-m}{\mu}2(\mu-2m-1)+\frac{m}{\mu}2(\mu-2m+1)$
$\displaystyle=2\mu-4m+\frac{4m-2\mu}{\mu}$
$\displaystyle=2\mu-4m\left(1-\frac{1}{\mu}\right)-2\geq-2(\mu-1)$

using $m\leq\mu$ in the last step. ∎

In the next lemma we show that, conditional on being in plateau, the loss of
diversity is no larger than $(2/\mu^{2})S(P_{t})+9k(\mu-1)\chi/n$ compared to
balanced uniform crossover. This is the key step of our analysis.

######  Lemma 4.4.

For every pair of parents $x_{1},x_{2}\in P_{t}$ the following holds. Consider
a random offspring $y\in\\{0,1\\}^{n}$ resulting from uniform
crossover$(x_{1},x_{2})$. Let $z$ be a random search point created from $y$ by
standard bit mutation with mutation probability $\chi/n=\Theta(1/n)$. Let
$d\in[\mu]$ uniform random and let $V$ be the event $z\in\textsc{plateau}$.
Let $P_{t+1}:=(P_{t}\cup\\{z\\})\setminus\\{x_{d}\\}$. Let $y^{b}$ be the
random search point resulting from balanced uniform crossover$(x_{1},x_{2})$.
Then for $Q_{t}^{b}:=(P_{t}\cup\\{y^{b}\\})\setminus\\{x_{d}\\}$ and
sufficiently large $n$

$\displaystyle E(S(P_{t+1})\mid
V)\geq\mathrm{E}(S(Q_{t}^{b}))-\frac{9}{k(\mu-1)\chi}{n\mathrm{Pr}(V)}.$

###### Proof.

Call a position $i$ _disagreeing_ if $x_{1}$ and $x_{2}$ differ at $i$ (i.e.
$(x_{1})_{i}\neq(x_{2})_{i}$). Note that there are $H(x_{1},x_{2})\leq 2k$
disagreeing positions. For $\ell\in\\{-k,\ldots,k\\}$ denote by $A_{\ell}$ the
event that, in the substring $y^{\prime}$ of $y$ given by all disagreeing
positions, $\left|y^{\prime}\right|_{1}=\left|y^{\prime}\right|_{0}+\ell$.
Hence, $\ell$ indicates the surplus of ones generated by crossover. We
describe a way of generating a random crossover output $y$ under the condition
$A_{\ell}$. We first copy all bits that agree in $x_{1}$ and $x_{2}$ to $y$
and distribute $H(x_{1},x_{2})/2$ many ones and zeros uniformly at random
among the positions in which $x_{1}$ and $x_{2}$ disagree. That gives an
outcome $y^{b}$ of balanced uniform crossover. Then we flip $\ell$ zeros in
$y^{b}$ if $\ell\geq 0$ ($\ell$ ones if $\ell<0$), again chosen uniformly at
random among the disagreeing positions of $x_{1}$ and $x_{2}$. This yields a
uniform random offspring $y$ amongst all offspring with a surplus of $\ell$
ones. Let $Q_{t}:=(P_{t}\cup\\{y\\})\setminus\\{x_{d}\\}$ and
$Q_{t}^{b}:=(P_{t}\cup\\{y^{b}\\})\setminus\\{x_{d}\\}$.

######  Lemma 4.5.

We have that

$\displaystyle E(S(Q_{t})\mid A_{\ell})\geq E(S(Q_{t}^{b}))-2|{\ell}|(\mu-1).$
(11)

###### Proof.

Let $Y(\ell,y^{b})$ denote the set of bit strings obtainable from $y^{b}$ by
flipping $\ell$ zeros. For $y\in Y(\ell,y^{b})$ let
$\Gamma_{y}:=\\{i\in[n]\mid y_{i}\neq y_{i}^{b}\\}$. Then we obtain with Lemma
4.3 conditioning on the event that fixed $y^{b}$ and $y\in Y(\ell,y^{b})$ are
produced

$\displaystyle E(S(Q_{t}))$
$\displaystyle=\sum_{i\notin\Gamma_{y}}E(S_{i}(Q_{t}))+\sum_{i\in\Gamma_{y}}E(S_{i}(Q_{t}))$
$\displaystyle\geq\sum_{i\notin\Gamma_{y}}E(S_{i}(Q_{t}^{b}))+\sum_{i\in\Gamma_{y}}E(S_{i}(Q_{t}^{b}))-2|{\ell}|(\mu-1)$
$\displaystyle=E(S(Q_{t}^{b}))-2|{\ell}|(\mu-1).$

Hence, we obtain with the law of total probability by summing over all
possible $y_{b}$ and $y\in Y(\ell,y^{b})$

$\displaystyle E(S(Q_{t})\mid A_{\ell})$ $\displaystyle\geq
E(S(Q_{t}^{b}))-2|{\ell}|(\mu-1)\qed.$

For $i\in\\{0,\ldots,2k\\}$ and $j\in\\{0,\ldots,n-2k\\}$ let $B_{ij}$ be the
event of flipping $i$ zeros and $j$ ones in $y$ with the standard mutation
operator. Let $q_{i,j,\ell}:=\mathrm{Pr}(B_{ij}\mid A_{\ell})$. Then for
$i\in[k-\ell]$ and $j\in[n-k+\ell]$

$q_{i,j,\ell}=\binom{k-\ell}{i}\binom{n-k+\ell}{j}\left(\frac{\chi}{n}\right)^{i+j}\left(1-\frac{\chi}{n}\right)^{n-i-j}$

and $q_{i,j,\ell}=0$ otherwise. Note that $z$ has $k$ zeros (i.e. is in
plateau) if and only if $A_{\ell}$ and then $B_{i,i+\ell}$ occurs for some
$i\in\\{0,\ldots,k-\ell\\}$ if $\ell\geq 0$, or $A_{\ell}$ and then
$B_{i-\ell,i}$ occurs for some $i\in\\{0,\ldots,k-\ell\\}$ if $\ell<0$. If
$A_{\ell}$ occurred, we have for $0\leq i\leq k-\ell-1$ and $0\leq j\leq
n-k+\ell-1$

$\displaystyle q_{i+1,j+1,\ell}$
$\displaystyle=\binom{k-\ell}{i+1}\binom{n-k+\ell}{j+1}\left(\frac{\chi}{n}\right)^{i+j+2}\left(1-\frac{\chi}{n}\right)^{n-i-j-2}$
$\displaystyle=\left(\frac{\chi}{n-\chi}\right)^{2}\frac{k-\ell-i}{i+1}\cdot\frac{n-k+\ell-j}{j+1}\cdot
q_{i,j,\ell}$ $\displaystyle=O(k/n)\cdot q_{i,j,\ell}$ (12)

due to $\binom{r}{s}=\frac{r-s+1}{s}\binom{r}{s-1}$ for $r,s\in\mathbb{N}$
with $r\geq s\geq 1$.

We continue the proof by estimating $\mathrm{E}(S(P_{t+1})\mid
A_{\ell},B_{i,i+\ell})$ and $\mathrm{E}(S(P_{t+1})\mid
A_{-\ell},B_{i+\ell,i})$ for $\ell\geq 0$, encapsulated in the following
nested lemma.

######  Lemma 4.6.

For $\ell\geq 0$ in the context of Lemma 4.4,

$\displaystyle\mathrm{E}(S(P_{t+1})\mid
A_{\ell},B_{i,i+\ell})\geq\mathrm{E}(S(Q^{b}_{t}))-(i+\ell)\tfrac{4k\mu}{n-2k}$
(13)

and

$\displaystyle\mathrm{E}(S(P_{t+1})\mid
A_{-\ell},B_{i-\ell,i})\geq\mathrm{E}(S(Q^{b}_{t}))-4\ell(\mu-1)-\tfrac{4ki\mu}{n-2k}.$
(14)

###### Proof.

Let $y$ be a possible outcome of crossover on $x_{1},x_{2}$ with a surplus of
$\ell$ ones. We will use that

$\displaystyle\mathrm{E}(S(P_{t+1})\mid y,B_{i,i+\ell})$
$\displaystyle=\mathrm{E}(S(P_{t}\setminus\\{x_{d}\\})\mid
y,B_{i,i+\ell})+2E(S_{P_{t}\setminus\\{x_{d}\\}}(z)\mid y,B_{i,i+\ell})$
$\displaystyle=\mathrm{E}(S(Q_{t})\mid
y)-2\mathrm{E}(S_{P_{t}\setminus\\{x_{d}\\}}(y))+2\mathrm{E}(S_{P_{t}\setminus\\{x_{d}\\}}(z)\mid
y,B_{i,i+\ell}).$

So we need to estimate the difference
$\Delta:=S_{P_{t}\setminus\\{x_{d}\\}}(z)-S_{P_{t}\setminus\\{x_{d}\\}}(y)$
when we obtain $z$ from $y$ by flipping $i$ zeros and $i+\ell$ ones. Flipping
a zero into a one can contribute at most $\mu-1$ to $\Delta$. To estimate the
contribution of flipping a one into zero, consider a uniformly random one in
$y$ and let $N_{0}$ be the number of zeros in $P_{t}\setminus\\{x_{d}\\}$ at
this position. Then flipping this position from one to zero in $y$ contributes
$\mu-1-2N_{0}$ to $\Delta$, because each of the $N_{0}$ zeros contributes $-1$
and each of the $\mu-1-N_{0}$ ones contributes $+1$. Note that the total
number of zeros in $P_{t}\setminus\\{x_{d}\\}$ over _all_ positions is
$(\mu-1)k$. Hence, if we restrict ourselves to the $|y|_{1}$ positions where
$y$ is one, the total number of zeros in $P_{t}$ is still at most $(\mu-1)k$
and hence $\mathrm{E}(N_{0})\leq k\mu/|y|_{1}\leq k\mu/(n-2k)$. By summing up
all positions, we obtain with the law of total expectation

$\displaystyle\mathrm{E}(S(P_{t+1})\mid y,B_{i,i+\ell})$
$\displaystyle=\mathrm{E}(S(Q_{t})\mid y)+2E(\Delta\mid y,B_{i,i+\ell})$
$\displaystyle\geq\mathrm{E}(S(Q_{t})\mid
y)-2i(\mu-1)+2(i+\ell)\mathrm{E}(\mu-1-2N_{0})$
$\displaystyle\geq\mathrm{E}(S(Q_{t}))\mid
y)-2i(\mu-1)+2(i+\ell)\left(\mu-1-\frac{2k\mu}{n-2k}\right).$

Since $\mathrm{Pr}(B_{i,i+\ell}\mid y)=\mathrm{Pr}(B_{i,i+\ell}\mid A_{\ell})$
(for every possible outcome $y$ with
$\left|y\right|_{1}=\left|y\right|_{0}+\ell$ on disagreeing positions of
$x_{1},x_{2}$ the event $B_{i,i+\ell}$ occurs with the same probability) we
obtain by the law of total probability and Inequality (11)

$\displaystyle\mathrm{E}(S(P_{t+1})\mid A_{\ell},B_{i,i+\ell})$
$\displaystyle\geq\mathrm{E}(S(Q_{t})\mid
A_{\ell})-2i(\mu-1)+2(i+\ell)\left(\mu-1-\frac{2k\mu}{n-2k}\right)$
$\displaystyle\geq\mathrm{E}(S(Q^{b}_{t}))-2(i+\ell)(\mu-1)+2(i+\ell)\left(\mu-1-\frac{2k\mu}{n-2k}\right)$
$\displaystyle=\mathrm{E}(S(Q^{b}_{t}))-(i+\ell)\left(\frac{4k\mu}{n-2k}\right).$
(15)

Now we estimate $\mathrm{E}(S(P_{t+1})\mid A_{-\ell},B_{i+\ell,i})$ for
$\ell>0$. Let $y$ be a possible outcome of crossover with
$\left|y^{\prime}\right|_{1}=\left|y^{\prime}\right|_{0}-\ell$. By an
analogous argument as above flipping $i+\ell$ zero bits decreases the
diversity by $2(i+\ell)(\mu-1)$ in $S(P_{t+1})$ compared to $S(Q_{t}\mid y)$
and flipping $i$ one-bits increases the diversity by
$2i(\mu-1-\frac{2k\mu}{n-2k})$ in expectation. Hence,

$\displaystyle\mathrm{E}(S(P_{t+1})\mid y,B_{i+\ell,i})$
$\displaystyle\geq\mathrm{E}(S(Q_{t})\mid
y)-2(i+\ell)(\mu-1)+2i\left(\mu-1-\frac{2k\mu}{n-2k}\right)$
$\displaystyle=\mathrm{E}(S(Q_{t})\mid y)-2\ell(\mu-1)-\frac{4ki\mu}{n-2k},$

and similar as above

$\displaystyle\mathrm{E}(S(P_{t+1})\mid A_{-\ell},B_{i-\ell,i})$
$\displaystyle\geq\mathrm{E}(S(Q_{t})\mid
A_{-\ell})-2\ell(\mu-1)-\frac{4ki\mu}{n-2k}$
$\displaystyle\geq\mathrm{E}(S(Q^{b}_{t}))-4\ell(\mu-1)-\frac{4ki\mu}{n-2k}.$
(16)

∎

Now we compute the total decrease in $\mathrm{E}(S(P_{t+1}))$ compared to
$S(P_{t})$. Denote $\rho_{\ell}:=\mathrm{Pr}(A_{\ell})$. By the law of total
expectation and using (13) (for $\ell\geq 0$) and (14) (for $\ell<0$), we have

$\displaystyle\mathrm{E}(S(P_{t+1})\mid V)\mathrm{Pr}(V)$
$\displaystyle=\sum\nolimits_{\ell=0}^{k}\sum\nolimits_{i=0}^{k-\ell}\mathrm{E}(S(P_{t+1})\mid
A_{\ell},B_{i,i+\ell})\rho_{\ell}q_{i,i+\ell,\ell}$
$\displaystyle+\sum\nolimits_{\ell=1}^{k}\sum\nolimits_{i=0}^{k+\ell}\mathrm{E}(S(P_{t+1})\mid
A_{-\ell},B_{i+\ell,i})\rho_{-\ell}q_{i+\ell,i,-\ell}$
$\displaystyle\geq\mathrm{E}(S(Q^{b}_{t}))\mathrm{Pr}(V)-T_{1}-T_{2},$ (17)

where

$\displaystyle
T_{1}:=\frac{4k\mu}{n-2k}\sum\nolimits_{\ell=0}^{k}\sum\nolimits_{i=0}^{k-\ell}(i+\ell)\rho_{\ell}q_{i,i+\ell,\ell}\text{
and }$ $\displaystyle
T_{2}:=\sum\nolimits_{\ell=1}^{k}\sum\nolimits_{i=0}^{k+\ell}\left(2\ell(\mu-1)+\frac{4ki\mu}{n-2k}\right)\rho_{-\ell}q_{i+\ell,i,-\ell}.$

######  Lemma 4.7.

We have that $T_{1}\leq 4k\mu\chi(1+O(k/n))/n$ and
$T_{2}\leq(4k(\mu-1))\chi(1+O(k/n))/n$.

###### Proof.

To bound $T_{1}$ and $T_{2}$ we use $\rho_{\ell}\leq 1$ and
$q_{0,\ell,\ell}\leq\binom{n}{\ell}(\chi/n)^{\ell}(1-\chi/n)^{n-\ell}$.
Moreover, note that $\sum\nolimits_{\ell\geq 0}q_{0,\ell,\ell}\leq 1$ and
$\sum\nolimits_{\ell\geq 0}\ell q_{0,\ell,\ell}\leq\chi$. Hence, with Equation
(4),

$\displaystyle T_{1}$
$\displaystyle\leq\frac{4k\mu}{n-2k}\left(\sum\nolimits_{\ell=0}^{k}\ell
q_{0,\ell,\ell}+\sum\nolimits_{\ell=0}^{k}\sum\nolimits_{i=1}^{k-\ell}(i+\ell)q_{i,\ell+i,\ell}\right)$
$\displaystyle\leq\frac{4k\mu}{n-2k}\left(\sum\nolimits_{\ell=0}^{k}\ell
q_{0,\ell,\ell}+\sum\nolimits_{\ell=0}^{k}\sum\nolimits_{i=1}^{k}(i+\ell)q_{0,\ell,\ell}O(k^{i}/n^{i})\right)$
$\displaystyle=\frac{4k\mu}{n-2k}\left(\chi+\sum\nolimits_{i=1}^{k}(i+\chi)O(k^{i}/n^{i})\right)$
$\displaystyle=\frac{4k\mu\chi}{n-2k}\left(1+\sum\nolimits_{i=1}^{k}(1+i/\chi)O(k^{i}/n^{i})\right)$
$\displaystyle=\frac{4k\mu\chi}{n}(1+O(k/n)).$

Note also that
$q_{\ell,0,-\ell}\leq\binom{k}{\ell}(\chi/n)^{\ell}(1-\chi/n)^{k-\ell}$ which
implies $\sum\nolimits_{\ell\geq 0}q_{\ell,0,-\ell}\leq 1$ and
$\sum\nolimits_{\ell\geq 0}\ell q_{\ell,0,-\ell}\leq k\chi/n$ and thus again
with Inequality (4)

$\displaystyle T_{2}$
$\displaystyle\leq\sum\nolimits_{\ell=1}^{k}\sum\nolimits_{i=0}^{k+\ell}\left(4\ell(\mu-1)+\frac{4ki\mu}{n-2k}\right)q_{i+\ell,i,-\ell}$
$\displaystyle\leq\sum\nolimits_{\ell=1}^{k}\sum\nolimits_{i=0}^{2k}\left(4\ell(\mu-1)+\frac{4ki\mu}{n-2k}\right)q_{i+\ell,i,-\ell}$
$\displaystyle\leq\sum\nolimits_{\ell=1}^{k}4\ell(\mu-1)q_{\ell,0,-\ell}+\sum\nolimits_{\ell=1}^{k}\sum\nolimits_{i=1}^{2k}\left(4\ell(\mu-1)+\frac{4ki\mu}{n-2k}\right)q_{i+\ell,i,-\ell}$
$\displaystyle\leq
4k\chi(\mu-1)/n+\sum\nolimits_{\ell=1}^{k}\sum\nolimits_{i=1}^{2k}\left(4\ell(\mu-1)+\frac{4ki\mu}{n-2k}\right)q_{\ell,0,-\ell}O(k^{i}/n^{i})$
$\displaystyle\leq
4k\chi(\mu-1)/n+\sum\nolimits_{i=1}^{2k}\left(4k\chi(\mu-1)/n+\frac{4ki\mu}{n-2k}\right)O(k^{i}/n^{i})$
$\displaystyle\leq
4k\chi(\mu-1)/n\left(1+\sum\nolimits_{i=1}^{2k}\left(1+\frac{i\mu}{\chi(\mu-1)(1-2k/n)}\right)O(k^{i}/n^{i})\right)$
$\displaystyle\leq\frac{4k(\mu-1)\chi}{n}(1+O(k/n))$

since the latter sum converges owing to $k/n\leq 1/4$. ∎

Dividing (4) by $\mathrm{Pr}(V)$, plugging in the bound for $T_{1}$ and
$T_{2}$, and increasing the constant from $4$ to $4.5$ in $T_{1}$ and $T_{2}$
to swallow the $(1+O(k/n))$ and $(\mu/(\mu-1))$ factor in $T_{1}$ and the
$(1+O(k/n))$ factor in $T_{2}$ concludes the proof of Lemma 4.4. ∎

Now we turn to the ($\mu$+1) GA stated in Algorithm 2, mostly in the following
situation.

######  Situation 4.8.

Let $k\in o(n)$, $\lambda\geq 6\sqrt{k}e^{\chi}\ln(\mu)$, and
$\chi=\Theta(1)$. Consider a ($\mu$+1) GA with $\lambda$ competing crossover
offspring as in Algorithm 2, using standard bit mutation with mutation
probability $\chi/n$ and uniform crossover with crossover probability $p_{c}$
on $\textsc{Jump}_{k}^{\prime}$, and suppose the current population is
$P_{t}\subseteq\textsc{plateau}$.

######  Lemma 4.9.

In Situation 4.8, consider one generation of the ($\mu$+1) GA when crossover
occurs. Then

$\displaystyle
E(S(P_{t+1}))\geq\big{(}1-\tfrac{3}{\mu^{2}}\big{)}S(P_{t})-9k(\mu-1)\chi/n.$

###### Proof.

Let $x_{1},x_{2}$ be the two parents. By the law of total probability we
obtain

$\displaystyle\mathrm{E}(S(P_{t+1}))=\frac{1}{\mu^{2}}\sum\nolimits_{(x_{1},x_{2})\in
P_{t}^{2}}E(S(P_{t+1})\mid x_{1},x_{2}).$ (18)

Let $V$ be the event that a fixed offspring $z$ is in plateau conditioned on
the choice of the parents, and let $V_{\lambda}$ be the event that at least
one out of the $\lambda$ offspring is in plateau. Note that
$\mathrm{E}(S(P_{t+1})\mid x_{1},x_{2},V)=\mathrm{E}(S(P_{t+1})\mid
x_{1},x_{2},V_{\lambda})$. Then again with the law of total probability for
two parents $x_{1},x_{2}$ and Lemma 4.4

$\displaystyle\mathrm{E}(S(P_{t+1})\mid x_{1},x_{2})$
$\displaystyle\geq\mathrm{E}(S(P_{t+1})\mid
x_{1},x_{2},V_{\lambda})\Pr(V_{\lambda}\mid x_{1},x_{2})$
$\displaystyle\geq\mathrm{E}(S(Q_{t}^{b})\mid x_{1},x_{2})\Pr(V_{\lambda}\mid
x_{1},x_{2})-\tfrac{9k(\mu-1)\chi}{n},$

where $Q_{t}$ and $Q_{t}^{b}$ are defined as in Lemmas 4.2 and 4.4. Note that
the probability of $V$ is at least the probability that crossover generates an
offspring in plateau and mutation does not change it, hence
$\Pr(V)\geq\binom{2k}{k}2^{-2k}(1-\chi/n)^{n}\geq(1-\chi/n)^{n}/(2\sqrt{k})\geq
e^{-\chi}/(3\sqrt{k})$. So we obtain for $\lambda\geq
6\sqrt{k}e^{\chi}\ln(\mu)$ due to $1-x\leq e^{-x}$,

$\displaystyle\Pr(V_{\lambda}\mid x_{1},x_{2})$
$\displaystyle=1-\left(1-\mathrm{Pr}(V)\right)^{\lambda}\geq
1-\left(1-e^{-\chi}/(3\sqrt{k})\right)^{6\sqrt{k}e^{\chi}\ln(\mu)}$
$\displaystyle\geq 1-e^{-2\ln(\mu)}=1-1/\mu^{2}.$

Using once more the bound $\Pr(V)\geq e^{-\chi}/(3\sqrt{k})$, we obtain for
every $(x_{1},x_{2})\in P_{t}^{2}$

$\displaystyle\mathrm{E}(S(P_{t+1})\mid x_{1},x_{2})$
$\displaystyle\geq\big{(}1-\tfrac{1}{\mu^{2}}\big{)}\mathrm{E}(S(Q_{t}^{b})\mid
x_{1},x_{2})-\tfrac{9k(\mu-1)\chi}{n}.$ (19)

Since _balanced uniform crossover_ is diversity-neutral by [12, Theorem
6.5.5], we obtain with Lemma 4.2

$\displaystyle\frac{1}{\mu^{2}}\sum\nolimits_{(x_{1},x_{2})\in
P_{t}^{2}}\mathrm{E}(S(Q_{t}^{b})\mid
x_{1},x_{2})=\mathrm{E}(S(Q_{t}))=(1-\tfrac{2}{\mu^{2}})S(P_{t}).$ (20)

Plugging (19) and (20) into (18) and using
$(1-1/\mu^{2})(1-2/\mu^{2})\geq(1-3/\mu^{2})$ gives the lemma. ∎

We are able to derive a lower bound for $\mathrm{E}(S(P_{t+1})\mid S(P_{t}))$
for the ($\mu$+1) GA.

######  Corollary 4.10.

In Situation 4.8, let

$\displaystyle\alpha:=(1-p_{c})4(\mu-1)\sum\nolimits_{\ell=0}^{k}\ell
p_{\ell}-9p_{c}k(\mu-1)\chi/n$ (21)

and

$\displaystyle\delta:=\frac{1}{\mu^{2}}\left(3p_{c}+(2-2p_{c})\sum\nolimits_{\ell=0}^{k}p_{\ell}\left(1+\frac{(\mu-1)\ell
n}{k(n-k)}\right)\right)$ (22)

where $p_{\ell}$ denotes the probability that $\mathrm{mutation}$ flips $\ell$
ones and $\ell$ zeros. Then

$\displaystyle\mathrm{E}(S(P_{t+1})\mid
S(P_{t}))\geq(1-\delta)S(P_{t})+\alpha.$ (23)

###### Proof.

Denote by $A$ the event that crossover is executed in iteration $t+1$ in the
$(\mu+1)$ GA and by $B$ the event that no crossover is executed. Then we
obtain by the law of total probability

$\displaystyle\mathrm{E}(S(P_{t+1})\mid
S(P_{t}))=p_{c}\mathrm{E}(S(P_{t+1})\mid
S(P_{t}),A)+(1-p_{c})\mathrm{E}(S(P_{t+1})\mid S(P_{t}),B).$ (24)

By (7) above we obtain

$\displaystyle\mathrm{E}(S(P_{t+1})\mid S(P_{t}),B)=(1-\gamma)S(P_{t})+\beta$
(25)

where $\beta$ and $\gamma$ are defined as in (6) and with Lemma 4.9

$\displaystyle E(S(P_{t+1})\mid
S(P_{t}),A)\geq\left(1-\frac{3}{\mu^{2}}\right)S(P_{t})-9k(\mu-1)\chi/n.$ (26)

Plugging (25) and (26) into (24) gives the result. ∎

Note that our proofs do not rely on the existence of such an equilibrium
state. For a finite state space the drift is trivially negative for large
enough $S(P_{t})$, in particular when $S(P_{t})$ is at its maximum value.
However, in general, there may be no equilibrium state due to rounding issues,
or there may be more than one such state due to non-monotonicity of the drift.
Despite these caveats, we use the term equilibrium state since it provides
helpful intuition. For our later paramater choices we will always have
$\alpha>0$. Equation (23) implies that the equilibrium state of $S(P_{t})$ is
at least $\alpha/\delta$, since for $S(P_{t})\leq\alpha/\delta$ the drift is
non-negative due to $\mathrm{E}(S(P_{t+1})-S(P_{t}))\mid S(P_{t}))\geq-\delta
S(P_{t})+\alpha\geq 0$. In the next lemma we will compute how large
$\alpha/\delta$ is for standard bit mutations with $\chi=\Theta(1)$. If
$\mu=\Omega(n)$ then we will show that
$\alpha/\delta\geq(1-O(k^{3/2}p_{c}+n/\mu))2k\mu^{2}$. Note that $2k\mu^{2}$
is a deterministic upper bound for $S(P_{t})$ because any two individuals on
the plateau have distance at most $2k$. Hence, if $k^{3/2}p_{c}$ and $n/\mu$
are both small, then the following corollary implies that the equilibrium
state is very close to the maximum.

For brevity, we write

$\displaystyle C_{1}:=\sum\nolimits_{\ell=0}^{k}p_{\ell}\quad\text{ and }\quad
C_{2}:=\frac{n}{k}\sum\nolimits_{\ell=0}^{k}\ell p_{\ell}.$ (27)

Note that for standard bit mutations with $\chi=\Theta(1)$ and for $k\leq n/2$
we have $C_{1},C_{2}=\Theta(1)$ by Lemma 3.6.

######  Corollary 4.11.

In Situation 4.8, let $\alpha,\delta$ be as in (21), (22) and $C_{1},C_{2}$ as
in (27). Then

$\displaystyle\frac{\alpha}{\delta}\geq
2k\mu^{2}\cdot\left(1-p_{c}\frac{C_{2}+9\chi/4}{C_{2}}-\frac{k}{n-k}-\frac{n}{\mu-1}\frac{2C_{1}+3p_{c}}{2C_{2}}\right).$
(28)

In particular, let $\varepsilon>0$. If
$p_{c}\leq\frac{\varepsilon}{3}\frac{C_{2}}{C_{2}+9\chi/4}$ and $\mu\geq
1+\frac{3n}{\varepsilon}\frac{2C_{2}}{2C_{1}+3p_{c}}$ and
$k\leq\frac{\varepsilon(n-k)}{3}$ then $1/\delta=O(\mu n)$ and

$\displaystyle\alpha/\delta\geq 2k\mu^{2}\cdot\left(1-\varepsilon\right).$
(29)

###### Proof.

We may write

$\displaystyle\alpha=4C_{2}(\mu-1)\frac{k}{n}\left(1-p_{c}(1+9\chi/(4C_{2}))\right).$

For $\delta$, using $1-p_{c}\leq 1$ we obtain the upper bound

$\displaystyle\delta\leq\frac{1}{\mu^{2}}\left(3p_{c}+2C_{1}+\frac{2C_{2}(\mu-1)}{n-k}\right)=\frac{2C_{2}(\mu-1)}{\mu^{2}n}\left(1+\frac{k}{n-k}+\frac{(2C_{1}+3p_{c})n}{2C_{2}(\mu-1)}\right).$
(30)

This shows $1/\delta=O(\mu n)$. Combining both bounds yields

$\displaystyle\frac{\alpha}{\delta}\geq
2k\mu^{2}\cdot\frac{1-p_{c}(1+9\chi/(4C_{2}))}{1+\frac{k}{n-k}+\frac{(2C_{1}+3p_{c})n}{2C_{2}(\mu-1)}}.$

The bound (28) now follows from the inequality $(1-x)/(1+y)\geq(1-x)(1-y)\geq
1-x-y$ for all $x,y\geq 0$. Equation (29) then follows immediately by plugging
in. ∎

We now provide a lemma which shows that if $\alpha/\delta$ is close to
$2k\mu^{2}$ then after some short initial time $\tau_{0}$ it is likely that
$S(P_{t+\tau_{0}+\tau})$ is also close to $2k\mu^{2}$ for a constant fraction
of values of $\tau$.

######  Lemma 4.12.

In Situation 4.8, let $\alpha$ and $\delta$ as in (21) and (22) respectively.
Suppose that $\alpha/\delta<2k\mu^{2}$ and let $\varepsilon\geq
1-\frac{\alpha}{2k\mu^{2}\delta}>0$, or equivalently

$\displaystyle\alpha/\delta\geq(1-\varepsilon)2k\mu^{2}.$ (31)

Let $\tau_{0}:=\lceil\ln(1/\varepsilon)/\delta\rceil$, let $T\in\mathds{N}$,
and let $\mathcal{E}_{T}$ be the event that $|\\{\tau\in[T]:\
S(P_{t+\tau_{0}+\tau})\geq(1-4\varepsilon)2k\mu^{2}\\}|\geq T/4$. Then
$\mathrm{Pr}(\mathcal{E}_{T})\geq 1/3$.

###### Proof.

We start with the following lemma where we show that $E(S(P_{t}))$ converges
quickly to $\alpha/\delta$. Note that this lemma only examines the expectation
$E(S(P_{t}))$. In the subsequent proof, we will then deduce that similar
statements also hold for the random variable $S(P_{t})$.

######  Lemma 4.13.

In Situation 4.8, let $\alpha$ and $\delta$ be as in (21) and (22)
respectively, and suppose that its current population is
$P_{t}\subseteq\textsc{plateau}$. Then for every $\tau\in\mathds{N}$,

$\displaystyle\mathrm{E}(S(P_{t+\tau})\mid
S(P_{t}))\geq(1-e^{-\delta\tau})\alpha/\delta.$ (32)

###### Proof.

Using (23) from Corollary 4.10, we have

$\displaystyle\frac{\alpha}{\delta}-\mathrm{E}(S(P_{t+1})\mid
S(P_{t}))\leq\frac{\alpha}{\delta}-(1-\delta)S(P_{t})-\alpha=(1-\delta)\left(\frac{\alpha}{\delta}-S(P_{t})\right).$

Hence, the random variable $Y_{t}:=\alpha/\delta-S(P_{t})$ satisfies the
recursion $E(Y_{t+1}\mid Y_{t})\leq(1-\delta)Y_{t}$. Iterating this recursion
$\tau$ times and using the law of total expectation, we obtain
$E(Y_{t+\tau}\mid Y_{t})\leq(1-\delta)^{\tau}Y_{t}$. Written out and using
$S(P_{t})\geq 0$, this is

$\displaystyle\frac{\alpha}{\delta}-\mathrm{E}(S(P_{t+\tau})\mid
S(P_{t}))\leq(1-\delta)^{\tau}\left(\frac{\alpha}{\delta}-S(P_{t})\right)\leq(1-\delta)^{\tau}\frac{\alpha}{\delta}\leq
e^{-\delta\tau}\frac{\alpha}{\delta}.$

This is equivalent to (32) and proves the lemma. ∎

Fix $\tau\in\mathds{N}$. We first use Lemma 4.13 for
$\tau_{0}+\tau\geq\tau_{0}$ and find that

$\displaystyle\begin{split}\mathrm{E}(S(P_{t+\tau_{0}+\tau})\mid
S(P_{t}))&\geq(1-e^{-\delta(\tau_{0}+\tau)})\frac{\alpha}{\delta}\geq(1-e^{-\delta\tau_{0}})\frac{\alpha}{\delta}\\\
&\geq(1-\varepsilon)\frac{\alpha}{\delta}\geq(1-\varepsilon)^{2}2k\mu^{2}\geq(1-2\varepsilon)2k\mu^{2}.\end{split}$
(33)

Let us write $\rho:=\Pr(S(P_{t+\tau_{0}+\tau})<(1-4\varepsilon)2k\mu^{2})$.
Any two individuals in $P_{t+\tau_{0}+\tau}$ have Hamming distance $k$ from
the optimum, so they have Hamming distance at most $2k$ from each other. Since
$S(P_{t+\tau_{0}+\tau})$ is defined as the sum over $\mu^{2}$ such Hamming
distances, we have $S(P_{t+\tau_{0}+\tau})\leq 2k\mu^{2}$. Therefore, we may
bound

$\displaystyle\mathrm{E}(S(P_{t+\tau_{0}+\tau})\mid
S(P_{t}))\leq\rho\cdot(1-4\varepsilon)2k\mu^{2}+(1-\rho)\cdot
2k\mu^{2}=2k\mu^{2}-4\varepsilon\cdot 2k\mu^{2}\cdot\rho.$

This implies

$\displaystyle\rho\leq\frac{2k\mu^{2}-\mathrm{E}(S(P_{t+\tau_{0}+\tau})\mid
S(P_{t}))}{4\varepsilon\cdot 2k\mu^{2}}\stackrel{{\scriptstyle\eqref{eq:SPt-
is-large-1}}}{{\leq}}\frac{2\varepsilon\cdot 2k\mu^{2}}{4\varepsilon\cdot
2k\mu^{2}}=1/2.$ (34)

Now consider the random variable

$N_{T}:=|\\{\tau\in[T]:\
S(P_{t+\tau_{0}+\tau})<(1-4\varepsilon)2k\mu^{2}\\}|.$

By definition of $\rho$ and by (34), it has expectation $E(N_{T})\leq T/2$. By
Markov’s inequality, we obtain $\mathrm{Pr}(N_{T}>3T/4)\leq(T/2)/(3T/4)=2/3$.
On the other hand, the event $\mathcal{E}_{T}$ from the lemma is the
complement of the event “$N_{T}>3T/4$”, and hence
$\mathrm{Pr}(\mathcal{E}_{T})\geq 1-\mathrm{Pr}(N_{T}>3T/4)\geq 1/3$. This
concludes the proof. ∎

##  5 Analysing the ($\mu$+1) GA on Jump

######  Lemma 5.1.

Let $\varepsilon>0$ and let $P_{t}\subseteq\textsc{plateau}$ be a population
of size $\mu$. Suppose that $S(P_{t})\geq 2k\mu^{2}(1-\varepsilon)$. Then
there are at least $\mu^{2}/2$ pairs $(x,y)\in P_{t}^{2}$ with
$H(x,y)>(1-2\varepsilon)2k$.

###### Proof.

Let $D$ be the set of pairs $(x,y)\in P_{t}^{2}$ with
$H(x,y)>(1-2\varepsilon)2k$. Note that $H(x,y)\leq 2k$ since $x,y$ are in
plateau. Hence, each pair in $D$ has Hamming distance at most $2k$, and each
pair in $P_{t}^{2}\setminus D$ has distance at most $(1-2\varepsilon)2k$.
Hence

$S(P_{t})\leq|D|\cdot
2k+(\mu^{2}-|D|)(1-2\varepsilon)2k=2k\mu^{2}(1-2\varepsilon)+4\varepsilon
k|D|.$

Together with $S(P_{t})\geq 2k\mu^{2}(1-\varepsilon)$, this implies
$2k\mu^{2}\varepsilon\leq 4\varepsilon k|D|$, and thus $|D|\geq\mu^{2}/2$ as
required. ∎

The next theorem gives an upper bound for the expected time until the
$(\mu+1)$ GA (Algorithm 2) finds the global optimum if we use our results from
Lemma 5.1 and Lemma 4.12.

######  Theorem 5.2.

Let $0<\varepsilon<1/4$. In Situation 4.8, suppose
$p_{c}\leq\frac{\varepsilon}{3}\frac{2C_{2}}{2C_{2}+9\chi/4}$ and $\mu\geq
1+\frac{3n}{\varepsilon}\frac{2C_{2}}{2C_{1}+3p_{c}}$ and
$k\leq\varepsilon(n-k)/3$, where $C_{1},C_{2}$ are the constants from (27).
Then the global optimum is found in

$O\big{(}\mu\lceil\lambda
p_{c}\rceil(n\log(1/\varepsilon)+\log(\mu))+4^{(1-8\varepsilon)k}\left(n/\chi\right)^{\lfloor
8\varepsilon k\rfloor}/p_{c}\big{)}$

expected fitness evaluations. In particular, for $\varepsilon=1/(16k)$, we
have $\lfloor 8\varepsilon k\rfloor=0$ and thus get

$\displaystyle O\big{(}\mu\lceil\lambda
p_{c}\rceil(n\log(k)+\log(\mu))+4^{k}/p_{c}\big{)}$ (35)

function evaluations for $p_{c}\leq\frac{1}{48k}\frac{2C_{2}}{2C_{2}+9\chi/4}$
and $\mu\geq 1+48kn\frac{2C_{2}}{2C_{1}+3p_{c}}$ and $k^{2}\leq(n-k)/48$. If
$\mu$ is polynomial in $n$, $\lambda=O(1/p_{c})=O(k)$ and
$k=\Omega(\log^{2}\mu)$, we obtain

$\displaystyle O\big{(}\mu n\log(k)+4^{k}/p_{c}\big{)}.$ (36)

The condition $k=\Omega(\log^{2}\mu)$ ensures that there exist feasible
$\lambda\in[6\sqrt{k}e^{\chi}\ln(\mu),O(k)]$. For the optimal population size
$\mu=\Theta(kn)$ in (36), the upper bound simplifies to
$O(kn^{2}\log(k)+4^{k}/p_{c})$. Note that the upper bounds increase with
$\mu$, hence in terms of our upper bounds there is no benefit of choosing a
population size larger than the minimum requirement.

###### Proof of Theorem 5.2.

Consider the algorithm on $\textsc{Jump}_{k}^{\prime}$, so that the process
continues after sampling the all-one-string. According to Theorem 2.4, we have
that in $O(\lceil\lambda p_{c}\rceil(\mu n+n\log(n)+\mu\log\mu))$ fitness
evaluations $P_{t}\subseteq\textsc{plateau}$. Since by assumption
$\mu=\Omega(n)$, we have $n\log n\in O(\mu n)$ and the bound simplifies to
$O(\lceil\lambda p_{c}\rceil(\mu n+\mu\log\mu))$. Afterwards, let
$\tau_{0}:=\lceil\ln(1/\varepsilon)/\delta\rceil$ as in Lemma 4.12 and note
that by Corollary 4.11 we have $1/\delta=O(\mu n)$, which implies
$\tau_{0}=O(\mu n\log(1/\varepsilon))$. Also by Corollary 4.11 we have
$\alpha/\delta\geq(1-\varepsilon)2k\mu^{2}$ as in (31). Consider a _trial_ of
$\tau_{0}+T$ consecutive generations on plateau, where
$T:=4^{(1-8\varepsilon)k}(n/\chi)^{\lfloor 8\varepsilon k\rfloor}/(\lambda
p_{c}))$. Let $\mathcal{E}$ be the event that during the trial we have
$S(P_{t})\geq(1-4\varepsilon)2k\mu^{2}$ for at least $T/4$ generations in the
trial. We call such generations _good_ generations. Then $\Pr(\mathcal{E})\geq
1/3$ by Lemma 4.12.

By Lemma 5.1, each good generation has at least $\mu^{2}/2$ pairs
$(x_{1},x_{2})\in P_{t}^{2}$ with distance $H(x_{1},x_{2})>2k(1-8\varepsilon)$
from each other, which we call _good pairs_. This implies that the number $r$
of positions in which both $x_{1}$ and $x_{2}$ have a zero-bit is less than
$8\varepsilon k$. Since $r$ is integral, we even have $r\leq\lfloor
8\varepsilon k\rfloor$. In a good generation, a good pair is picked for
crossover with probability at least $p_{c}/2$. If a good pair is picked, then
the algorithm creates $\lambda$ offspring, and with each offspring it may
create the optimum by (i) choosing crossover, (ii) setting all $2(k-r)$
differing bit positions to $1$ via crossover, (iii) correcting the remaining
$r$ bits via mutation, and (iv) not flipping any of the correct bits with
mutation. The probability of each of these steps is $p_{c}$, $2^{-2(k-r)}$,
$(\chi/n)^{r}$, and $(1-\chi/n)^{n-r}=\Theta(1)$, respectively. Hence, the
probability that a fixed individual of the $\lambda$ offspring is the optimum
is at least

$\displaystyle\Omega\left(p_{c}4^{r-k}\left(\frac{\chi}{n}\right)^{r}\right)=\Omega\left(p_{c}4^{-(1-8\varepsilon)k}\left(\frac{\chi}{n}\right)^{\lfloor
8\varepsilon k\rfloor}\right).$

Therefore, conditioned on $\mathcal{E}$, the probability that the optimum is
created in a trial is at least

$\displaystyle
1-\left(1-\Omega\left(p_{c}4^{-(1-8\varepsilon)k}(\chi/n)^{\lfloor
8\varepsilon k\rfloor}\right)\right)^{\lambda T/4}$ $\displaystyle\geq
1-e^{-\Omega\left(p_{c}4^{-(1-8\varepsilon)k}(\chi/n)^{\lfloor 8\varepsilon
k\rfloor}\lambda T/4\right)}=1-e^{-\Omega(1)}=\Omega(1).$

Since $\Pr[\mathcal{E}]\geq 1/3$, the probability to find the optimum in a
fixed trial is $\Omega(1)$. If a trial does not succeed, we start the next
trial. Then we need $O(1)$ trials in expectation until the optimum is found.
This concludes the proof for general $\varepsilon$. For $\varepsilon=1/(16k)$
the statement follows immediately with the simplification
$4^{(1-\varepsilon)k}\leq 4^{k}$. The last statement exploits $\lceil\lambda
p_{c}\rceil=O(1)$ and absorbs the $+\log(\mu)$ term. ∎

Note that for the second case $\varepsilon=1/(16k)$ in Theorem 5.2, the
condition $k^{2}\leq(n-k)/48$ is in particular satisfied for $k=o(\sqrt{n})$.

###  5.1 Tightness

We now argue that $\Omega(4^{k}/p_{c})$ is also a lower bound for the time to
create the optimum from any population on the plateau, unless $p_{c}$ is so
small that it becomes more likely to reach the optimum by mutation. The
following lower bound applies to all $p_{c}>0$ and to all unbiased mutation
operators.

######  Theorem 5.3.

Consider Situation 4.8 and additionally $k\leq\sqrt{n}/2$. Then the expected
optimisation time is at least $\min\\{\Omega(4^{k}/p_{c}),\binom{n}{k}\\}$.

The result also holds for all variants of the ($\mu$+1) GA using arbitrary
parent selection, arbitrary offspring populations, and any replacement
selection that only accepts offspring in $\textsc{plateau}\cup\\{1^{n}\\}$.

###### Proof.

Note that the ($\mu$+1) GA, and its variants mentioned in the statement, will
always maintain a population $P_{t}\subseteq\textsc{plateau}$ until the global
optimum is found. The following arguments apply to all prior time steps $t$.
Consider two individuals $x_{1},x_{2}\in P_{t}$ with Hamming distance $2d$ on
the plateau. (The number must be even since the number of $0/1$-bits and $1/0$
bits in $x_{1},x_{2}$ must be equal when both are in plateau.) Let $y$ be an
offspring created by crossover and standard bit mutation with mutation
probability $p_{m}$. Note that $2d\leq 2k$ by the triangle inequality, because
both parents have distance $k$ from the optimum.

Now, if crossover sets $i$ of the $2d$ bits to one in which the parents
differ, the offspring has $k+d-i$ zeros. To create the optimum, all zeros and
no ones must be flipped. It is well known that every unbiased mutation
operator can be described as follows: pick a radius $r$ (deterministically or
according to some probability distribution) and then flip $r$ different bits
chosen uniformly at random. Assuming that the mutation operator picks radius
$r=k+d-i$ (otherwise it is impossible to create the optimum), the probability
of choosing precisely all zeros to be flipped is
$1/\binom{n}{r}=1/\binom{n}{k+d-i}$. Thus, the probability of $y$ being the
optimum is

$\displaystyle\mathrm{Pr}[y=\vec{1}]=\sum\nolimits_{i=0}^{2d}\binom{2d}{i}2^{-2d}\cdot\frac{1}{\binom{n}{k+d-i}}=4^{-d}\sum\nolimits_{i=0}^{2d}\binom{2d}{i}/\binom{n}{k+d-i}.$
(37)

(This generalises [4, Lemma 2] to arbitrary unbiased mutation operators.)
Denoting the summands in (37) as $S_{0},\dots,S_{2d}$, we have, for all
$i\in\\{1,\dots,2d\\}$,

$\displaystyle\frac{S_{i}}{S_{i-1}}=\frac{\binom{2d}{i}}{\binom{2d}{i-1}}\cdot\frac{\binom{n}{k+d-i+1}}{\binom{n}{k+d-i}}=\frac{2d-i+1}{i}\cdot\frac{n-k-d+i}{k+d-i+1}=\frac{2d-i+1}{k+d-i+1}\cdot\frac{n-k-d+i}{i}$

and we observe that both factors are non-increasing with $i$. Thus, the
minimum of $S_{i}/S_{i-1}$ is attained for $i=2d$ and we get

$\displaystyle\frac{S_{i}}{S_{i-1}}\geq\;$
$\displaystyle\frac{1}{k-d+1}\cdot\frac{n-k+d}{2d}\geq\frac{n-k}{2d(k-d+1)}.$

The denominator is maximised for $d=(k+1)/2$, which implies

$\displaystyle\frac{S_{i}}{S_{i-1}}\geq\;$
$\displaystyle\frac{n-k}{(k+1)((k-1)/2+1)}=\frac{2(n-k)}{(k+1)^{2}}\geq 2$

by assumption on $k$. Hence, the whole sum is dominated by the term for $i=2d$
and

$\displaystyle\mathrm{Pr}[y=\vec{1}]=O\left(4^{-d}/\binom{n}{k-d}\right),$
(38)

which is maximised for $2d=2k$ where $\binom{n}{k-d}=1$. Therefore, for any
two parents on the plateau, the probability that the offspring is the optimum
is $O(4^{-k})$, and the probability of having a generation with crossover that
ends with a global optimum is $O(p_{c}\cdot 4^{-k})$. In generations without
crossover, the parent has $k$ zeros and the probability of creating the
optimum by mutation is at most $1/\binom{n}{k}$. Since in every offspring
creation the probability of creating the optimum is bounded by
$\max\\{O(4^{-k}\cdot p_{c}),1/\binom{n}{k}\\}$, the expected time to generate
the optimum is at least $\min\\{\Omega(4^{k}/p_{c}),\binom{n}{k}\\}$ as
claimed. ∎

Together, we have shown that the term $4^{k}/p_{c}$ yields an asymptotically
tight bound for a range of $k$.

######  Corollary 5.4.

Consider the ($\mu$+1) GA with
$p_{c}\leq\frac{1}{48k}\frac{2C_{2}}{2C_{2}+9\chi/4}$ and
$p_{c}\geq(4k/n)^{k}$, $\mu\geq 1+48kn\frac{2C_{2}}{2C_{1}+3p_{c}}$ and
$\mu\leq\mathrm{poly}(n)$, $\lambda\geq 6\sqrt{k}e^{\chi}\ln(\mu)$ and
$\lambda\leq 1/p_{c}$, where $C_{1},C_{2}$ are as in Theorem 5.2. Then for all
$k\in[\log^{2}n,\ \sqrt{n}/8]$ the expected optimisation time on
$\textsc{Jump}_{k}$ is $\Theta(4^{k}/p_{c})$.

###### Proof.

The preconditions in the final statement of Theorem 5.2 are met if
$k^{2}\leq(n-k)/48$, which is implied by $k\leq\sqrt{n}/8$ for large enough
$n$. Also note that $k=\Omega(\log^{2}n)=\Omega(\log^{2}\mu)$ since $\mu$ is
polynomial in $n$. Then Theorem 5.2 yields an upper bound of

$O\left(\mu n\log(k)+4^{k}/p_{c}\right).$

Now $k\geq\log^{2}n$ implies $4^{k}\geq\mu n\log k$ (with room to spare) and
thus the upper bound simplifies to $O(4^{k}/p_{c})$. For the lower bound, we
use that

$4^{k}/p_{c}\leq
4^{k}\cdot\left(\frac{n}{4k}\right)^{k}=\left(\frac{n}{k}\right)^{k}\leq\binom{n}{k}$

and Theorem 5.3 yields a lower bound of $\Omega(4^{k}/p_{c})$. ∎

##  6 Conclusions

We have presented the first runtime bounds for a ($\mu$+1) GA variant that
show strong benefits of crossover in the regime of large crossover
probabilities $p_{c}$ without explicit diversity-enhancing mechanisms. Our
analysis has shown that the population evolves near-perfect diversity, where
most pairs of parents have the maximum Hamming distance of $2k$. We believe
that our analysis can be easily transferred to a ($\mu$+1) GA when omitting
mutation after crossover as, unlike the work in [3], the optimum can be
reached without mutation. Moreover, we believe that with stronger restrictions
on $p_{c}$ such as $p_{c}=O(1/(kn))$ as in [9] our results apply to the
original ($\mu$+1) GA.

One limitation of our approach is that we had to modify the original ($\mu$+1)
GA to include $\lambda$ competing offspring. An important task for future work
is therefore to show similar results for the original ($\mu$+1) GA. Another
research question is whether the dependency on $p_{c}$ can be further relaxed,
possibly up to $p_{c}=1$ as in [3, 7]. For this one might need to carefully
consider the possible advantages that crossover can provide for population
diversity.

We are confident that our approach can also be applied to other functions of
unitation featuring a plateau that is only left for strict fitness
improvements. This includes generalisations of the $\textsc{Jump}_{k}$
benchmark such as $\textsc{Jump}_{k,\delta}$ [2] or JumpOffset [17] that were
proposed independently, and that contain a fitness valley of a specified width
$\delta$, or the unitation function Hurdle [14] that contains many peaks.

## References

  * Badkobeh et al. [2015] G. Badkobeh, P. K. Lehre, and D. Sudholt.  Black-box complexity of parallel search with distributed populations.  In _Proceedings of Foundations of Genetic Algorithms (FOGA 2015)_ , pages 3–15. ACM, 2015.
  * Bambury et al. [2024] H. Bambury, A. Bultel, and B. Doerr.  An extended jump functions benchmark for the analysis of randomized search heuristics.  _Algorithmica_ , 86(1):1–32, 2024.
  * Dang et al. [2016] D.-C. Dang, T. Friedrich, T. Kötzing, M. S. Krejca, P. K. Lehre, P. S. Oliveto, D. Sudholt, and A. M. Sutton.  Emergence of diversity and its benefits for crossover in genetic algorithms.  In _Proceedings of the 14th International Conference Parallel Problem Solving From Nature (PPSN)_. Springer, 2016.
  * Dang et al. [2018] D.-C. Dang, T. Friedrich, T. Kötzing, M. S. Krejca, P. K. Lehre, P. S. Oliveto, D. Sudholt, and A. M.Sutton.  Escaping local optima using crossover with emergent diversity.  _IEEE Transactions on Evolutionary Computation_ , 22(3):484–497, 2018.
  * Doerr [2020] B. Doerr.  Probabilistic tools for the analysis of randomized optimization heuristics.  In B. Doerr and F. Neumann, editors, _Theory of Evolutionary Computation: Recent Developments in Discrete Optimization_ , pages 1–87. Springer, 2020.
  * Doerr [2021] B. Doerr.  Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift.  _Evolutionary Computation_ , 29(2):305–329, 2021\.
  * Doerr et al. [2024] B. Doerr, A. Echarghaoui, M. Jamal, and M. S. Krejca.  Runtime Analysis of the ($\mu$ \+ 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations.  In _38th Annual AAAI Conference on Artificial Intelligence_ , Feb. 2024.
  * Friedrich et al. [2022] T. Friedrich, T. Kötzing, A. Radhakrishnan, L. Schiller, M. Schirneck, G. Tennigkeit, and S. Wietheger.  Crossover for cardinality constrained optimization.  In _Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2022)_ , page 1399–1407. ACM, 2022.
  * Jansen and Wegener [2002] T. Jansen and I. Wegener.  On the analysis of evolutionary algorithms – a proof that crossover really can help.  _Algorithmica_ , 34(1):47–66, 2002.
  * Kötzing et al. [2011] T. Kötzing, D. Sudholt, and M. Theile.  How crossover helps in pseudo-boolean optimization.  In _Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO 2011)_ , pages 989–996. ACM, 2011.
  * Lehre and Witt [2010] P. K. Lehre and C. Witt.  Black box search by unbiased variation.  In _Genetic and Evolutionary Computation Conference (GECCO 2010)_ , pages 1441–1448. ACM, 2010.
  * Lengler et al. [2023] J. Lengler, A. Opris, and D. Sudholt.  Analysing equilibrium states for population diversity.  In _Proceedings of the 2023 Annual Conference on Genetic and Evolutionary Computation_ , GECCO ’23, pages 1628–1636. ACM, 2023.
  * Li and Kötzing [2023] X. Li and T. Kötzing.  Experimental analyses of crossover and diversity on Jump.  In _Proceedings of the Companion Conference on Genetic and Evolutionary Computation_ , GECCO ’23 Companion, page 823–826. Association for Computing Machinery, 2023.  ISBN 9798400701207.
  * Prügel-Bennett [2004] A. Prügel-Bennett.  When a Genetic Algorithm Outperforms Hill-Climbing.  _Theoretical Computer Science_ , 320(1):135 – 153, 2004.
  * Wineberg and Oppacher [2003] M. Wineberg and F. Oppacher.  The underlying similarity of diversity measures used in evolutionary computation.  In _Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003)_ , pages 1493–1504. Springer, 2003.
  * Witt [2006] C. Witt.  Runtime analysis of the ($\mu$+1) EA on simple pseudo-Boolean functions.  _Evolutionary Computation_ , 14(1):65–86, 2006\.
  * Witt [2021] C. Witt.  On Crossing Fitness Valleys with Majority-Vote Crossover and Estimation-of-Distribution Algorithms.  In _Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA ’21)_. ACM, 2021.  ISBN 9781450383523.

##  Appendix A Details on adapted runtime bounds stated in Table 1

In this short appendix we give further details on adaptations made to
published bounds from [10] and [7].

Kötzing et al. [10] showed a bound of

$O(\mu n\log(n)+e^{6k}\mu^{k+2}n)$

for $p_{c}\leq k/n$ and for a mutation operator which never creates duplicates
of the parent. Inspecting the proof of [10, Theorem 7], we found a minor bug.
The probability of event E6 of crossover happening at least once during $n/k$
generations and no mutation leading to an accepted offspring is bounded from
below by

$1-(1-p_{c})^{n/k}\cdot\left(1-\frac{k}{n}\right)^{k/n}=\Omega(1).$

There are two typos in the expression on the left-hand side; it should read

$(1-(1-p_{c})^{n/k})\cdot\left(1-\frac{k}{n}\right)^{n/k}.$

The above equality is correct for $p_{c}=\Theta(k/n)$, but for smaller $p_{c}$
we only have $1-(1-p_{c})^{n/k}=\Theta(p_{c}\cdot n/k)$ (cf. [1, Lemma 10]).
This leads to an additional factor of $1/(p_{c}\cdot n/k)=k/(np_{c})$ in the
asymptotic bound, which then becomes

$O(\mu n\log(n)+e^{6k}\mu^{k+2}k/p_{c}).$

Doerr et al. [7] very recently proved an upper bound of

$\displaystyle O\Big{(}$ $\displaystyle\mu
n\log(\mu)+n\log(n)+\frac{(n/k+\mu)\log(\mu)}{(n/\chi)^{-k+1}\min(\exp(p_{c}\mu/(2048e)),(n/\chi)^{+k-1})}+\left(\frac{n}{\chi}\right)^{k-1}\Big{)}$

for $2\leq\mu=o(n)$. The third summand can be written as

$\displaystyle\frac{(n/k+\mu)\log(\mu)}{\min((n/\chi)^{-k+1}\exp(p_{c}\mu/(2048e)),1)}\leq\frac{(n/k+\mu)\log(\mu)}{(n/\chi)^{-k+1}\exp(p_{c}\mu/(2048e))}+\frac{(n/k+\mu)\log(\mu)}{1}.$

Since $(n/k+\mu)\log(\mu)=O(\mu n\log(\mu))$, the last term can be omitted and
we obtain a simplified bound of

$\displaystyle O\left(\mu
n\log(\mu)+n\log(n)+\left(\frac{n}{\chi}\right)^{k-1}\left(1+\frac{(n/k+\mu)\log(\mu)}{\exp(p_{c}\mu/(2048e))}\right)\right).$