Source-linked AI summary
Erratum: Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
Pietro S. Oliveto, Carsten Witt
TL;DR
The paper addresses an error in the simplified drift theorem, whose original jump condition was insufficient for proving long target-reaching times. It strengthens that condition, proves a more general corrected theorem, and revisits earlier applications, finding that they satisfy the stronger requirement directly or with additional arguments.
Problem
The original simplified drift theorem is invalid because its condition controlling jumps toward the target does not also control large jumps away from the target.
Source: §1 · p. 1Method
The paper strengthens the jump condition to control large jumps in both directions, proves the corrected theorem, and reassesses previous applications.
Source: §3 · p. 4, §4 · pp. 6–7Results
The corrected theorem provides a valid lower-bound result while no longer requiring a Markov process or finite search space.
Source: §3 · p. 4Takeaways & Limitations
Previous applications either satisfy the stronger condition directly or can be repaired with a few additional arguments.
Source: §4 · pp. 6–7, §4.4 · p. 9The fitness-proportional EA analysis requires modifying the algorithm because very large jumps away from the target remain possible for the original population size µ = 2.
Source: §4.4 · pp. 8–9
Abstract
from arXiv · showhide
This erratum points out an error in the simplified drift theorem (SDT) [Algorithmica 59(3), 369-386, 2011]. It is also shown that a minor modification of one of its conditions is sufficient to establish a valid result. In many respects, the new theorem is more general than before. We no longer assume a Markov process nor a finite search space. Furthermore, the proof of the theorem is more compact than the previous ones. Finally, previous applications of the SDT are revisited. It turns out that all of these either meet the modified condition directly or by means of few additional arguments.
1 Introduction
The simplified drift theorem concerns processes whose expected distance from a target increases, while seeking long target-reaching times requires exponentially small probabilities of large jumps toward the target. This erratum identifies a flaw in the original condition and announces a corrected theorem and review of prior applications.
1 Introduction
- The simplified drift theorem analyzes processes that drift away from a target, meaning their expected distance from that target increases each step.For a target state 0, this can be expressed as E(X_t+1 − X_t) ≥ ε when X_t > 0.Source: §1 · p. 1
- Positive expected drift alone does not imply a long target-reaching time because a process may still jump directly to the optimum with substantial probability.The theorem therefore needs a separate condition controlling jumps toward the target.Source: §1 · p. 1
- The original SDT required exponential decay for jumps toward the target, such as Prob(X_t+1 − X_t ≤ −j) ≤ 2^-j.This condition is described in and.Source: §1 · p. 2
- The erratum reports that the original SDT is incorrect unless exponential decay also applies to large jumps away from the target, essentially using Prob(|X_t+1 − X_t| ≥ j) ≤ 2^-j.The absolute value is the crucial strengthening of the second condition.Source: §1 · p. 2
- The paper presents a counterexample, proves a corrected SDT, and revisits earlier applications to show that they satisfy the stronger conditions directly or with additional arguments.The counterexample, corrected theorem, and application review are assigned to Sections 2–4.Source: §1 · p. 2
2 An Example Where the Original Theorem is Wrong
A counterexample shows that the original SDT can predict long target-reaching times despite a process that reaches the target with very high probability. The failure arises from combining constant drift away from the target with rare but very large jumps away from it.
2 An Example Where the Original Theorem is Wrong
- The counterexample uses a Markov process on an exponentially large state space, starting at b = n with target a = 0.The original theorem demanded a finite search space.Source: §2 · p. 2
- Within the drift interval, the process jumps upward by 2e^n with probability e^-n and decreases by 1 otherwise.Outside the relevant interval, its behavior does not affect the counterexample.Source: §2 · p. 2
- These transitions yield expected drift of at least 1 away from the target within the drift interval.The rare upward jump offsets the almost-always unit decrease in expectation.Source: §2 · p. 2
- Despite constant drift away from the target, the process reaches the target after n consecutive decreasing steps with probability at least 1 − ne^-n.Starting from b = n, each step toward the target decreases the state by 1.Source: §2 · p. 2
- The original proof incorrectly upper-bounded a double sum in the drift moment-generating function by uniformly bounding terms without accounting for their signs.This is the identified source of the theorem’s failure.Source: §2 · p. 2
3 The Corrected Version
The corrected simplified drift theorem combines drift away from a target with exponential control of both large forward and backward jumps. It applies without Markovian or finite-search-space assumptions and yields exponentially small probabilities of reaching the target quickly.
Theorem statement
- The corrected theorem requires exponentially decaying probabilities for large jumps in either direction, in addition to drift away from the target.Its jump condition bounds Prob(|X_t+1 − X_t| ≥ j | F_t ∧ a < X_t) using r(ℓ)(1+δ)^j.Source: §3 · p. 4
Generality
- The theorem applies to real-valued stochastic processes without assuming Markovian dynamics, a finite search space, or an explicit potential-function representation.The process variables may already incorporate the mapping from a state space to real-valued potentials.Source: §3 · pp. 3–4
Theorem statement
- For interval length ℓ = b − a and r(ℓ) = o(ℓ/log(ℓ)), reaching a or below within 2c*ℓ/r(ℓ) steps has probability 2^−Ω(ℓ/r(ℓ)).The stopping time starts from X_0 ≥ b and records the first time X_t ≤ a.Source: §3 · p. 4
Proof
- The proof uses an exponential-moment bound E(e^−λΔ) ≤ 1 − 1/p(ℓ), with λ = Ω(1/r(ℓ)) and p(ℓ) = O(r(ℓ)).The first drift condition supplies the negative exponential-moment term, while the jump-tail condition bounds the absolute-jump moment by O(r(ℓ)).Source: §3 · pp. 4–5
- Applying Hajek’s drift theorem with L(ℓ) = 2c*ℓ/r(ℓ) completes the proof of the exponentially small early-hitting probability.The prerequisite r(ℓ) = o(ℓ/log(ℓ)) enables the final simplification.Source: §3 · p. 6
4 Previous Applications
The corrected condition is checked across earlier applications, often directly or with additional bounds for jumps away from the target. Most applications carry over, while specific analyses require adjustments or expose limitations.
4 Previous Applications
- Earlier applications generally satisfy the stronger jump condition directly or after additional arguments, preserving their intended drift-based analyses.Constant-size neighborhoods and standard bit mutation provide immediate cases; other applications require bounding jumps away from the optimum.Source: §4 · pp. 6–7
4.1 Maximum Matching (Theorem 8, [14, 15])
- For maximum matching, bounding path-lengthening events supplies the missing probability estimate and establishes Condition 2 with δ = 1 and r = 2^2.At most (2h)^j ways can lengthen the path by j, with two edge flips required per lengthening.Source: §4.1 · p. 7
4.2 Diversity with fitness duplicates (Theorem 3, [4])
- For diversity with fitness duplicates, increasing the potential by j requires selecting y_k and flipping ϕ − k + j 1-bits, after which the opposite-direction calculations apply.The probability bound is derived from the required parent selection and bit flips.Source: §4.2 · pp. 7–8
4.3 (1,λ)-EA Analysis (Theorem 7, [18])
- For the (1,λ)-EA on OneMax, jump and self-loop bounds establish the stronger condition for λ = r(ℓ), where 1 ≤ r(ℓ) = o(ℓ / log(ℓ)).With λ ≤ (1−ε) log_e e^−1 n, the corrected theorem yields the stated runtime implication, but one result is a log n factor weaker than Theorem 7.Source: §4.3 · p. 8
4.4 Fitness-Proportional EA (Theorem 8, [12])
- The original fitness-proportional EA can make overly large jumps away from the target because repeated selection of a low-fitness individual can drastically reduce the potential.For μ = 2, selecting x_2 twice has probability Ω(1), while the potential g(x_1, x_2) = 8|x_1| + 8|x_2| can drop sharply.Source: §4.4 · p. 8
- PEA′ prevents this anomaly by always mutating the best individual once, while preserving a well-defined distribution and an optimization time stochastically no larger than the original PEA.The modified selection scheme also retains E(S_i) ≤ 2, allowing the remainder of the original analysis to carry over.Source: §4.4 · p. 9