pith. sign in

arxiv: 1906.09047 · v2 · pith:MKZLRGBLnew · submitted 2019-06-21 · 💻 cs.NE · cs.DS· math.PR

Sharp Bounds on the Runtime of the (1+1) EA via Drift Analysis and Analytic Combinatorial Tools

Hsien-Kuei Hwang , Carsten Witt This is my paper

Pith reviewed 2026-05-25 18:39 UTC · model grok-4.3

classification 💻 cs.NE cs.DSmath.PR
keywords (1+1) EAOneMaxdrift analysisexpected runtimeasymptotic expansionruntime analysisevolutionary computation
0
0 comments X

The pith

Expected runtime of the (1+1) EA on OneMax equals the sum of inverse drifts minus (e/2) log n plus O(1).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that drift analysis suffices to locate the expected running time of the (1+1) evolutionary algorithm on OneMax within an additive logarithmic error. Starting from a configuration with roughly half the bits set to one, the runtime lies between the sum of the reciprocals of the per-state drifts and that same sum shifted by two different positive multiples of log n. Standard asymptotic expansion of the difference then pins the leading correction term at exactly (e/2) log n plus a bounded remainder. This tightens an earlier error of order n to the two-thirds from looser analyses. A reader cares because the result shows that elementary drift calculations already deliver the precision that previously required matched-asymptotics machinery.

Core claim

The expected running time E(T), starting from ⌈n/2⌉ one-bits, satisfies sum_{k=1}^{⌊n/2⌋} 1/Δ(k) - c1 log n ≤ E(T) ≤ sum_{k=1}^{⌊n/2⌋} 1/Δ(k) - c2 log n, where Δ(k) is the drift (expected increase of the number of one-bits from the state of n-k ones) and c1, c2 > 0 are explicitly computed constants. Using standard asymptotic techniques, the difference between E(T) and the sum of inverse drifts is found to be (e/2) log n + O(1).

What carries the argument

The per-state drift Δ(k), the expected increase in the number of one-bits when the current state has n-k ones.

If this is right

  • The runtime admits an explicit non-asymptotic bound once the finite sum and the two constants c1 and c2 are evaluated.
  • The leading correction is independent of the particular starting point provided it is Ω(n).
  • The same drift-based sandwich can be applied to any linear function whose per-state success probabilities yield a comparable drift expression.
  • Higher-order terms in the asymptotic expansion of E(T) can be read off from the expansion of the inverse-drift sum alone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The appearance of the constant e/2 hints that the same correction may govern the runtime on other unimodal landscapes whose drift is locally linear.
  • The method supplies a template for replacing heavy analytic-combinatorial machinery with drift analysis plus elementary singularity analysis in other evolutionary-algorithm settings.
  • If the drift function admits a closed-form antiderivative, the entire runtime expression collapses to a single integral plus the logarithmic shift.

Load-bearing premise

The recurrence satisfied by the expected runtime admits an asymptotic solution whose error after subtracting the sum of inverse drifts is captured exactly by the term (e/2) log n plus a constant.

What would settle it

Numerical computation of the exact expected runtime for a concrete n around 10^4, followed by direct subtraction of the inverse-drift sum minus (e/2) log n, to check whether the remainder stays bounded.

Figures

Figures reproduced from arXiv: 1906.09047 by Carsten Witt, Hsien-Kuei Hwang.

