# Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark

Marcel Chwialkowski, Benjamin Doerr, Martin Stefan Krejca

► To cite this version:

Marcel Chwialkowski, Benjamin Doerr, Martin Stefan Krejca. Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark. IEEE Transactions on Evolutionary Computation, 2026, 30 (1), pp.311-320. 10.1109/TEVC.2025.3549929. hal-05533937

HAL Id: hal-05533937

https://hal.science/hal-05533937v1

Submitted on 3 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Runtime Analysis of the Compact Genetic
Algorithm on the LeadingOnes Benchmark

Marcel Chwiałkowski, Benjamin Doerr, Martin S. Krejca

**Abstract**—The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA)—another simple EDA—, the cGA has been subject to extensive mathematical runtime analyses, often showcasing a similar or even superior performance to competing approaches. Surprisingly though, up to date and in contrast to the UMDA and many other heuristics, we lack a rigorous runtime analysis of the cGA on the LEADINGONES benchmark—one of the most studied theory benchmarks in the domain of evolutionary computation.

We fill this gap in the literature by conducting a formal
runtime analysis of the cGA on LEADINGONES. For the cGA's
single parameter—called the hypothetical population size—at
least polylogarithmically larger than the problem size, we prove
that the cGA samples the optimum of LEADINGONES with high
probability within a number of function evaluations quasi-linear
in the problem size and linear in the hypothetical population size.
For the best hypothetical population size, our result matches, up
to polylogarithmic factors, the typical quadratic runtime that
many randomized search heuristics exhibit on LEADINGONES.
Our analysis exhibits some noteworthy differences in the working
principles of the two algorithms which were not visible in
previous works.

***Index Terms***—Estimation-of-distribution algorithms, compact genetic algorithm, runtime analysis, LeadingOnes.

# I. INTRODUCTION

ESTIMATION-of-distribution algorithms [1] (EDAs) con-
stitute a large and important class of general-purpose
randomized optimization heuristics (ROHs) [2]. A key feature
of EDAs that clearly separates them from other prominent
classes of ROHs, such as evolutionary algorithms [3], is that
they maintain and evolve a probabilistic model of the search
space. This model defines a probability distribution over the
search space and aims at giving better solutions a higher
probability. Ideally, only global optima in the search space
have a positive probability. EDAs iteratively refine their model
based on random samples thereof, giving more probability to
more promising solutions. This approach has been shown to
outperform competing approaches both empirically [1] as well
as theoretically [4] on numerous occasions.

Like other ROHs, EDAs have been subject to mathemat-
ical investigations for more than two decades, starting with
convergence guarantees [4]. The first fully rigorous runtime
analysis comparable to the current state of the art in this

field was carried out by Droste [5]. In this seminal paper,
he analyzed the *compact genetic algorithm* [6] (cGA) on
the *ONEMAX* benchmark. The cGA is a simple EDA that
samples the problem variables independently, resulting in a so-
called *univariate* model. It refines this model in each iteration
based solely on two independent samples, shifting probability
mass in discrete steps of size $\frac{1}{\mu}$, where $\mu$ is an algorithm-
specific parameter called the *hypothetical population size*.
Since the cGA is a simple EDA and since ONEMAX is the
most commonly studied theory benchmark in the field of
evolutionary computation [7], the result by Droste [4] served
as a logical and strong first runtime contribution in the domain
of EDAs. Interestingly, this paper was initially not followed
up by a lot of theoretical work.

The rigorous investigation of EDAs only gained momentum
with the paper by Dang and Lehre [8], who analyzed the
runtime of the *univariate marginal distribution algorithm* [9]
(UMDA), which is also a univariate EDA but allows, in
contrast to the cGA, for a larger sample size than two. Dang
and Lehre considered the *ONEMAX* and the *LEADINGONES*
theory benchmarks, covering the two most important theory
benchmarks in the field. Since then, numerous theoretical
results on EDAs have been published [4]. Most of these results
still only consider the cGA and the UMDA, but they provide us
with deep insights into the complex dynamics of updating the
algorithms' probabilistic models. Moreover, they cover more
complex benchmarks than *ONEMAX* and *LEADINGONES*, and
they also consider more complex scenarios, such as noisy
optimization. In Section II, we give more detail about some
of these works.

Surprisingly, despite this increased theoretical body of lit-
erature and the long way that runtime analysis on EDAs has
come since the initial paper by Droste [4], to this day, the
cGA's runtime performance on the LEADINGONES benchmark
has not been rigorously studied. In other words, we are still
missing a theoretical result for one of the most studied EDAs
on one of the most studied theory benchmarks. In comparison,
runtime guarantees for the commonly studied UMDA on
LEADINGONES have existed for more than a decade [10].

**Our contribution:** We conduct the first runtime analysis of the cGA on LEADINGONES. We consider the parameter regime of the algorithm where it exhibits low *genetic drift*, that is, the updates of the cGA to its probabilistic model are sufficiently small such that random fluctuations in the update process do not have a strong impact on the overall performance. For a problem size of *n*, we show that the cGA with $\mu = \Omega(n \log^2 n)$ samples the optimum of LEADINGONES

M. Chwiałkowski is with École Polytechnique, Institut Polytechnique de Paris

B. Doerr and M. S. Krejca are with Laboratoire d'Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris

This research benefited from the support of the FMJH Program Gaspard Monge for optimization and operations research and their interactions with data science.
with high probability after $O(\mu n \log n)$ function evaluations (Theorem 4). This runtime bound is minimized for $\mu = \Theta(n \log^2 n)$, resulting in an overall runtime of $O(n^2 \log^3 n)$.

This runtime bound is slightly worse, by a factor of $O(\log^3 n)$, compared to the common $O(n^2)$ bound of many other ROHs on LEADINGONES [7], including the best-known runtime bound of the UMDA [11]. For the generally preferred regime of low genetic drift, the best known runtime bound for the UMDA is $\Theta(n^2 \log n)$ [12], which is only better by a factor of $O(\log^2 n)$. These small differences might be a consequence of how the cGA and the UMDA fix certain parts in their probabilistic model. As the UMDA, due to its larger sample size, can apply larger (justified) changes to its model, it can adjust it slightly quicker. We discuss this difference in the optimization behavior of the two algorithms in more detail after Lemma 7 and a second difference at the end of Section IV.

We note, though, that we currently have no matching lower bound. Hence we cannot say whether the two algorithms truly have a different asymptotic runtime or the difference in the upper bounds is caused by our upper bound not being absolutely tight. Due to the difficulty of proving lower bounds, we have to leave this an open problem.

**Outline:** We discuss related work in Section II. In Section III, we describe the cGA, the LEADINGONES problem, and the mathematical tools we use for our analysis. We then conduct the runtime analysis of the cGA on LEADINGONES in Section IV. Last, we conclude our paper in Section V.

## II. RELATED WORK

We now discuss important runtime results of EDAs that relate to our result. The term *runtime* refers to the number of function evaluations until a global maximum of the objective function is sampled for the first time. For EDAs, runtime results are often shown to hold with high probability but also regularly in expectation. We do not detail which is the case, as they can often be translated into each other. Moreover, we note that EDAs are often studied with *borders* in their probabilistic model, which prevent them from fully fixing problem variables to a deterministic value. If borders are absent, the translation between expected runtime and the ones with high probability no longer works, as the runtime of the algorithm is infinite if the probabilistic model fixes a problem variable to a wrong value. Moreover, results in the regime of high genetic drift only hold if borders are present. However, since we aim to provide an overview on the general runtime behavior of the algorithms, we do not mention the specific details in the following and refer instead to the respective works.

We first discuss the effect of *genetic drift* in EDAs, which underlies all of the runtime results, although not always explicitly stated this way. Afterward, we discuss results of the cGA on benchmarks other than LEADINGONES. Last, we discuss results of other EDAs on LEADINGONES.

**Genetic drift in EDAs.** Genetic drift is a concept that quantifies how much an EDA is affected by random fluctuations in the model update, due to the variance in the samples. If genetic drift is *high*, this usually implies that the probability

is high that the probability mass for an incorrect value of some problem variables<fnref n="1" /> is close to 1. Analogously, *low* genetic drift usually implies with high probability that the probability mass for each problem variable is not large for incorrect values, for a sufficiently long time.

Doerr and Zheng [13] provide a tight quantification of the effect of genetic drift in various EDAs, including the cGA and the UMDA. Their results in particular allow to argue that with high probability the probability mass for incorrect values of the problem variables remains small. During this time, an EDA has usually the best chances of succeeding in optimization.

