TY - CHAP
T1 - Probabilistic tools for the analysis of randomized optimization heuristics
AU - Doerr, Benjamin
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2020.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - This chapter collects several probabilistic tools that have proven to be useful in the analysis of randomized search heuristics. This includes classic material such as the Markov, Chebyshev, and Chernoff inequalities, but also lesser-known topics such as stochastic domination and coupling, and Chernoff bounds for geometrically distributed random variables and for negatively correlated random variables. Most of the results presented here have appeared previously, but some only in recent conference publications. While the focus is on presenting tools for the analysis of randomized search heuristics, many of these may be useful as well for the analysis of classic randomized algorithms or discrete random structures.
AB - This chapter collects several probabilistic tools that have proven to be useful in the analysis of randomized search heuristics. This includes classic material such as the Markov, Chebyshev, and Chernoff inequalities, but also lesser-known topics such as stochastic domination and coupling, and Chernoff bounds for geometrically distributed random variables and for negatively correlated random variables. Most of the results presented here have appeared previously, but some only in recent conference publications. While the focus is on presenting tools for the analysis of randomized search heuristics, many of these may be useful as well for the analysis of classic randomized algorithms or discrete random structures.
U2 - 10.1007/978-3-030-29414-4_1
DO - 10.1007/978-3-030-29414-4_1
M3 - Chapter
AN - SCOPUS:85076085319
T3 - Natural Computing Series
SP - 1
EP - 87
BT - Natural Computing Series
PB - Springer
ER -