Figure 1
Figure 1. Figure 1: Differences between ∆∗ n (k), 1 ∆∗ n(k) and their asymptotic approximations for n = 2, . . . , 50 (in increasing order of the density of the curves) and k = 1, . . . , n (normalized in the unit interval). 29 [PITH_FULL_IMAGE:figures/full_fig_p029_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Differences between the exact expected runtime and [PITH_FULL_IMAGE:figures/full_fig_p030_2.png] view at source ↗
read the original abstract

The expected running time of the classical (1+1) EA on the OneMax benchmark function has recently been determined by Hwang et al. (2018) up to additive errors of $O((\log n)/n)$. The same approach proposed there also leads to a full asymptotic expansion with errors of the form $O(n^{-K}\log n)$ for any $K>0$. This precise result is obtained by matched asymptotics with rigorous error analysis (or by solving asymptotically the underlying recurrences via inductive approximation arguments), ideas radically different from well-established techniques for the running time analysis of evolutionary computation such as drift analysis. This paper revisits drift analysis for the (1+1) EA on OneMax and obtains that the expected running time $E(T)$, starting from $\lceil n/2\rceil$ one-bits, is determined by the sum of inverse drifts up to logarithmic error terms, more precisely $$\sum_{k=1}^{\lfloor n/2\rfloor}\frac{1}{\Delta(k)} - c_1\log n \le E(T) \le \sum_{k=1}^{\lfloor n/2\rfloor}\frac{1}{\Delta(k)} - c_2\log n,$$ where $\Delta(k)$ is the drift (expected increase of the number of one-bits from the state of $n-k$ ones) and $c_1,c_2 >0$ are explicitly computed constants. This improves the previous asymptotic error known for the sum of inverse drifts from $\tilde{O}(n^{2/3})$ to a logarithmic error and gives for the first time a non-asymptotic error bound. Using standard asymptotic techniques, the difference between $E(T)$ and the sum of inverse drifts is found to be $(e/2)\log n+O(1)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper claims that drift analysis yields sharp non-asymptotic bounds on the expected runtime E(T) of the (1+1) EA on OneMax (starting from ⌈n/2⌉ ones): the sum of inverse drifts minus c1 log n is a lower bound and minus c2 log n is an upper bound, with explicit positive constants c1, c2. This improves the prior error term from Õ(n^{2/3}) to O(log n). Using standard asymptotic techniques on the underlying recurrence, the paper further claims that the difference E(T) minus the inverse-drift sum equals exactly (e/2) log n + O(1).

Significance. If the derivations hold, the work is significant because it is the first to obtain explicit logarithmic error bounds via drift analysis alone (with explicitly computed c1, c2) and to isolate a precise leading coefficient for the difference term. This bridges classical drift methods with analytic combinatorics in a way that supplies falsifiable, non-asymptotic predictions for a canonical benchmark, strengthening the toolbox for runtime analysis of evolutionary algorithms.

major comments (1)
  1. [Abstract (difference statement) and the subsequent asymptotic-analysis section] The claim that the difference is precisely (e/2) log n + O(1) (abstract) rests on applying standard asymptotic techniques (matched asymptotics or inductive approximation) to the recurrence after the drift bounds are established. Because Δ(k) = (k/n)(1−k/n) is a specific quadratic form, it must be shown that the Euler-Maclaurin or equivalent expansion isolates the coefficient e/2 without additional logarithmic contributions from the harmonic structure of the sum or from the boundary terms at k ≈ n/2; otherwise the explicit constants c1, c2 become invalid. This step is load-bearing for the sharp-constant claim.
minor comments (1)
  1. [Abstract] The abstract refers to 'analytic combinatorial tools' without naming the concrete technique (e.g., Euler-Maclaurin formula, singularity analysis); a one-sentence pointer in the introduction would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a load-bearing aspect of the asymptotic claim. We respond to the major comment below.

read point-by-point responses

  1. Referee: [Abstract (difference statement) and the subsequent asymptotic-analysis section] The claim that the difference is precisely (e/2) log n + O(1) (abstract) rests on applying standard asymptotic techniques (matched asymptotics or inductive approximation) to the recurrence after the drift bounds are established. Because Δ(k) = (k/n)(1−k/n) is a specific quadratic form, it must be shown that the Euler-Maclaurin or equivalent expansion isolates the coefficient e/2 without additional logarithmic contributions from the harmonic structure of the sum or from the boundary terms at k ≈ n/2; otherwise the explicit constants c1, c2 become invalid. This step is load-bearing for the sharp-constant claim.

    Authors: The drift-analysis portion of the manuscript derives the explicit constants c1 and c2 independently of the finer asymptotic expansion; these constants bound the difference between E(T) and the inverse-drift sum by O(log n) via direct comparison of the recurrence with the continuous drift. The separate claim that the difference equals exactly (e/2) log n + O(1) is obtained by applying matched asymptotics (or inductive approximation) directly to the exact recurrence for the expected hitting time, after the drift bounds have already been established. For the quadratic drift Δ(k) = (k/n)(1−k/n), the Euler-Maclaurin expansion of the resulting sum isolates the coefficient e/2 from the leading integral term; the harmonic-number contributions are absorbed into this coefficient, and the boundary correction at the fixed starting point k = ⌈n/2⌉ produces only an O(1) term with no additional log n factor. Consequently the O(log n) error bounds with explicit c1, c2 remain valid and are not invalidated by the sharper expansion. If the referee believes a dedicated lemma spelling out the absence of extra logarithmic boundary terms would strengthen the presentation, we are prepared to insert one. revision: partial

Circularity Check

0 steps flagged

Derivation self-contained via independent drift analysis

full rationale

The paper establishes the stated bounds on E(T) directly from drift analysis applied to the (1+1) EA on OneMax, yielding the explicit constants c1 and c2 without reference to fitted parameters or prior self-results. The sharpening of the difference to (e/2)log n + O(1) is obtained by applying external standard asymptotic techniques (e.g., Euler-Maclaurin summation or inductive approximation) to the recurrence for expected runtime. The citation to Hwang et al. (2018) provides only contextual comparison to a tighter but methodologically distinct prior result and is not invoked to justify the drift bounds or the logarithmic error term. No step reduces by construction to a quantity defined in terms of itself, and the central claims remain independently verifiable from the drift equations and generic asymptotic tools.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The analysis rests on standard probabilistic assumptions about the (1+1) EA mutation operator (independent bit flips) and on the applicability of analytic combinatorics tools for asymptotic expansion of the runtime recurrence; no free parameters or new entities are introduced.

axioms (2)
  • domain assumption The drift Δ(k) equals the expected increase in the number of one-bits when the current state has n-k ones, computed from the binomial distribution of bit flips.
    This definition is required to form the sum of inverse drifts that approximates E(T).
  • domain assumption Standard asymptotic techniques suffice to extract the precise (e/2)log n + O(1) difference between E(T) and the inverse-drift sum.
    Invoked when the abstract states the difference is found using those techniques.

pith-pipeline@v0.9.0 · 5876 in / 1681 out tokens · 33668 ms · 2026-05-25T18:39:06.055570+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · 3 internal anchors

  1. [1]

    Theory of Randomized Search Heuristics – Foundations and Recent Developments

    Anne Auger and Benjamin Doerr. Theory of Randomized Search Heuristics – Foundations and Recent Developments . World Scientific Publishing, 2011

    work page 2011

  2. [2]

    Sutton, L

    Francisco Chicano, Andrew M. Sutton, L. Darrell Whitley, and Enrique Alba. Fitness probability distribution of bit-flip mutation. Evolutionary Computa- tion, 23(2):217–248, 2015. 30

    work page 2015

  3. [3]

    The impact of random initialization on the runtime of randomized search heuristics

    Benjamin Doerr and Carola Doerr. The impact of random initialization on the runtime of randomized search heuristics. Algorithmica, 75(3):529–553, 2016

    work page 2016

  4. [4]

    Optimal parameter choices via precise black-box analysis

    Benjamin Doerr, Carola Doerr, and Jing Yang. Optimal parameter choices via precise black-box analysis. In Proc. of GECCO ’16 , pages 1123–1130. ACM Press, 2016

    work page 2016

  5. [5]

    Quasirandom evolu- tionary algorithms

    Benjamin Doerr, Mahmoud Fouz, and Carsten Witt. Quasirandom evolu- tionary algorithms. In Proc. of GECCO ’10 , pages 1457–1464. ACM Press, 2010

    work page 2010

  6. [6]

    Sharp bounds by probability-generating functions and variable drift

    Benjamin Doerr, Mahmoud Fouz, and Carsten Witt. Sharp bounds by probability-generating functions and variable drift. In Proc. of GECCO ’11 , pages 2083–2090. ACM Press, 2011

    work page 2083

  7. [7]

    The (1+λ) evolutionary algorithm with self-adjusting mutation rate

    Benjamin Doerr, Christian Gießen, Carsten Witt, and Jing Yang. The (1+λ) evolutionary algorithm with self-adjusting mutation rate. Algorith- mica, 81(2):593–631, 2019

    work page 2019

  8. [8]

    Multiplicative drift analysis

    Benjamin Doerr, Daniel Johannsen, and Carola Winzen. Multiplicative drift analysis. Algorithmica, 64(4):673–697, 2012

    work page 2012

  9. [9]

    On the analysis of the (1+1) evolutionary algorithm

    Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science , 276:51–81, 2002

    work page 2002

  10. [10]

    Rigorous hitting times for binary mutations

    Josselin Garnier, Leila Kallel, and Marc Schoenauer. Rigorous hitting times for binary mutations. Evolutionary Computation, 7(2):173–203, 1999

    work page 1999

  11. [11]

    Optimal mutation rates for the (1+λ) EA on OneMax through asymptotically tight drift analysis

    Christian Gießen and Carsten Witt. Optimal mutation rates for the (1+λ) EA on OneMax through asymptotically tight drift analysis. Algorithmica, 80(5):1710–1731, 2018

    work page 2018

  12. [12]

    Hitting-time and occupation-time bounds implied by drift anal- ysis with applications

    Bruce Hajek. Hitting-time and occupation-time bounds implied by drift anal- ysis with applications. Advances in Applied Probability, 13(3):502–525, 1982

    work page 1982

  13. [13]

    Drift analysis and average time complexity of evolu- tionary algorithms

    Jun He and Xin Yao. Drift analysis and average time complexity of evolu- tionary algorithms. Artificial Intelligence, 127:57–85, 2001

    work page 2001

  14. [14]

    Probabilistic analysis of the (1+1)-evolutionary algorithm

    Hsien-Kuei Hwang, Alois Panholzer, Nicolas Rolin, Tsung-Hsi Tsai, and Wei- Mei Chen. Probabilistic analysis of the (1+1)-evolutionary algorithm. CoRR, abs/1409.4955, 2014. http://arxiv.org/abs/1409.4955. 31

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  15. [15]

    Probabilistic analysis of the (1+1)-evolutionary algorithm

    Hsien-Kuei Hwang, Alois Panholzer, Nicolas Rolin, Tsung-Hsi Tsai, and Wei- Mei Chen. Probabilistic analysis of the (1+1)-evolutionary algorithm. Evolu- tionary Computation, 26:299–345, 2018

    work page 2018

  16. [16]

    Analyzing Evolutionary Algorithms - The Computer Science Perspective

    Thomas Jansen. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Natural Computing Series. Springer, 2013

    work page 2013

  17. [17]

    Random combinatorial structures and randomized search heuristics

    Daniel Johannsen. Random combinatorial structures and randomized search heuristics. PhD thesis, Universit¨ at des Saarlandes, Germany, 2010

    work page 2010

  18. [18]

    Timo K¨ otzing and Martin S. Krejca. First-hitting times for finite state spaces. In Proc. of PPSN ’18 , pages 79–91. Springer, 2018

    work page 2018

  19. [19]

    Timo K¨ otzing and Martin S. Krejca. First-hitting times under additive drift. In Proc. of PPSN ’18 , pages 92–104. Springer, 2018

    work page 2018

  20. [20]

    Drift analysis (tutorial)

    Per Kristian Lehre. Drift analysis (tutorial). In Companion to GECCO 2012 , pages 1239–1258. ACM Press, 2012

    work page 2012

  21. [21]

    Black-box search by unbiased variation

    Per Kristian Lehre and Carsten Witt. Black-box search by unbiased variation. Algorithmica, 64(4):623–642, 2012

    work page 2012

  22. [22]

    General Drift Analysis with Tail Bounds

    Per Kristian Lehre and Carsten Witt. General drift analysis with tail bounds. Technical report, 2013. http://arxiv.org/abs/1307.2559

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  23. [23]

    Concentrated hitting times of ran- domized search heuristics with variable drift

    Per Kristian Lehre and Carsten Witt. Concentrated hitting times of ran- domized search heuristics with variable drift. In Proc. of ISAAC ’14 , pages 686–697. Springer, 2014

    work page 2014

  24. [24]

    Drift Analysis

    Johannes Lengler. Drift analysis. CoRR, abs/1712.00964, 2018. To appear as a book chapter in Theory of Evolutionary Algorithms in Discrete Search Spaces (eds. B. Doerr and F. Neumann), Springer

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  25. [25]

    Rowe, and Chris Cannings

    Boris Mitavskiy, Jonathan E. Rowe, and Chris Cannings. Theoretical anal- ysis of local search strategies to optimize network communication subject to preserving the total number of links. International Journal of Intelligent Computing and Cybernetics , 2(2):243–284, 2009

    work page 2009

  26. [26]

    How genetic algorithms really work: I

    Heinz M¨ uhlenbein. How genetic algorithms really work: I. Mutation and hillclimbing. In Proc. of PPSN ’92 , pages 15–26. Elsevier, 1992

    work page 1992

  27. [27]

    Rowe and Dirk Sudholt

    Jonathan E. Rowe and Dirk Sudholt. The choice of the offspring popula- tion size in the (1, λ) evolutionary algorithm. Theoretical Computer Science, 545:20–38, 2014. 32

    work page 2014

  28. [28]

    General lower bounds for the running time of evolutionary algorithms

    Dirk Sudholt. General lower bounds for the running time of evolutionary algorithms. In Proc. of PPSN ’10 , pages 124–133. Springer, 2010

    work page 2010

  29. [29]

    Tight bounds on the optimization time of a randomized search heuristic on linear functions

    Carsten Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability and Computing , 22(2):294–318, 2013. 33

    work page 2013