**Runtime results for the cGA.** A substantial line of research studies the runtime of the cGA on the ONEMAX benchmark, which returns the number of 1s in a length-$n$ bit strings; a quantity that is aimed to be maximized. Many classic ROHs with suitable parameter values have an expected runtime of $O(n \log n)$ on ONEMAX [14], [15], [16], [17], [18], [19], [20], [21]. The seminal paper by Droste [5] came close to this bound for the cGA, proving for an arbitrary constant $\varepsilon > 0$ and for a choice of $\mu = \Omega(n^{1/2+\varepsilon})$ a runtime of $O(\mu\sqrt{n})$. This result was improved and made tight by Sudholt and Witt [22], who proved an upper bound of $O(\mu\sqrt{n})$ for $\mu = \Omega(\sqrt{n} \log n)$, and a general lower bound of $\Omega(\mu\sqrt{n} + n \log n)$, matching the typical $O(n \log n)$ bound for the best choice of $\mu$. We note that the upper bound pertains to the regime of low genetic drift. This result was later complemented by Lengler, Sudholt, and Witt [23], who considered smaller values of $\mu$, where the effect of genetic drift is more prominent, and showed a bound of $\Omega(\mu^{1/3}n + n \log n)$ for $\mu = O(\sqrt{n}/\log^2 n)$. This result shows that the cGA has a runtime strictly worse than $O(n \log n)$ for $\mu = \omega(\log^3 n) \cap O(\sqrt{n}/\log^2 n)$, a parameter range in the regime with high genetic drift.

The cGA has also been analyzed on a noisy version of ONEMAX where additive posterior noise disturbs the fitness [24]. This result shows that the cGA can deal with noise of very large variance if the parameter $\mu$ is chosen adequately, which is in contrast to population-based evolutionary algorithms (EAs), which fail. Using a smart restart strategy [25], this performance can also be achieved without knowing the variance of the noise. A similar superior performance of the cGA was also shown for a rugged version of ONEMAX [26].

The cGA also shows a very promising runtime behavior in overcoming local optima. Hasenöhrl and Sutton [27] initiated the runtime analysis of the cGA on the JUMP benchmark with gap size $k$, proving superpolynomial speed-ups compared to mutation-only EAs. This result was later refined by Doerr [28], who proved that the cGA optimizes JUMP with $k = O(\log n)$ in only $O(\mu\sqrt{n})$ function evaluations if $\mu = \Omega(\sqrt{n} \log n) \cap \text{poly}(n)$. This results for $\mu = \Theta(\sqrt{n} \log n)$ in a runtime of $O(n \log n)$, which is the same as on ONEMAX, standing in stark contrast to mutation-only EAs, who exhibit a runtime of $\Theta(n^k)$ [29]. Moreover, Witt [30] showed that the cGA also performs well with different variants of fitness valleys, whereas other approaches that perform well on JUMP fail.

<footnote n="1">¹That is, a value that is different from the one of a global optimum.</footnote>
Last, we mention that the cGA was also studied on the
binary-value function BINVAL. The first result was given again
by Droste [5], proving for arbitrary ε > 0 and a choice
of μ = Ω(n1+ε) a runtime bound of O(μn), as well as
the general bound Ω(μn). Witt [31] refined this result and
proved for a choice of μ = Ω(n log n) ∩ poly(n) a runtime
bound of Θ(μn). This runtime is strictly worse than the
general O(n log n) bound that the (1 + 1) EA exhibits on all
linear functions [32], showing that the cGA does not always
compete or outperform other existing approaches. That more
complex algorithms may find it harder to optimize BINVAL
was later observed also for the (1 + λ) EA [33], which for
larger population sizes is again is faster on ONEMAX than on
BINVAL.

**EDA runtime results for LEADINGONES.** LEADINGONES returns the length of the longest all-1s prefix of a bit string. It has been mostly studied for the UMDA, which takes $\lambda$ samples each iteration and performs its update based on the $\mu$ best of these. We note that the dynamics of the UMDA can depend drastically on the ratio of $\mu$ and $\lambda$ (the selection pressure). However, in order to keep this section brief, we assume that $\mu/\lambda$ is constant in the problem size and sufficiently well-chosen, without elaborating on the details in the following. We note that under these assumptions, $\mu$ of the UMDA relates well to $\mu$ of the cGA when comparing runtimes.

The first result of the UMDA on LEADINGONES was
proven by Chen et al. [10], showing for an arbitrary constant
$\epsilon > 0$ and a choice of $\mu = \Omega(n^{2+\epsilon})$ a runtime of $O(\mu n)$,
far off from the common runtime bound of $O(n^2)$ of other
ROHs [34], [15], [16], [17], [35], [36], [37]. Dang and
Lehre [8] drastically improved this result by showing a runtime
of $O(n\mu \log \mu + n^2)$ for $\mu = \Omega(\log n)$. For $\mu = O(n/\log n)$,
this matches the common $O(n^2)$ bound. Interestingly, this
result applies to a regime of $\mu$ where genetic drift is not
low. The case with low genetic drift, for $\mu = \Omega(n \log n)$,
was refined by Doerr and Krejca [12], who proved a runtime
of $\Theta(\mu n)$. For the best choice of $\mu$, this results in a bound of
$\Theta(n^2 \log n)$, which is worse than the typical $O(n^2)$ runtime
by a factor of $O(\log n)$. This shows that the regime with
low genetic drift is not optimal for the UMDA on LEADING-
ONES. An analogous asymptotically tight bound was recently
proven for a multi-valued version of the UMDA on a multi-
valued LEADINGONES version [38], which generalizes the
binary case. We note that Adak and Witt [39] used the same
framework and proved an upper bound of a multi-valued cGA
on a multi-valued ONEMAX version, almost analogous to the
bound in the binary domain for low genetic drift, but worse
by a factor of $\log^2 n$.

The UMDA was also considered in a prior-noise setting on
LEADINGONES [40], where, with constant probability, instead
of returning the function value of a sample $x \in \{0, 1\}^n$, the
noisy version returns the function value of a variant of $x$ where
a single position chosen uniformly at random is inverted. The
authors prove that the runtime of the UMDA in this scenario
is identical to the unnoisy case. That is, for $\mu = \Omega(\log n)$, the
runtime is $O(n\mu \log \mu + n^2)$.

LEADINGONES was also studied for newly created EDAs
that operate differently from purely univariate EDAs like
the cGA and the UMDA. Doerr and Krejca introduced the
significance-based cGA [41] (sig-cGA), which is similar to
the traditional cGA but also stores some history of good
variable values and only updates its probabilistic model if this
history shows a statistically significant bias toward a certain
value. This algorithm does not require the parameter $\mu$ of the
classic cGA. The authors prove a runtime of $O(n \log n)$ of
the sig-cGA on LEADINGONES, which was the first ROH
with such a good proven runtime on LEADINGONES while
also showcasing a runtime of $O(n \log n)$ on ONEMAX. This
result was followed by the introduction of the competing genes
evolutionary algorithm (cgEA) by Ajimakin and Devi [42],
which is an algorithm with a population of size $\mu$ that fixes
in each iteration the value of one problem variable. The cgEA
bases this decision on a more involved decision process, mak-
ing use of the Gauss-Southwell score and of inverting values
at specific positions. The authors prove for $\mu = \Omega(\log n)$ a
runtime of $O(\mu n)$ of the cgEA on LEADINGONES, which
matches the $O(n \log n)$ bound of the sig-cGA for the best
choice of $\mu$.

III. PRELIMINARIES

Let $\mathbb{N}$ denote the natural numbers, including 0, and for all $m, n \in \mathbb{N}$, let $[m \cdot n] = [m, n] \cap \mathbb{N}$ as well as $[n] := [1 \cdot n]$.

Let $n \in \mathbb{N}_{\ge 1}$. We consider pseudo-Boolean maximization, that is, the maximization of fitness functions $f: \{0,1\}^n \to \mathbb{R}$. We call each $x \in \{0,1\}^n$ an individual, and $f(x)$ the fitness of $x$. Moreover, for all $v \in \mathbb{R}^n$ and all $i \in [n]$, let $v_i$ denote the value of $v$ at position $i$. When given a fitness function, we implicitly assume that $n$ is provided, and when we use big-O notation, it always refers to asymptotics in this $n$. For example, an expression of $o(1)$ tends to 0 as $n$ tends to infinity.

