Source-linked AI summary
Signed Sensitivity of Expected Hitting Time to Mutation Rate in the (1+1) EA: Per-State Sign Theorems and Verifiable Certificates for Non-Lumpable Families
RenKai Wang
TL;DR
The paper studies how the (1 + 1) EA’s expected hitting time varies with mutation rate, a question not settled by fixed-rate exact analyses or numerical rate searches. It gives a signed influence treatment and double-residual certificates, proving per-state signs on OneMax and extending certificates to non-lumpable families.
Problem
Existing work supplies exact per-state analyses at p = 1/n and numerical searches for optimal rates, but the paper identifies a gap in rigorous finite-n sensitivity analysis across continuous mutation rates and non-lumpable families.
Source: §1 · pp. 1–2Method
Results
On OneMax, ∂cH_k < 0 for every non-optimal initial distance and c ∈ (0, 1), while at c = 1 only distance one is stationary; non-lumpable families also receive interval and finite-instance certificates.
Source: §1 · p. 2Takeaways & Limitations
Under uniform random initialization, the OneMax result implies that the finite-n optimal static rate is strictly larger than one.
Source: §1 · p. 2The paper leaves extending the sign theorem to larger c intervals and the certificate framework to other parameters and non-lumpable benchmarks as open problems.
Source: §10 · p. 11
Abstract
from arXiv · showhide
For the (1+1) evolutionary algorithm with standard bit mutation, we study the sensitivity of the expected hitting time $H_p=\mathbb{E}_x T$ to the mutation rate. We first point out an easily overlooked formalization pitfall: the improvement event is not monotone in the mutation mask, so the unsigned (total-influence) form of the Margulis-Russo formula does not apply; the correct object is the signed endpoint difference. Second, we give an exact three-dimensional separation: two fitness functions share the entire one-step success-rate curve, yet their expected hitting times are two different exact rational numbers; hence one-step success-rate quantities do not determine the expected hitting time. Building on the runtime derivative $H'_p=(I-Q_p)^{-1}Q'_p H_p$, we construct computable double-residual sign certificates, prove a per-initial-state sign theorem on OneMax (for every non-optimal initial state, $\partial_c H<0$ on $0<c<1$, where $p=c/n$; at $c=1$ only the distance-one state is stationary), and extend the framework to non-lumpable positive linear families: an explicit non-lumpability witness, a block-interval double-residual certificate that covers all states without enumerating them, a uniform sign bound $\partial_c\mathbb{E}T\le -9n/16$ over the whole interval $c\in[1/4,1/2]$ for an explicit family at all even scales $n\ge 8$, and a heterogeneous instance certificate $H'_x\le -1/6$ on 57 of 63 states across $c=1$. All finite verifications use exact rational arithmetic. A bounded systematic literature search did not uncover this exact combination, although the underlying tools are well established; we therefore make no novelty claim beyond the stated combination.
1 Introduction
The paper addresses the gap between fixed-rate exact analyses and numerical rate optimization with a rigorous finite-n study of expected hitting-time sensitivity. It combines a signed influence correction, a OneMax per-state theorem, and certificates for non-lumpable families.
Introduction
- Prior work provides exact per-state analyses at p = 1/n and numerical searches for optimal rates, but not rigorous finite-n sensitivity analysis across continuous rates and non-lumpable state spaces.The exact analyses and numerical searches concern OneMax and, respectively.Source: §1 · pp. 1–2
Contributions
- The paper frames its contribution as the first rigorous per-initial-state, finite-n sign analysis of expected hitting time versus mutation rate, specifically at the intersection of these tools with runtime analysis.The introduction organizes the contribution around signed influence analysis, double-residual certificates, and their extension to non-lumpable families.Source: §1 · p. 2
- The improvement event is not monotone in the mutation mask, so the unsigned total-influence bridge fails; the paper gives a minimal counterexample and a signed per-state replacement.The signed Margulis–Russo identity itself is textbook material.Source: §1 · p. 2
- On OneMax, ∂cH_k < 0 for every non-optimal distance k and c ∈ (0, 1); at c = 1, only the distance-one state is stationary.Under uniform random initialization, this yields a rigorous finite-n result that the optimal static rate is strictly larger than one.Source: §1 · p. 2
- For non-lumpable families, block-interval certificates bound residuals for all states without enumerating them, with a uniform sign bound over an interval and all even scales.The introduction also reports a finite-instance certificate across c = 1; finite checks use exact rational arithmetic.Source: §1 · p. 2
2 Preliminaries and Notation
The preliminaries define the mutation process and accepted transitions, then express expected hitting times through the transient-state transition matrix. Derivatives throughout are with respect to the normalized rate c, where p = c/n.
Mutation and selection
- Each mutation mask has independent Bernoulli(p) coordinates, and the offspring is formed by bitwise XOR with the parent.K denotes the number of flipped bits, and E_p is expectation under the p-biased product measure.Source: §2 · p. 3
- The (1 + 1) EA accepts offspring whose fitness is at least the parent’s, and the Boolean influence uses the signed endpoint difference across one mask coordinate.The unsigned influence is the probability that this endpoint difference is nonzero.Source: §2 · p. 3
Hitting times and derivatives
- For the transient transition matrix Q_p, H_p = (I − Q_p)^−1 1; D and U denote its c-derivative and the c-derivative of H_p, respectively.The derivative convention is p = c/n, so d/dc = (1/n)d/dp; the stated formulas need no further rescaling.Source: §2 · p. 3
3 Signed Margulis–Russo and the Monotonicity Pitfall
The section replaces an invalid unsigned influence argument with a signed treatment of improvement probabilities, then shows that identical one-step success curves can conceal different expected hitting times.
3.1 The signed Margulis–Russo identity
- The signed Margulis–Russo treatment differentiates mask probabilities through coordinatewise endpoint differences, with the Boolean improvement indicator’s sign determined by the parent bit.The section also records the positive-affine-invariance observation without claiming novelty for it.Source: §3.1 · p. 3, §3.2 · p. 4
3.2 The monotonicity pitfall
- For the n = 2 OneMax parent (1, 0), improvement requires mask (0, 1), so the improvement event is non-monotone although total influence stays 1.The success-probability derivative changes sign; therefore the unsigned total-influence bridge is invalid, and the signed coordinate difference is the appropriate replacement.Source: §3.2 · pp. 3–4
3.3 One-step success rates do not determine running time
- OneMax at n = 3 and p = 1/3 has the same success-rate curve as BinVal but different exact expected hitting times from 000: 189/22 versus 2139/247.The one-step success probability, even together with global change probability, does not determine expected running time.Source: §3.3 · pp. 4–5
4 OneMax: A Per-State Sign Theorem
On OneMax, the derivative of expected hitting time is negative for every non-optimal initial state when 0 < c < 1, with distance one the sole stationary state at c = 1. The section supports this result with exact level analysis and residual-based sign certification.
4 OneMax: A Per-State Sign Theorem
- OneMax aggregates exactly by distance to the optimum, and a coupling orders hitting times for parents with nested zero-coordinate sets.The contraction bound uses W(x) = k, with α = p(1 − p)^(n−1).Source: §4 · p. 5
- For every distance k ≥ 1, U_k(c) < 0 on 0 < c < 1; at c = 1, only the distance-one state is stationary.For k ≥ 2 the derivative remains negative at c = 1, while U_1(c) is positive for c > 1.Source: §4 · p. 5
- Under uniform random initialization, the expected hitting time has negative derivative at c = 1, so no minimizer on [0, n] lies at or below 1.Thus the finite-n optimal static mutation rate is strictly larger than c = 1.Source: §4 · p. 6
- The double-residual framework bounds errors in approximations to H and its derivative, yielding per-level sign intervals; exact level solutions make the OneMax residuals vanish.The framework also gives a uniform rounding precision on any fixed rational interval inside (0, 1) that preserves strict negative signs.Source: §4 · p. 6
5 Non-Lumpable Families: Block Interval Certificates
For positive linear targets, the section constructs blockwise residual intervals that cover every state without assuming the block partition is lumpable. When the resulting derivative interval is strictly negative, the certificate establishes a negative derivative for every state in that block.
5 Non-Lumpable Families: Block Interval Certificates
- The construction applies to positive linear targets grouped by coordinates, although the original chain is generally not lumpable by the resulting zero-count block labels.A witness gives two states in one block with different normalized transition masses to a third block.Source: §5 · p. 6
- The block-interval double-residual certificate computes rational intervals containing every state’s residual in a block without enumerating the underlying states.It bounds the derivative’s deviation from the block table value; a strictly negative upper sign bound certifies negativity throughout the block.Source: §5 · p. 7
6 A Uniform Whole-Interval Sign Bound
The section gives a whole-interval negative derivative certificate for an explicit non-lumpable family at even scales. Its finite-n result goes beyond what asymptotic leading terms establish about derivative signs.
6 A Uniform Whole-Interval Sign Bound
- For even n = 2m ≥ 8, the two-group family has a negative runtime-derivative certificate throughout c ∈ [1/4, 1/2].The family uses m low-weight bits of weight 1 and m high-weight bits with weights b + δi.Source: §6 · pp. 7–8
- Except for specified g = 0 classes in four parent blocks, the family’s acceptance decisions agree with OneMax, leaving residual contributions only in those classes.The proof bounds the exceptional class mass and residuals to obtain a uniform negative margin.Source: §6 · p. 8
- Finite-n exact derivative signs are not implied by the asymptotic decrease of the leading term, since lower-order terms can reverse a state’s sign.The result adds finite n, exact derivatives, and a non-lumpable family.Source: §6 · p. 8
- The certificate uses deliberately conservative bounds, and the tightest admissible radius at n = 8 is smaller than 7/32.The passage notes that exact rational arithmetic is used so errors in constants cannot silently weaken the bound.Source: §6 · p. 8
7 A Heterogeneous Instance Certificate Across c = 1
A rational-interval certificate covers most states of a heterogeneous n = 6 instance across a parameter cell around c = 1. Its exclusions are structural: single-zero states can have indeterminate derivative signs there.
7 A Heterogeneous Instance Certificate Across c = 1
- For n = 6, the certificate covers all 57 states whose zero-count is at least 2; the six single-zero states are outside its conclusion.The proof uses rational-interval Horner expansions and independently checks the proxy equations and bounds.Source: §7 · pp. 8–9
- Block-level sign envelopes have no uniform cell-width guarantee, and derivatives can disagree within a block for BinVal at n = 8 and c = 0.999.Certified signs persist over cell sequences whose widths tend to zero, but coarser partitions can mix signs.Source: §7 · p. 9
- Single-zero-bit states have indeterminate derivative signs across c = 1, so no uniform negative bound there can cover them.This matches the OneMax result that the distance-one state is stationary at c = 1.Source: §7 · p. 9
8 Related Work
The related work distinguishes fixed-rate and asymptotic runtime analyses from rigorous per-state sensitivity over a continuous mutation-rate parameter. It also situates the paper’s certificates alongside work on hitting times, verification, and non-lumpable linear families.
Optimal mutation rates on OneMax
- Prior analyses either fix p = 1/n or target asymptotic leading terms, leaving finite-n, per-state rigorous analysis over a continuous mutation rate unaddressed.Numerical searches for optimal rates have also been conducted for OneMax [11].Source: §8 · p. 9
State-dependent optimal rates
- Dynamic-rate work optimizes per-fitness-level rates numerically, whereas this paper studies static-rate hitting-time derivative signs and rigorously finds the random-initialization optimum above 1.The direction is consistent with approximate drift conclusions for the (1 + λ) EA and per-n numerics.Source: §8 · p. 9
One-step quantities and running time
- Two fitness functions can share the entire one-step success-rate curve yet have different exact rational expected hitting times, showing that success-rate quantities alone do not determine runtime.The passage frames this as an exact minimal form of a broader distinction between one-step quantities and running time.Source: §8 · p. 9
Hitting-time derivatives and verification methods
- Classical absorbing-chain perturbation and parametric model-checking methods provide precedents, but the cited certificates target derivative signs for coupled H and U over intervals and scales [31, 37, 7, 22, 8, 3, 26, 25, 2, 9].Prior analyses of non-lumpable linear families use potentials, stochastic domination, or drift; the paper instead supplies a non-lumpability witness and block-level interval certificates [14].Source: §8 · p. 10
9 Verification and Reproducibility
The paper reports exact-rational verification with independent cross-checks and archived artifacts. It also quantifies the checks performed across the OneMax and heterogeneous analyses.
9 Verification and Reproducibility
- All finite checks use exact rational arithmetic, and key results are cross-validated by matrix differentiation and the rational-function quotient rule.The authors state that sign conclusions depend on exactness because floating-point error cannot support sign assertions.Source: §9 · p. 10
- The verification totals include 4,408 OneMax reconciliation checks, 4,408 contraction checks, 5,472 certificates, and 2,455 heterogeneous parameter–state combinations.The heterogeneous instance also has 1,475 issued sign certificates.Source: §9 · p. 10
- Scripts, execution logs, and hash receipts are archived with the project.The reported audits include 230 + 133 + 603 artifact-integrity items.Source: §9 · p. 10
10 Conclusion and Open Problems
The paper analyzes expected hitting time as a continuous function of mutation rate and combines signed analysis, exact separation results, per-state sign theorems, and certificates for non-lumpable families. It closes with open problems on extending the sign theorem and certificate framework.
10 Conclusion and Open Problems
- The analysis treats expected hitting time as a continuous function of the mutation rate.Source: §10 · p. 10
- The paper combines signed Margulis–Russo analysis, an exact separation of one-step quantities from running time, OneMax per-state signs, and certificates for non-lumpable families.The non-lumpable results include a uniform interval sign bound across even scales and a finite-instance certificate across c = 1.Source: §10 · p. 10
- Open problems include extending the OneMax sign theorem to larger c intervals and studying block-level envelope limits and partition trade-offs.The authors also propose extending certificates to other parameters and benchmarks, and connecting them to parametric model-checking toolchains.Source: §10 · p. 11