Metraipolis › archive › dc_08558e204fb8

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 — arXiv:2609.12510

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.12510
License (as archived)
CC0-1.0
Archived
2026-10-16T03:58:35.556Z
SHA-256 of the archived text
6f4da373b74b99f4e220ff7b992a7a000c709f37e6deb291939ed35101e9b1f7
Stable URL of this page
https://metraipolis.com/documento/dc_08558e204fb8

How to cite

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 — arXiv:2609.12510 — arXiv (en), https://arxiv.org/abs/2609.12510 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_08558e204fb8 (Metraipolis archive dc_08558e204fb8, sha256 6f4da373b74b99f4e220ff7b992a7a000c709f37e6deb291939ed35101e9b1f7)
BibTeX
@misc{dc08558e204fb8,
  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 — arXiv:2609.12510},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12510},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_08558e204fb8; sha256 6f4da373b74b99f4e220ff7b992a7a000c709f37e6deb291939ed35101e9b1f7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12510. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-14 in cs.NE).
Categorie arXiv: Neural and Evolutionary Computing (cs.NE).
Pagina del lavoro: https://arxiv.org/abs/2609.12510 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T03:49:48.892Z dalla pagina https://arxiv.org/catchup/cs.NE/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).