Analyzing Randomized Search Heuristics: Tools from Probability Theory

Benjamin Doerr

doi:10.1142/9789814282673-1

Analyzing Randomized Search Heuristics: Tools from Probability Theory

Benjamin Doerr

Max-Planck-Institut fur Informatik

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

Abstract

In this chapter, we collect a few probabilistic tools that are useful for analyzing randomized search heuristics. This includes elementary mate¬rial like Markov, Chebyshev and Chernoff bounds, but also lesser known topics like dealing with sums of random variables that are only close to being independent or a strong lower bound for the time needed by the coupon collector process. Such results, while also of general inter¬est, seem to be particularly useful in the analysis of randomized search heuristics.

Original language	English
Title of host publication	Theory of Randomized Search Heuristics
Subtitle of host publication	Foundations and Recent Developments
Publisher	World Scientific Publishing Co.
Pages	1-20
Number of pages	20
ISBN (Electronic)	9789814282673
ISBN (Print)	9814282669, 9789814282666
DOIs	https://doi.org/10.1142/9789814282673-1
Publication status	Published - 1 Jan 2011
Externally published	Yes

Access to Document

10.1142/9789814282673-1

Cite this

@inbook{8959c4d46794471bb646e4d38a77d2b9,

title = "Analyzing Randomized Search Heuristics: Tools from Probability Theory",

abstract = "In this chapter, we collect a few probabilistic tools that are useful for analyzing randomized search heuristics. This includes elementary mate¬rial like Markov, Chebyshev and Chernoff bounds, but also lesser known topics like dealing with sums of random variables that are only close to being independent or a strong lower bound for the time needed by the coupon collector process. Such results, while also of general inter¬est, seem to be particularly useful in the analysis of randomized search heuristics.",

author = "Benjamin Doerr",

note = "Publisher Copyright: {\textcopyright} 2011 by World Scientific Publishing Co. Pte. Ltd.",

year = "2011",

month = jan,

day = "1",

doi = "10.1142/9789814282673-1",

language = "English",

isbn = "9814282669",

pages = "1--20",

booktitle = "Theory of Randomized Search Heuristics",

publisher = "World Scientific Publishing Co.",

}

TY - CHAP

T1 - Analyzing Randomized Search Heuristics

T2 - Tools from Probability Theory

AU - Doerr, Benjamin

PY - 2011/1/1

Y1 - 2011/1/1

N2 - In this chapter, we collect a few probabilistic tools that are useful for analyzing randomized search heuristics. This includes elementary mate¬rial like Markov, Chebyshev and Chernoff bounds, but also lesser known topics like dealing with sums of random variables that are only close to being independent or a strong lower bound for the time needed by the coupon collector process. Such results, while also of general inter¬est, seem to be particularly useful in the analysis of randomized search heuristics.

AB - In this chapter, we collect a few probabilistic tools that are useful for analyzing randomized search heuristics. This includes elementary mate¬rial like Markov, Chebyshev and Chernoff bounds, but also lesser known topics like dealing with sums of random variables that are only close to being independent or a strong lower bound for the time needed by the coupon collector process. Such results, while also of general inter¬est, seem to be particularly useful in the analysis of randomized search heuristics.

U2 - 10.1142/9789814282673-1

DO - 10.1142/9789814282673-1

M3 - Chapter

AN - SCOPUS:85129052535

SN - 9814282669

SN - 9789814282666

SP - 1

EP - 20

BT - Theory of Randomized Search Heuristics

PB - World Scientific Publishing Co.

ER -

Analyzing Randomized Search Heuristics: Tools from Probability Theory

Abstract

Access to Document

Fingerprint

Cite this