We say that an event *E* occurs *with high probability* if and
only if the probability of *E* not occurring is at most *O*(n⁻¹).
Last, for each proposition *A*, we let 1{*A*} denote the indicator
function for *A*, which is 1 if *A* is true, and it is 0 otherwise.

A. *The Compact Genetic Algorithm*

The *compact genetic algorithm* [6] (cGA, Algorithm 1) maximizes a given pseudo-Boolean function *f* by maintaining a *frequency vector* *p* ∈ [1/n, 1 - 1/n]ⁿ that corresponds to a probability distribution over {0, 1}ⁿ as follows. For each *i* ∈ [*n*], the *frequency* *p*ᵢ indicates the independent probability to sample a 1 at position *i*. Formally, let *x* ∈ {0, 1}ⁿ, and let *Z* ∈ {0, 1}ⁿ be a random sample from *p*. Then Pr[*Z* = *x*] = ∏ᵢ∈[*n*] (pᵢᵏ (1 - pᵢ)¹⁻ᵏ). Note that since *p* is restricted to [1/n, 1 - 1/n]ⁿ, at any time any variable value can be sampled with positive probability.

The cGA updates *p* iteratively based on two independent
samples, *x*⁽¹⁾ and *x*⁽²⁾, and on an algorithm-specific parameter
*μ* ∈ ℝ>0 called the *hypothetical population size*. It evaluates
the fitness of the two samples and assigns the sample with
the higher fitness to *y*⁽¹⁾ and the other one to *y*⁽²⁾. Afterward,
it adjusts the components of *p* where *y*⁽¹⁾ and *y*⁽²⁾ differ by
an additive *step size* of 1/μ towards the value of *y*⁽¹⁾. More
precisely, for each $i \in [n]$, the following update is performed. If $y_i^{(1)} = 1$ and $y_i^{(2)} = 0$, then $p_i$ is increased by $\frac{1}{\mu}$. If $y_i^{(1)} = 0$ and $y_i^{(2)} = 1$, then $p_i$ is decreased by $\frac{1}{\mu}$. If $y_i^{(1)} = y_i^{(2)}$, then $p_i$ remains unchanged. Last, for all positions $i \in [n]$, if $p_i$ is less than $\frac{1}{n}$, it is set to $\frac{1}{n}$. Analogously, if $p_i$ is greater than $1 - \frac{1}{n}$, it is set to $1 - \frac{1}{n}$. We say that *p* is restricted to $[\frac{1}{n}, 1 - \frac{1}{n}]^n$.

Due to restricting *p*, the update made to each component can be less than $\frac{1}{\mu}$ while larger than 0. As this makes the mathematical analysis needlessly complicated, we assume that the range $\frac{1}{2} - \frac{1}{n}$ of frequency values from $\frac{1}{2}$ to either of the extreme values is a multiple of the step size $\frac{1}{\mu}$. This ensures that non-zero updates to *p* are always exactly $\frac{1}{\mu}$. This is known as the *well-behaved frequency assumption* [28], and we apply this terminology also to $\mu$, meaning that its choice results in well-behaved frequencies. This assumption solely simplifies the mathematical analysis. All of our results are still valid for other values of $\mu$ that respect the restrictions of the respective mathematical statement.

Algorithm 1 uses the same notation as above but indicates the iteration $t \in \mathbb{N}$ for each variable in the superscript. We say that the algorithm is in iteration $t$ if and only if the samples are indexed with $t$. Hence, the first iteration is 0. We are interested in the number of iterations until a global optimum of $f$ is sampled for the first time. We call this value the *runtime of the cGA on f*. We note that since the cGA evaluates $f$ exactly twice each iteration, its runtime is also the number of fitness evaluations until a global optimum of $f$ is sampled for the first time, up to a factor of 2.

**Differences to practical implementations.** Algorithm 1 does not mention a specific termination criterion. As we stop our theoretical considerations once a global optimum is sampled, we require the cGA to run at least as long, which is trivially given if it runs indefinitely. In practice, a budget for the number of fitness evaluations is typically employed. Similarly, we do not specify what the cGA actually returns, as this is irrelevant for our analysis. In practice, since one is interested in good individuals, one usually stores the individual with the best-so-far fitness and returns it together with the frequency vector upon termination.

## B. The LeadingOnes Benchmark

LEADINGONES, first proposed in [34], is one of the most prominent benchmarks in the theoretical analysis of randomized search heuristics. The problem returns the longest prefix of consecutive 1s in an individual. Formally,

$$ \text{LEADINGONES: } x \mapsto \max\{i \in [0..n]: \forall j \in [i]: x_j = 1\}. $$

The problem is unimodal, with the all-1s bit string being the global optimum. Note that if an individual has a LEADING-ONES fitness of $k \in [0..n]$, then the bit at position $k+1$ is a 0 (if this position exists), and the bit values at positions larger than $k+1$ do not contribute to the fitness at all.

## C. Mathematical Tools

We carefully study how each frequency is updated over time in expectation, and then translate these values into bounds on

**Algorithm 1:** The *compact genetic algorithm* [6] with well-behaved hypothetical population size $\mu \in \mathbb{R}_{>0}$, maximizing a given pseudo-Boolean function *f*.

1. $t \leftarrow 0$;

2. $p^{(t)} \leftarrow (\frac{1}{2})_{i \in [n]}$;

3. **repeat**

4. $x^{(1,t)} \leftarrow \text{sample of } p^{(t)}$;

5. $x^{(2,t)} \leftarrow \text{sample of } p^{(t)}$;

6. $y^{(1,t)} \leftarrow x^{(1,t)}$;

7. $y^{(2,t)} \leftarrow x^{(2,t)}$;

8. **if** $f(x^{(1,t)}) < f(x^{(2,t)})$ **then**

9. $\lfloor$ swap $y^{(1,t)}$ and $y^{(2,t)}$;

10. **foreach** $i \in [n]$ **do**

11. $\lfloor p_i^{(t+1)} \leftarrow p_i^{(t)} + \frac{1}{\mu}(y_i^{(1,t)} - y_i^{(2,t)}) \rfloor$;

12. restrict $p^{(t+1)}$ to $[\frac{1}{n}, 1 - \frac{1}{n}]^n$;

13. $t \leftarrow t + 1$;

14. **until** termination criterion met;

hitting times for each frequency. The mathematical technique that formalizes this translation is called *drift analysis* [43], with *drift* referring to the expected change of the process. In particular, we make use of the following three theorems. We adjust their formulation to better suit our presentation.

The first theorem shows that it is unlikely for a random process whose progress is linearly proportional to its expected progress to not reach a certain value after a short time. This so-called *multiplicative-drift theorem* dates back to Doerr, Johannsen, and Winzen [44], with the concentration bound we utilize being first shown by Doerr and Goldberg [45].

**Theorem 1 (Multiplicative drift [43, Theorem 18]).** Let $(X_t)_{t \in \mathbb{N}}$ be a random process over $S \subseteq \mathbb{R}_{\ge 0}$ with $0 \in S$. Let $s_{\min} = \min(S \setminus \{0\})$, and let $T = \inf\{t \in \mathbb{N} \mid X_t = 0\}$. Assume that there is a $\delta \in \mathbb{R}_{>0}$ such that for all $t \in \mathbb{N}$ it holds that

$$ \mathbb{E}[X_t - X_{t+1} \mid X_t] \cdot \mathbf{1}\{t < T\} \ge \delta X_t \cdot \mathbf{1}\{t < T\}. $$

Then for all $r \in \mathbb{R}_{\ge 0}$, we have

$$ \Pr[T > \left\lfloor \frac{r + \ln(X_0/s_{\min})}{\delta} \right\rfloor \mid X_0] \le \exp(-r). $$

The following theorem shows that a random process that moves in expectation away from a target point $b \in \mathbb{R}_{>0}$ has a low probability of hitting it within a number of steps polynomial in $b$. The variant of this *negative-drift* theorem is due to Kötzing [46], who phrased it in a fashion that required the process to move away from the target in expectation at any point in time. The following version only requires this for an interval.

