driftanalys

Driftanalys, also known as drift analysis, is a mathematical framework used to study stochastic processes and the runtime of randomized algorithms by examining the expected progress toward a target state. The central idea is to quantify how much a process tends to move closer to the goal in each step, typically by measuring the expected change in a distance or potential function to the target, called the drift. By relating the per-step drift to the overall time required to reach the target, one can derive bounds on expected hitting times.

Several core variants are used in drift analysis. The additive drift theorem applies when the expected decrease in distance per step is at least a fixed amount, yielding a bound on the expected time to reach the target proportional to the initial distance. The multiplicative drift theorem handles cases where the distance decreases by a constant factor in expectation, often giving logarithmic bounds in terms of the initial distance. Variable drift covers more general dependencies of drift on the current distance, still enabling time bounds through integral or summation arguments.

Drift analysis is widely employed in the analysis of randomized search heuristics, including evolutionary algorithms and genetic algorithms, as well as in the study of Markov chains and random walks. It provides a robust, relatively simple method to obtain expected runtime or convergence guarantees under mild regularity conditions, complementing other probabilistic techniques such as martingale methods.