# Probabilistic Tools for the Analysis of Randomized Optimization Heuristics

arXiv: https://arxiv.org/abs/1801.06733 · HTML: https://mlsanity.com/paper/1801.06733/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jan 2018.

## Built on by (most cited first, 24 of 24)

- [Mixability made efficient: Fast online multiclass logistic regression](https://mlsanity.com/paper/2110.03960/) (2021)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)](https://mlsanity.com/paper/2211.08202/) (2022)
- [Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2112.08581/) (2021)
- [Position: Scaling LLM Agents Requires Asymptotic Analysis with LLM Primitives](https://mlsanity.com/paper/2502.04358/) (2025)
- [A Theory of Unsupervised Translation Motivated by Understanding Animal Communication](https://mlsanity.com/paper/2211.11081/) (2022)
- [Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives](https://mlsanity.com/paper/2211.13084/) (2022)
- [Lower Bounds from Fitness Levels Made Easy](https://mlsanity.com/paper/2104.03372/) (2021)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [3-Objective Pareto Optimization for Problems with Chance Constraints](https://mlsanity.com/paper/2304.08774/) (2023)
- [Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise](https://mlsanity.com/paper/2305.10259/) (2023)
- [Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets](https://mlsanity.com/paper/2311.09858/) (2023)
- [Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2203.02693/) (2022)
- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)
- [Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus](https://mlsanity.com/paper/2302.08021/) (2023)
- [(1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error](https://mlsanity.com/paper/2303.07455/) (2023)
- [The Runtime of Random Local Search on the Generalized Needle Problem](https://mlsanity.com/paper/2403.08153/) (2024)
- [When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection](https://mlsanity.com/paper/2604.07473/) (2026)
- [Convergence and scaling of Boolean-weight optimization for hardware reservoirs](https://mlsanity.com/paper/2305.07908/) (2023)
- [A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2404.03838/) (2024)
- [On the Probability of First Success in Differential Evolution: Hazard Identities and Tail Bounds](https://mlsanity.com/paper/2601.11499/) (2026)
- [Parent Selection Mechanisms in Elitist Crossover-Based Algorithms](https://mlsanity.com/paper/2604.04083/) (2026)
- [A Fresh Look at Lamarckian Evolution and the Baldwin Effect](https://mlsanity.com/paper/2605.28703/) (2026)

## Abstract (arXiv)

This chapter collects several probabilistic tools that proved to be useful in the analysis of randomized search heuristics. This includes classic material like Markov, Chebyshev and Chernoff inequalities, but also lesser known topics like stochastic domination and coupling or Chernoff bounds for geometrically distributed random variables and for negatively correlated random variables. Most of the results presented here have appeared previously, some, however, only in recent conference publications. While the focus is on collecting tools for the analysis of randomized search heuristics, many of these may be useful as well in the analysis of classic randomized algorithms or discrete random structures.