**Theorem 2 (Negative drift [47, Corollary 3.24]).** Let $(X_t)_{t \in \mathbb{N}}$ be a random process over $\mathbb{R}$. Moreover, let $X_0 \le 0$, let $b \in \mathbb{R}_{>0}$, and let $T = \inf\{t \in \mathbb{N} \mid X_t \ge b\}$. Suppose that there are values $a \in \mathbb{R}_{\le 0}$, $c \in (0, b)$, and $\varepsilon \in \mathbb{R}_{< 0}$ such that for all $t \in \mathbb{N}$ holds that

$$ (a) \mathbb{E}[X_{t+1} - X_t \mid X_t] \cdot \mathbf{1}\{X_t \ge a\} \le \varepsilon \cdot \mathbf{1}\{X_t \ge a\}, $$
(b) $|X_t - X_{t+1}| \cdot \mathbf{1}\{X_t \ge a\} < c$, and

(c) $X_{t+1} \cdot \mathbf{1}\{X_t < a\} \le 0$.

Then for all $t \in \mathbb{N}$, we have

$$ \mathrm{Pr}[T \le t] \le t^2 \cdot \exp\left(-\frac{b|\varepsilon|}{2c^2}\right). $$

The last theorem bounds the effect of genetic drift. That is, it shows that frequencies in the cGA do not get too low too quickly if the fitness function that is being optimized considers at each position a 1 at least as valuable as a 0 in terms of fitness. Formally, a fitness function $f$ weakly prefers $1s$ over $0s$ at position $i \in [n]$ if and only if for all $x, y \in \{0, 1\}^n$ that differ only in position $i$ such that $x_i = 1$ (and $y_i = 0$), we have $f(x) \ge f(y)$.

**Theorem 3 (Genetic drift [13, Corollary 2(2)])**. Consider the cGA with a well-behaved hypothetical population size $\mu \in \mathbb{R}_{>0}$ optimizing a fitness function $f$ that weakly prefers $1s$ over $0s$ at position $i \in [n]$. Then for all $\gamma \in \mathbb{R}_{>0}$ and all $T \in \mathbb{N}$ it holds that

$$ \mathrm{Pr} \left[ \forall t \in [0..T] : p_i^{(t)} > \frac{1}{2} - \gamma \right] \ge 1 - 2 \exp \left( - \frac{\gamma^2 \mu^2}{2T} \right). $$

## IV. RUNTIME ANALYSIS OF THE cGA ON LEADINGONES

Our main result is Theorem 4, which essentially proves that the cGA with $\mu = \Omega(n \log^2 n)$ maximizes LEADINGONES with high probability in $O(\mu n \log n)$ iterations. In particular, this runtime is minimized for $\mu = \Theta(n \log^2 n)$ and results in a runtime of $O(n^2 \log^3 n)$ with high probability. This bound is only worse by a factor of $O(\log^3 n)$ than the common $O(n^2)$ runtime bound of many other randomized search heuristics [7], and it is only worse by a factor of $O(\log^2 n)$ than the runtime of the EDA UMDA for a comparable parameter regime [12]. Notably, the cGA achieves this result while only having access to two samples in each iteration.

**Theorem 4.** Consider the cGA maximizing LEADINGONES with $n \ge 8$ and $\mu \ge 786 \exp(6)n \ln^2 n$. Then with a probability of at least $1 - \frac{4}{n}$, after $12 \exp(6)\mu n \ln n$ iterations, all frequencies are greater than $1 - \frac{3}{n}$ and remain that way for at least the next $12 \exp(6)\mu n \ln n$ iterations. Moreover, with a probability of at least $1 - \frac{5}{n}$, the algorithm finds the optimum of LEADINGONES within $24 \exp(6)\mu n \ln n$ iterations.

We note that we state and prove our main result only for $n \ge 8$. By excluding the small values $n \le 7$, we can work with explicit (though not optimized) constants, which increases the readability of the proof. We note that, trivially, the asymptotic statements made in the introduction hold for $n \le 7$; for this it suffices to see that from any state of the algorithm, with constant probability in a constant number of iterations the frequency vector $(1 - \frac{1}{n}, \dots, 1 - \frac{1}{n})$ is reached, namely by always sampling the all-ones and the all-zeros vector.

We now turn to the more interesting case that $n$ is large, for which $n \ge 8$ suffices here. Our analysis considers the cGA in the parameter regime with low genetic drift. Genetic drift refers to the effect that a frequency at position $i \in [n]$ is shifted over time based solely on the random order of the bit values at position $i$ of the samples, that is, without

the fitness function biasing the ranking. This occurs regularly when optimizing LEADINGONES, as bits after the first 0 do not affect the ranking of the samples. This leads to random updates of frequencies. However, in the regime of low genetic drift, this effect is negligible (Lemma 5). This is achieved by choosing $\mu$ to be sufficiently large. Formally, we rely on Theorem 3, which bounds with high probability the total negative offset a frequency receives.

By relying on the impact of genetic drift being low, our analysis proceeds by showing that the frequencies are increased sequentially until they reach values close to $1 - \frac{1}{n}$. Moreover, while it is unlikely for a frequency to remain exactly at $1 - \frac{1}{n}$, we show that it does not go below $1 - \frac{3}{n}$ with high probability before the optimum is sampled (Lemma 6). This motivates the definition of the critical position $i \in [n]$, which is (for each iteration) the smallest position in $[n]$ whose frequency is below $1 - \frac{3}{n}$. The main idea of our analysis is to show inductively that the critical position increases with high probability after $O(\mu \log n)$ iterations (Lemma 7). Since it can be increased at most $n$ times, the frequency vector is close to the all-1s vector with high probability after $O(\mu n \log n)$ iterations. Afterward, the optimum is sampled with high probability within $O(\log n)$ iterations, yielding our main result.

In the following, we formalize these steps in different lemmas before we prove our main result.

The following lemma shows that the impact of genetic drift is low, implying that all frequencies remain with high probability greater than $\frac{1}{4}$ for the duration of the optimization.

**Lemma 5.** Consider the cGA maximizing LEADINGONES with $\mu \ge 786 \exp(6)n \ln^2 n$. Then the probability that all frequencies are greater than $\frac{1}{4}$ in the first $12 \exp(6)\mu n \ln n$ iterations is at least $1 - \frac{2}{n}$.

*Proof.* We aim at applying Theorem 3 for $T := 12 \exp(6)\mu n \ln n$. We observe that LEADINGONES weakly prefers $1s$ over $0s$ for each position. Thus, Theorem 3 yields

$$ \mathrm{Pr} \left[ \forall t \in [0..T] : p_i^{(t)} > \frac{1}{4} \right] \ge 1 - 2 \exp \left( - \frac{\mu}{384 \exp(6) n \ln n} \right) $$

for all $i \in [n]$. Hence, as $\mu \ge 768 \exp(6)n \ln^2 n$, we observe that

$$ \mathrm{Pr} \left[ \forall t \in [0..T] : p_i^{(t)} > \frac{1}{4} \right] \ge 1 - 2 \exp(-2 \ln n) \\ = 1 - \frac{2}{n^2}. $$

The result follows by applying the union bound over all $n$ frequencies, hence adding their respective failure probabilities of $\frac{2}{n^2}$. $\square$

Next, we show that if a frequency $p_i$ is at its maximum value of $1 - \frac{1}{n}$ and all preceding frequencies $p_j$ with $j \in [i - 1]$ are at similarly high values, then $p_i$ also remains, with high probability, close to its maximum value for the duration of the optimization.

**Lemma 6.** Consider the cGA maximizing LEADINGONES with $n \ge 8$ and $\mu \ge 786 \exp(6)n \ln^2 n$, and let $i \in [2..n]$. Assume that at some iteration $t_0$ the frequency at position $i$ is
1 - 1/n and the first i - 1 frequencies stay above 1 - 3/n during the next T₀ := 12 exp(6)(2n - i + 1)µ ln n iterations. Then, with a probability of at least 1 - 1/n³, for the next T₀ iterations, the frequency at position i stays above 1 - 3/n.

The proof of this lemma is somewhat technical as it needs
a clever application of the negative drift theorem (Theorem 2)
to the value of the *i*-th frequency. To be able to apply this
drift theorem and to obtain the best possible estimates, we
twice modify the stochastic process. The first modification is
of a technical nature and only changes the process so that it
also exhibits the desired properties after the time interval in
which the *i*-th frequency is above 1 - 3/n. This does not change
the length of this time interval, so it does not influence our
estimates, but this is necessary since the negative drift theorem
requires the conditions to be fulfilled at each time step.

