First-hitting times under drift

DOI10.1016/J.TCS.2019.08.021zbMATH Open1435.68218arXiv1805.09415OpenAlexW2969531032WikidataQ127347631 ScholiaQ127347631MaRDI QIDQ2333786FDOQ2333786

Authors: Timo Kötzing, Martin S. Krejca 

Publication date: 13 November 2019

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

Abstract: For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process -- the drift. This is usually far easier than bounding the expected first-hitting time directly. Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be nonnegative, that is, we remove unnecessary restrictions like a finite, discrete, or bounded search space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift.

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

Recommendations

• Concentration of first hitting times under additive drift
• scientific article; zbMATH DE number 4054742
• The measurability of hitting times
• scientific article; zbMATH DE number 4128258
• The likelihood of mixed hitting times
• Hitting times and positions in rare events
• Moments of the first passage time under external driving
• Hitting time and place of Brownian motion with drift
• Hitting time statistics and extreme value theory

zbMATH Keywords

driftrandom processfirst-hitting time

Mathematics Subject Classification ID

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

Cites Work

• Probability and random processes.
• Probability with Martingales
• Weighted sums of certain dependent random variables
• 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
• Concentrated hitting times of randomized search heuristics with variable drift
• Concentration of first hitting times under additive drift
• 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
• Drift analysis and average time complexity of evolutionary algorithms
• Simplified drift analysis for proving lower bounds in evolutionary computation
• A basic course in probability theory
• Drift analysis and evolutionary algorithms revisited
• Probability

Cited In (8)

• Fixed-target runtime analysis
• Multiplicative up-drift
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• Concentrated hitting times of randomized search heuristics with variable drift
• Self-adjusting offspring population sizes outperform fixed parameters on the Cliff function
• First Steps Towards a Runtime Analysis of Neuroevolution
• Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers
• Runtime Analysis of a Co-Evolutionary Algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2333786)