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

• URL: http://arxiv.org/abs/2609.12510v1
• Date: Fri, 11 Sep 2026 07:14:28 GMT
• Title: 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
• Abstract summary: We study the sensitivity of the expected hitting time $H_p=mathbbE_x T$ to the mutation rate.<n>Two fitness functions share the entire one-step success-rate curve, yet their expected hitting times are two different exact rational numbers.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• One Inverse Step is a Convex Program: Bayes-Limit Calibration of Diffusion Inversion [0.0]
  One implicit DDIM inversion step is the cheapest probe of whether a pretrained diffusion model encodes local manifold geometry.<n>The Fermi window conflicts with the model's own training support by $3.6$-$5.6times$, and the trained Hessian-Lipschitz constant is $2$-$12%$ of the curvature the law reads.<n>Finally the unconditional ceiling $_t_max(mathrmsym,J)le1$, from $mathrmCov(x_0mid x_t)succeq0$
  arXiv  Detail & Related papers  (2026-08-24T11:01:54Z)
• The Physical Cutoff Does Not Restore Homogenization: Phase-Dependent Burning in the Strain G-Equation [2.538209532048867]
  We prove that for any $C2$ incompressible periodic flow, every $varepsilon$-outward barrier certificate has covering radius at most $2dvarepsilon$ for all sufficiently small $varepsilon$.
  arXiv  Detail & Related papers  (2026-08-15T17:41:14Z)
• An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
  We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere.<n>Our guiding principle is that its maximizers are rounding candidates.
  arXiv  Detail & Related papers  (2026-08-03T17:58:00Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• Random Parameter Noise Does Not Make Exact ReLU Verification Easy [14.270378035741404]
  We study exact verification of ReLU networks in an adversarial smoothed model.<n>We show that, under the standard assumption $mathrmNPnotsubseteqmathrmBPP$, there is no sound and complete verifier whose expected running time is embedding in network size, bit complexity, and inverse noise level for every base instance.
  arXiv  Detail & Related papers  (2026-07-15T21:26:20Z)
• Nonlinear Two-Time-Scale Stochastic Approximation: A Sharp Phase Transition and How to Beat It [46.80389197344682]
  We prove localized transfer theorems that extend the phase-transition mechanism to general nonlinear TTSA.<n>The proofs are non-asymptotic and rely on two Abel-transform cancellations.
  arXiv  Detail & Related papers  (2026-06-12T14:24:28Z)
• Optimizing Explicit Unit-Distance Lower-Bound Certificates [0.0]
  The 2026 disproof of Erds's unit-distance conjecture and Sawin's quantitative refinement show that the maximum number $u(n)$ of unit distances among $n$ planar points can exceed $n1+varepsilon$ for a fixed positive $varepsilon$.<n>This report treats Sawin's parameter selection as a nonlinear integer optimization problem and develops an open-source Python pipeline for certificates involving prime sets $T$ and $S_Q$.
  arXiv  Detail & Related papers  (2026-06-02T10:05:23Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation [49.1574468325115]
  Temporal Difference Learning (TD(0)) is fundamental in reinforcement learning.<n>We provide the first high-probability, finite-sample analysis of vanilla TD(0) on mixing Markov data.
  arXiv  Detail & Related papers  (2025-02-08T22:01:02Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.