The second modification is more interesting. We note that when the *i*-th frequency is close to 1 - 1/n, then with high probability it does not change, simply because both samples contain a one in the *i*-th position. This high rate of iterations with no change reduces the drift, but has little other effect. Consequently, by regarding the process only consisting of steps in which the *i*-th frequency changes, we obtain an essentially identical process, but with much stronger drift (this is the absolute value of ε in Theorem 2); for this process, the negative drift theorem gives much stronger estimates.

We note that these challenges did not appear in the analysis
of how the UMDA optimizes LEADINGONES [12], because
there the higher selection rate (which could be obtained from
the sample size larger than two) ensured that frequencies to
the left of the critical frequency always stayed at 1 - 1/n.

Proof. To ease the notation, we assume that $t_0 = 0$, that is, we artificially start the cGA with the situation assumed in the lemma at time $t_0$. Our goal is to apply Theorem 2 to the $i$-th frequency. We denote the stochastic process describing the run of the original cGA by $P$. Let $T$ be the number of iterations until the first time when the $i$-th frequency hits or goes below $1 - \frac{3}{n}$.

We first modify P so that we can show the assumptions
of Theorem 2 also after time T₀. This modified process P' is
defined as follows. Until iteration T₀, the processes P and P'
are identical. Afterwards, the frequency update of the cGA –
different from its original definition – does not change the first
i − 1 frequencies, but only updates the i-th frequency and the
higher ones. Let T' be the hitting time in P' that corresponds
to T in P (that is, the first time the i-th frequency in P' hits
or goes below 1 − 3/n). As for the first T₀ iterations P and P'
act identically, we have Pr[T' ≤ T₀] = Pr[T ≤ T₀]. On the
positive side, the process P' by construction satisfied that the
first i − 1 frequencies always stay above 1 − 3/n.

To increase the drift, that is, the absolute value of ε in the
application of Theorem 2, we modify the process a second
time by ignoring time steps in which the i-th frequency does
not change in P'. Formally speaking, the process P'' consists
of the initial state of P' and then only of those states of P'
in which the i-th frequency has a value different from the
previous state. Let T'' be the corresponding hitting time in
P'' and p'' the corresponding frequency vector. Since P'' is

a subsequence of the states of P' which contains all states in
which for the first time a particular value of the i-th frequency
is reached, we have T'' ≤ T' and hence Pr[T' ≤ T₀] ≤
Pr[T'' ≤ T₀]. Thus, we aim to prove a probabilistic bound on
T''.

To fit our process to the setting of Theorem 2, we define
(Y)ₜ as Yₜ = 1 - p''(t) - 1/n - 1/μ. We aim at showing that the
probability of (Y) hitting a state 2/n - 1/μ within T₀ iterations
is smaller than 1/n³. To that end, we use the framework from
Theorem 2. In our setting, the variable a from the theorem
statement is 0 and the variable b is 2/n - 1/μ. We verify that the
conditions (a) to (c) hold.

(a) We show that there exists ε < 0 such that for all points in time t < T'' we have

$$
E[(Y_{t+1} - Y_t) | Y_t] \cdot \mathbf{1}\{Y_t \ge 0\} \le \varepsilon \cdot \mathbf{1}\{Y_t \ge 0\}.
$$

For $Y_t < 0$, the inequality reduces to $0 \le 0$. We now
focus on times $t$ when $Y_t \ge 0$. In those cases, $(Y)$
changes either by $\frac{1}{\mu}$ or $-\frac{1}{\mu}$. Therefore, the search points
sampled by the cGA at the iteration corresponding to
point $t$ in the modified process differ at the $i$-th index.
Also, any bias to the update is introduced only when the
first $i-1$ bits in both search points are ones. Otherwise,
it is equally probable to increment or decrement the
$i$-th frequency, as for each pair of search points that
increments this frequency there exists a pair of search
points that decrements this frequency. Thus

$$
\begin{align*}
E[Y_{t+1} - Y_t | Y_t] &= -\frac{1}{\mu} \prod_{j=1}^{i-1} (p_j''(t))^2 \\
&\leq -\frac{1}{\mu} \left(1 - \frac{3}{n}\right)^{2(i-1)} \\
&\leq -\frac{1}{\mu} \left(1 - \frac{3}{n}\right)^{2(n-1)}.
\end{align*}
$$

We observe that the last expression decreases with $n$
increasing. Hence for $n \ge 8$, we have

$$
-\frac{1}{\mu} \left(1 - \frac{3}{n}\right)^{2(n-1)} \leq -\frac{1}{\mu} \left(1 - \frac{3}{8}\right)^{14} \leq -\frac{\exp(-6)}{2\mu}.
$$

Hence it suffices to set the value to of ε to − exp(−6) / 2μ to
satisfy condition (a).

(b) We show that there exists a constant c such that for all points in time t < T'', we have |Y_t - Y_{t+1}| · 1{Y_t ≥ 0} < c. For times t when Y_t < 0, the inequality reduces to 0 < c. For times t when Y_t ≥ 0, at each discrete step (Y) changes either by 1/μ or − 1/μ, so setting c to 2/μ suffices.

(c) We show that for all points in time $t < T''$, we have $Y_{t+1} \cdot 1\{Y_t < 0\} \le 0$. Observe that if $Y_t < 0$, then $Y_t = -\frac{1}{\mu}$. Thus, $Y_{t+1} \le 0$, as a frequency changes at most by $\frac{1}{\mu}$ in each iteration.

With conditions (a) to (c), Theorem 2 yields

$$
\mathrm{Pr}[T'' \le T_0] \le T_0^2 \exp \left( - \frac{\mu \left( \frac{2}{n} - \frac{1}{\mu} \right) \exp(-6)}{16} \right)
$$
$$
\begin{align*}
&\le (12 \exp(6)(2n - i + 1)\mu \ln n)^2 \\
&\qquad \cdot \exp\left(-\frac{\mu\left(\frac{2}{n} - \frac{1}{\mu}\right)\exp(-6)}{16}\right) \\
&\le (24 \exp(6)\mu n \ln n)^2 \exp\left(-\frac{\mu\left(\frac{2}{n} - \frac{1}{\mu}\right)\exp(-6)}{16}\right).
\end{align*}
$$

As $\mu > n$, we obtain

$$
\begin{align*}
\Pr[T'' \le T_0] \\
&\le (24 \exp(6) \mu n \ln n)^2 \exp\left(-\frac{\mu \exp(-6)}{16n}\right) \\
&= 576 \exp(12) \mu^2 n^2 \ln^2 n \exp\left(-\frac{\mu \exp(-6)}{16n}\right).
\end{align*}
$$

Thus considering $\mu \ge 786 \exp(6)n \ln^2 n$ we get

$$
\begin{align*}
\Pr[T'' \le T_0] \\
&\le 576 \cdot 786^2 \exp(24) n^4 \ln^6 n \exp(-49.125 \ln^2 n) \\
&\le 576 \cdot 786^2 \exp(24) n^4 \ln^6 n \exp(-49 \ln^2 n)
\end{align*}
$$

Since $n \ge 8$ we have $\ln n > 1$, we can estimate

$$
\begin{align*}
\Pr[T'' \le T_0] \\
&\le 576 \cdot 786^2 \exp(24) n^4 \ln^6 n \exp(-49 \ln n) \\
&\le \frac{576 \cdot 786^2 \exp(24) n^4 \ln^6 n}{n^{49}},
\end{align*}
$$

which is easily seen to be smaller than $\frac{1}{n^3}$ for $n \ge 8$. As we
showed in the beginning, the same probability bound holds
for $T$, which concludes the proof. $\square$

The next lemma shows that the frequency of the critical po-
sition reaches its maximum value within O(µ log n) iterations.
This is again very different from the UMDA, where the larger
sample size and the higher selection rate allowed to move this
frequency to the desired value in a single iteration [12].

The key to the proof of this lemma is observing that the
distance of the critical frequency to the ideal value of one
exhibits a multiplicative drift behavior, that is, the frequency
moves up with expected speed proportional to the current
distance (when, as assumed here, the frequency is at least
some constant, here $\frac{1}{4}$).

**Lemma 7.** Consider the cGA maximizing LEADINGONES with $n \ge 8$ and $\mu \ge 786 \exp(6)n \ln^2 n$, and let $i \in [0..n-1]$. Assume that at some iteration $t_0$ the frequency at position $i+1$ is at least $\frac{1}{4}$, the first $i$ frequencies are greater than $1-\frac{3}{n}$, and this condition also holds for the next $T_0 := 12 \exp(6)\mu \ln n$ iterations. Then, with a probability of at least $1-\frac{1}{n^2}$, the frequency at position $i+1$ reaches $1-\frac{1}{n}$ in the next $T_0$ iterations.

