First-hitting times under drift

DOI10.1016/j.tcs.2019.08.021zbMath1435.68218arXiv1805.09415OpenAlexW2969531032WikidataQ127347631 ScholiaQ127347631MaRDI QIDQ2333786

Timo Kötzing, Martin S. Krejca

Publication date: 13 November 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.09415

zbMATH Keywords

random processdriftfirst-hitting time

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (5)

Tail bounds on hitting times of randomized search heuristics using variable drift analysis ⋮ Fixed-target runtime analysis ⋮ First Steps Towards a Runtime Analysis of Neuroevolution ⋮ Runtime Analysis of a Co-Evolutionary Algorithm ⋮ Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

Cites Work

• Unnamed Item
• Concentration of first hitting times under additive drift
• Simplified drift analysis for proving lower bounds in evolutionary computation
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Adaptive drift analysis
• Multiplicative drift analysis
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Weighted sums of certain dependent random variables
• Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift
• Drift Analysis and Evolutionary Algorithms Revisited
• Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Probability with Martingales
• Probability
• A basic course in probability theory
• Drift analysis and average time complexity of evolutionary algorithms

This page was built for publication: First-hitting times under drift