Proof. Again, to ease the notation we assume that $t_0$ is zero, that is, the process is artificially started in the state assumed in the lemma.

Our goal is to apply Theorem 1 to the (i + 1)-st frequency.
We denote the process corresponding to the cGA as P. Let T

be the number of iterations until the first time when the (i+1)-st frequency hits 1 - 1/n. As in the previous lemma, to use Theorem 1 we need that our process exhibits a suitable drift throughout its runtime and not just for T₀ iterations. Hence as there, we artificially modify the process to ensure this property, and this in a way that it does not interfere with what we want to show. Hence let P' be the following process. P and P' are identical until iteration T₀. Afterwards the first i frequencies in P' do not change anymore, whereas the (i+1)-st frequency and the higher frequencies are updated as in the definition of the cGA. Let T' be the corresponding first-hitting time in P' and p' the corresponding frequency vector in P'. Observe that as for the first T₀ iterations P and P' act identically, Pr[T' < T₀] = Pr[T < T₀]. Thus we now prove a probabilistic bound on T'.

To fit our process to the setting of Theorem 1, we define
a sequence of random variables (X)<sub>t</sub> by X<sub>t</sub> = 1 - p'<sub>i+1</sub><sup>(t)</sup> if
p'<sub>i+1</sub><sup>(t)</sup> ≠ 1 - 1/n and X<sub>t</sub> = 0 otherwise. With this definition,
T' is the first time this sequence hits zero. We now show
that this process exhibits a multiplicative drift as required in
Theorem 1.

Let $x_1, x_2$ be the offspring sampled by the cGA in some
iteration and $y_1, y_2$ the offspring after the possible swap. As
in Lemma 6, the expected change of the (i + 1)-st frequency
is non-zero only if both $x_1$ and $x_2$ start with i ones and differ
in the (i + 1)-st position. Recalling that $X_{i+1,t} = 1 - p'_{i+1}$,
we deduce that

$$
\begin{align*}
& \mathrm{E}[X_{i+1,t} - X_{i+1,t+1} | X_{i+1,t}] \\
&= \frac{2}{\mu} \left( \prod_{j=1}^{i} (p'_{j}(t))^{2} \right) p'_{i+1}(1 - p'_{i+1}(t)) \\
&= \frac{2X_{i+1,t}}{\mu} \left( \prod_{j=1}^{i} (p'_{j}(t))^{2} \right) p'_{i+1}(1 - \frac{3}{n})^{2i} \\
&\geq \frac{X_{i+1,t}}{2\mu} \left( 1 - \frac{3}{n} \right)^{2i}.
\end{align*}
$$

As in Lemma 6, we use the fact that for $n \ge 8$, we have
$(1 - \frac{3}{n})^{2(n-1)} > \frac{\exp(-6)}{2}$, and obtain

$$
\begin{align*}
\mathrm{E}[X_{i+1,t} - X_{i+1,t+1} | X_{i+1,t}] \\
\geq \frac{X_{i+1,t} \exp(-6)}{4\mu}.
\end{align*}
$$

We apply Theorem 1 and obtain, for any $r \in \mathbb{R}_{\ge 0}$, that

$$
\Pr \left[ T' > 4\mu \left( \frac{r + \ln\left(\frac{3n}{4}\right)}{\exp(-6)} \right) + 1 \right] \le \exp(-r).
$$

Setting $r := 2 \ln n$ we get

$$
\begin{align*}
\frac{1}{n^2} &\ge \Pr \left[ T' > 4\mu \left( \frac{2 \ln(n) + \ln\left(\frac{3n}{4}\right) + \frac{\exp(-6)}{4\mu}}{\exp(-6)} \right) \right] \\
&\ge \Pr \left[ T' > 4\mu \left( \frac{3 \ln n}{\exp(-6)} \right) \right] = \Pr[T' > T_0].
\end{align*}
$$

As we showed before, the same probabilistic bound
for $T$. This finishes the proof. $\square$
When counting function evaluations, the result above shows a slighter slower model update for the cGA than what could be shown for the UMDA in [12]. Above, we have seen that the cGA within $O(\mu \log n)$ iterations, hence with $O(\mu \log n)$ samples, moves the critical frequency to the upper border. In [12], it was shown that a single iteration, hence $\Theta(\mu)$ samples, suffices for the UMDA with $\mu = \Omega(n \log n)$ and $\lambda = \Theta(\mu)$ a suitable constant factor larger than $\mu$. While the roles of $\mu$ are not perfectly comparable in both algorithms, they are quite similar, in particular, the same value of $\mu$ in both algorithms leads to comparable genetic drift. For the particular results shown here and in [12], the UMDA can even work with a slightly smaller value of $\mu$, namely $\mu = \Theta(n \log n)$, whereas we assume $\mu = \Omega(n \log^2 n)$. This difference is caused by the longer runtime needed on our result, which requires a weaker genetic drift.

Overall, our analysis suggests that the model update of the cGA allows for slightly slower model adjustments. From looking at our proof, we feel that the true reason for this effect is that fact that the cGA changes a frequency only when it samples two different values. Hence moving a frequency from very close to the optimal value to the optimal value itself takes many samples for the cGA, whereas the UDMA does this modification very easily.

Last, we combine Lemmas 5 to 7 inductively and prove our main result.

**Proof of Theorem 4.** We aim at showing that with high probability the critical position increases at least each $12 \exp(6) \mu \ln n$ iterations, and that when all frequencies are greater than $1 - \frac{3}{n}$, the optimum is sampled quickly. We proceed by induction on the frequencies. Formally, we prove that for every frequency (indexed by $i \in [n]$), with a probability of at least $(1 - \frac{2}{n})(1 - \frac{1}{n^2})^i (1 - \frac{1}{n^3})^i$, there exists an iteration $T_i \le 12 \exp(6) i \mu \ln n$ for which

(i) the first $i-1$ frequencies are greater than $1 - \frac{3}{n}$,

(ii) the $i$-th frequency is $1 - \frac{1}{n}$, and

(iii) the first $i$ frequencies remain greater than $1 - \frac{3}{n}$ for the next $12 \exp(6)(2n - i + 1) \mu \ln n$ iterations.

(iv) All the frequencies remain greater than $\frac{1}{4}$ for the first $12 \exp(6) \mu n \ln n$ iterations.

We observe that the fourth property is a direct result of Lemma 5 and holds with a probability of at least $1 - \frac{2}{n}$, regardless of the frequency considered. Thus, we do not mention it explicitly anymore but include it in the total probability.

Consider the first frequency from the start of the algorithm on, that is, we regard the case $i=1$. By Lemma 7, it reaches $1 - \frac{1}{n}$ within $12 \exp(6) \mu \ln n$ iterations with a probability of at least $1 - \frac{1}{n^2}$. At the iteration when it reaches $1 - \frac{1}{n}$, by Lemma 6, it remains greater than $1 - \frac{3}{n}$ for the next $12 \exp(6)(2n - i + 1) \mu \ln n$ iterations with a probability of at least $1 - \frac{1}{n^3}$. Thus, this iteration fulfills all properties to be $T_1$.

We assume that for some $i \in [n-1]$, $T_i$ exists with a probability of at least $(1 - \frac{2}{n})(1 - \frac{1}{n^2})^i (1 - \frac{1}{n^3})^i$. We show that with a probability of at least $(1 - \frac{2}{n})(1 - \frac{1}{n^2})^{i+1} (1 - \frac{1}{n^3})^{i+1} T_{i+1}$ exists. By Property (iii) of $T_i$, the conditions for Lemma 7 are fulfilled at iteration $T_i$, thus with a probability of at least

$1 - \frac{1}{n^2}$, so a total probability of at least $(1 - \frac{2}{n})(1 - \frac{1}{n^2})^{i+1} (1 - \frac{1}{n^3})^i$, the $i+1$-st frequency reaches $1 - \frac{1}{n}$ within the next $12 \exp(6) \mu \ln n$ iterations. Furthermore, when that happens, by Lemma 6, with a probability of at least $1 - \frac{1}{n^3}$, so a total probability of $(1 - \frac{2}{n})(1 - \frac{1}{n^2})^{i+1} (1 - \frac{1}{n^3})^{i+1}$, the first $i+1$ frequencies remain greater than $1 - \frac{3}{n}$ for the next $12 \exp(6)(2n-i) \mu \ln n$ iterations. Thus, this time is the desired iteration $T_{i+1}$:

(i) the first $i$ frequencies are greater than $1 - \frac{3}{n}$ due to Property (iii) for $T_i$,

(ii) the $i+1$-st frequency is equal to $1 - \frac{1}{n}$ by definition,

(iii) the first $i+1$ frequencies remain greater than $1 - \frac{3}{n}$ for the next $12 \exp(6)(2n-i) \mu \ln n$ iterations.

Therefore, by induction, with a probability of at least $(1 - \frac{2}{n})(1 - \frac{1}{n^2})^n (1 - \frac{1}{n^3})^n$, there exists an iteration $T_n \le 12 \exp(6) \mu n \ln n$.

We observe that from iteration $T_n$ onwards, it is guaranteed that for another $12 \exp(6)(n+1) \mu \ln n$ iterations all frequencies remain greater than $1 - \frac{3}{n}$, i.e., the probabilistic model of the cGA is very close to the optimum. By applying Bernoulli's inequality multiple times we obtain a lower bound on the derived probability: $(1 - \frac{2}{n})(1 - \frac{1}{n^2})^n (1 - \frac{1}{n^3})^n \ge (1 - \frac{2}{n})(1 - \frac{1}{n})(1 - \frac{1}{n^2}) \ge (1 - \frac{2}{n})(1 - \frac{1}{n})^2 \ge (1 - \frac{2}{n})^2 \ge 1 - \frac{4}{n}$. This finishes the proof of the first statement in the theorem. To prove the second statement, we observe that at each iteration in which all frequencies are at least $1 - \frac{3}{n}$, the probability of sampling an optimum is at least $(1 - \frac{3}{n})^n \ge (1 - \frac{3}{8})^8 \ge 0.02$, using $n \ge 8$ again, so the probability of sampling an optimum in the next $50 \ln n \le 12 \exp(6)(n+1) \mu \ln n$ iterations is at least $1 - (1 - 0.02)^{50 \ln n} \ge 1 - e^{-50 \ln n} = 1 - \frac{1}{n}$. This yields a total success probability of at least $(1 - \frac{4}{n})(1 - \frac{1}{n}) \ge 1 - \frac{5}{n}$. This finishes the proof. $\square$

**Lessons from the analysis:** We observe that the proof of our main result is significantly more involved than the proof of the corresponding result for the UMDA [12]. The reason is that indeed the optimization process is more complex for the cGA. To see this, consider the situation that the current frequency vector $p$ is such that the first $\ell = \Theta(n)$, $\ell < n$, frequencies are equal to $1 - \frac{1}{n}$, that is, they are at the upper border. In this situation, a sample $x$ has $\ell$ leading ones with probability $(1 - \frac{1}{n})^\ell \ge (1 - \frac{1}{n})^{n-1} \ge \frac{1}{e}$. Consequently, when the sample size of the UMDA is sufficiently large (and this is necessary anyway to be in the low-genetic-drift regime) and the selection rate is a constant smaller than $\frac{1}{e}$, the frequency update of the UMDA with high probability only depends on samples with $\ell$ leading ones, that is, the new frequency vector again has the first $\ell$ frequencies at the upper border. Consequently, an initial segment of frequencies at the upper border stays at this border for a long time, and the runtime analysis only has to care about how the critical frequency is moving to the upper border of the frequency range.

In contrast, due to the small sample size of two, the cGA does not observe such a stable optimization behavior. In fact, in the above situation, we see that with constant probability, the two offspring sampled by the cGA are such that both have a single zero in the first $\ell$ bits, and these are at different locations $i < j$. In this case, the frequency update favors the bit values
of the sample having the zero on position *j*, which means that the *j*-th frequency is moving from $1 - \frac{1}{n}$ to $1 - \frac{1}{n} - \frac{1}{\mu}$. Hence with constant probability, a frequency of the previously perfect initial segment is moving into the wrong direction. In consequence, these frequencies do not all stay at the upper border, but a constant fraction of them is strictly below it.

We cope with this difficulty by showing that, despite the effect just described, there is still a drift of the frequencies towards the upper border, ensuring that a single frequency $p_i$ with high probability does not go below $1 - \frac{3}{n}$ (Lemma 6). This drift only is strong enough when the previous $i-1$ frequencies are close to the upper border, which is why Lemma 6 takes this assumption and why our main proof requires the slightly technical induction.

The additional technicality of our proof, the slightly weaker bound we obtain, and the above considerations suggest that the UMDA with its larger sample size allows for a more stable and (slightly) more efficient optimization process. This could be a reason why the UMDA is more often used in practical applications.

At the same time, we note that our result also shows that the cGA can cope with this slightly less stable optimization process. Our bounds are by a polylogarithmic factor worse than the bounds for the UMDA, which is a small discrepancy, and given we have no matching lower bound, it is not even clear if there is a discrepancy at all.

## V. CONCLUSION

This work conducts the first runtime analysis for the cGA on the LEADINGONES benchmark, which was a result so far missing among the runtime analyses of classic univariate EDAs on classic, simple benchmark problems. Our analysis detects some additional difficulties compared to the optimization of this benchmark via the UMDA. We overcome these with a more complex proof and finally show a runtime guarantee only slightly inferior to the one of the UMDA. On the positive side, this result shows that also the simple cGA (having a single parameter only) is able to optimize LEADINGONES. However, our result also suggests that the smaller sample size of the cGA can be a disadvantage, and that more complex algorithms like the UMDA (having two parameters) might be more successful (with the right parameters).

From comparing our proof with the one for the UMDA in [12], we observe some structural differences in the working principles of the cGA and the UMDA. This is noteworthy since in most existing results, the two algorithms seemed to behave very similarly.

The biggest open problem stemming from this work is proving a matching lower bound for our result, which is generally a hard problem for EDAs. Such a bound would answer the question whether the differences in the algorithms truly lead to a different asymptotic runtime (with the difference at most being a polylogarithmic factor), or whether the two algorithms despite different working principles actually are equally efficient.

## REFERENCES

[1] M. Pelikan, M. Hauschild, and F. G. Lobo, "Estimation of distribution algorithms," in Springer Handbook of Computational Intelligence, J. Kacprzyk and W. Pedrycz, Eds. Springer, 2015, pp. 899-928.

[2] J. Kacprzyk and W. Pedrycz, Eds., Springer Handbook of Computational Intelligence. Springer, 2015.

[3] A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing, 2nd ed. Springer, 2015.

[4] M. Krejca and C. Witt, "Theory of estimation-of-distribution algorithms," in Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, B. Doerr and F. Neumann, Eds. Springer, 2020, pp. 405-442, also available at https://arxiv.org/abs/1806.05392.

[5] S. Droste, "A rigorous analysis of the compact genetic algorithm for linear functions," Natural Computing, vol. 5, pp. 257-283, 2006.

[6] G. R. Harik, F. G. Lobo, and D. E. Goldberg, "The compact genetic algorithm," IEEE Transactions on Evolutionary Computation, vol. 3, pp. 287-297, 1999.

[7] B. Doerr and F. Neumann, Eds., Theory of Evolutionary Computation—Recent Developments in Discrete Optimization. Springer, 2020, also available at http://www.lix.polytechnique.fr/Labo/Benjamin.Doerr/doerr_neumann_book.html.

[8] D. Dang and P. K. Lehre, "Simplified runtime analysis of estimation of distribution algorithms," in Genetic and Evolutionary Computation Conference, GECCO 2015. ACM, 2015, pp. 513-518.

[9] H. Mühlenbein and G. Paass, "From recombination of genes to the estimation of distributions I. Binary parameters," in Parallel Problem Solving from Nature, PPSN 1996. Springer, 1996, pp. 178-187.

[10] T. Chen, K. Tang, G. Chen, and X. Yao, "Analysis of computational time of simple estimation of distribution algorithms," IEEE Transactions on Evolutionary Computation, vol. 14, pp. 1-22, 2010.

[11] D. Dang, P. K. Lehre, and P. T. H. Nguyen, "Level-based analysis of the univariate marginal distribution algorithm," Algorithmica, vol. 81, pp. 668-702, 2019.

[12] B. Doerr and M. S. Krejca, "A simplified run time analysis of the univariate marginal distribution algorithm on LeadingOnes," Theoretical Computer Science, vol. 851, pp. 121-128, 2021.

[13] B. Doerr and W. Zheng, "Sharp bounds for genetic drift in estimation-of-distribution algorithms," IEEE Transactions on Evolutionary Computation, vol. 24, pp. 1140-1149, 2020.

[14] H. Mühlenbein, "How genetic algorithms really work: mutation and hillclimbing," in Parallel Problem Solving from Nature, PPSN 1992. Elsevier, 1992, pp. 15-26.

[15] S. Droste, T. Jansen, and I. Wegener, "On the analysis of the (1+1) evolutionary algorithm," Theoretical Computer Science, vol. 276, pp. 51-81, 2002.

[16] T. Jansen, K. A. D. Jong, and I. Wegener, "On the choice of the offspring population size in evolutionary algorithms," Evolutionary Computation, vol. 13, pp. 413-440, 2005.

[17] C. Witt, "Runtime analysis of the $(\mu + 1)$ EA on simple pseudo-Boolean functions," Evolutionary Computation, vol. 14, pp. 65-86, 2006.

[18] T. Jansen and I. Wegener, "A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation," Theoretical Computer Science, vol. 386, pp. 73-93, 2007.

[19] J. E. Rowe and D. Sudholt, "The choice of the offspring population size in the $(1, \lambda)$ evolutionary algorithm," Theoretical Computer Science, vol. 545, pp. 20-38, 2014.

[20] D. Antipov and B. Doerr, "A tight runtime analysis for the $(\mu + \lambda)$ EA," Algorithmica, vol. 83, pp. 1054-1095, 2021.

[21] B. Doerr, T. El Ghazi El Houssaini, A. Rajabi, and C. Witt, "How well does the Metropolis algorithm cope with local optima?" in Genetic and Evolutionary Computation Conference, GECCO 2023. ACM, 2023, pp. 1000-1008.

[22] D. Sudholt and C. Witt, "On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization," Algorithmica, vol. 81, pp. 1450-1489, 2019.

[23] J. Lengler, D. Sudholt, and C. Witt, "The complex parameter landscape of the compact genetic algorithm," Algorithmica, vol. 83, pp. 1096-1137, 2021.

[24] T. Friedrich, T. Kötzing, M. S. Krejca, and A. M. Sutton, "The compact genetic algorithm is efficient under extreme Gaussian noise," IEEE Transactions on Evolutionary Computation, vol. 21, pp. 477-490, 2017.

[25] W. Zheng and B. Doerr, "From understanding genetic drift to a smart-restart mechanism for estimation-of-distribution algorithms," Journal of Machine Learning Research, vol. 24, pp. 1-40, 2023.
[26] T. Friedrich, T. Kötzing, F. Neumann, and A. Radhakrishnan, “Theoretical study of optimizing rugged landscapes with the cGA,” in *Parallel Problem Solving from Nature, PPSN 2022, Part II*. Springer, 2022, pp. 586–599.

[27] V. Hasenöhrl and A. M. Sutton, “On the runtime dynamics of the compact genetic algorithm on jump functions,” in *Genetic and Evolutionary Computation Conference, GECCO 2018*. ACM, 2018, pp. 967–974.

[28] B. Doerr, “The runtime of the compact genetic algorithm on Jump functions,” *Algorithmica*, vol. 83, pp. 3059–3107, 2021.

[29] T. Jansen and I. Wegener, “The analysis of evolutionary algorithms – a proof that crossover really can help,” *Algorithmica*, vol. 34, pp. 47–66, 2002.

[30] C. Witt, “How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys,” *Theoretical Computer Science*, vol. 940, pp. 18–42, 2023.

[31] ——, “Domino convergence: why one should hill-climb on linear functions,” in *Genetic and Evolutionary Computation Conference, GECCO 2018*. ACM, 2018, pp. 1539–1546.

[32] ——, “Tight bounds on the optimization time of a randomized search heuristic on linear functions,” *Combinatorics, Probability & Computing*, vol. 22, pp. 294–318, 2013.

[33] B. Doerr and M. Kümnemann, “Optimizing linear functions with the (1+λ) evolutionary algorithm—different asymptotic runtimes for different instances,” *Theoretical Computer Science*, vol. 561, pp. 3–23, 2015.

[34] G. Rudolph, *Convergence Properties of Evolutionary Algorithms*. Verlag Dr. Kováč, 1997.

[35] S. Böttcher, B. Doerr, and F. Neumann, “Optimal fixed and adaptive mutation rates for the LeadingOnes problem,” in *Parallel Problem Solving from Nature, PPSN 2010*. Springer, 2010, pp. 1–10.

[36] D. Sudholt, “A new method for lower bounds on the running time of evolutionary algorithms,” *IEEE Transactions on Evolutionary Computation*, vol. 17, pp. 418–435, 2013.

[37] B. Doerr, “Analyzing randomized search heuristics via stochastic domination,” *Theoretical Computer Science*, vol. 773, pp. 115–137, 2019.

[38] F. Ben Jedidia, B. Doerr, and M. S. Krejca, “Estimation-of-distribution algorithms for multi-valued decision variables,” *Theoretical Computer Science*, vol. 1003, p. 114622, 2024.

[39] S. Adak and C. Witt, “Runtime analysis of a multi-valued compact genetic algorithm on generalized OneMax,” in *Parallel Problem Solving from Nature, PPSN 2024, Proceedings, Part III*, 2024, pp. 53–69.

[40] P. K. Lehre and P. T. H. Nguyen, “Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes,” *Algorithmica*, vol. 83, pp. 3238–3280, 2021.

[41] B. Doerr and M. S. Krejca, “Significance-based estimation-of-distribution algorithms,” *IEEE Transactions on Evolutionary Computation*, vol. 24, pp. 1025–1034, 2020.

[42] A. D. Ajimakin and V. S. Devi, “The competing genes evolutionary algorithm: Avoiding genetic drift through competition, local search, and majority voting,” *IEEE Transactions on Evolutionary Computation*, vol. 27, pp. 1678–1689, 2022.

[43] J. Lengler, “Drift analysis,” in *Theory of Evolutionary Computation: Recent Developments in Discrete Optimization*, B. Doerr and F. Neumann, Eds. Springer, 2020, pp. 89–131, also available at https://arxiv.org/abs/1712.00964.

[44] B. Doerr, D. Johannsen, and C. Winzen, “Multiplicative drift analysis,” *Algorithmica*, vol. 64, pp. 673–697, 2012.

[45] B. Doerr and L. A. Goldberg, “Adaptive drift analysis,” *Algorithmica*, vol. 65, pp. 224–250, 2013.

[46] T. Kötzing, “Concentration of first hitting times under additive drift,” *Algorithmica*, vol. 75, pp. 490–506, 2016.

[47] M. S. Krejca, “Theoretical analyses of univariate estimation-of-distribution algorithms,” Ph.D. dissertation, Universität Potsdam, 2019.

<figure><img src="image_2.png" /></figure>

Marcel Chwiałkowski is currently pursuing the B.Sc. degree in Mathematics and Computer Science at École Polytechnique, France.

<figure><img src="image_3.png" /></figure>

Benjamin Doerr received the Diploma, Ph.D., and Habilitation degrees in mathematics from the Christian-Albrechts-Universität zu Kiel, Kiel, Germany, in 1998, 2000, and 2005, respectively. He is a Full Professor (professeur de classe exceptionnelle) with the École Polytechnique, Palaiseau, France. From 2005 to 2013, he was a Senior Researcher (tenured) with the Max Planck Institute for Informatics, Saarbrücken, Germany, and an Adjunct Professor with Saarland University, Saarbrücken. His research interests include mathematical analyses of problem-specific algorithms and randomized search heuristics as well as the development of new algorithms based on such analyses.

Prof. Doerr is an Editor of several scientific journals, among them, Artificial Intelligence, Journal of Complexity, and Natural Computing.

<figure><img src="image_4.png" /></figure>

Martin S. Krejca received the B.Sc. and M.Sc. degree from the University of Jena, Jena, Germany, in 2012 and 2014, respectively, and the Ph.D. degree from the Hasso Plattner Institute, University of Potsdam, Potsdam, Germany, in 2019. He has been an Assistant Professor with École Polytechnique, Palaiseau, France, since 2022. His research interests are the theoretical analysis of randomized processes, especially black-box optimization heuristics.