Probabilistic Tools for the Analysis of Randomized Optimization Heuristics

01/20/2018
by   Benjamin Doerr, et al.
0

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. Almost all 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.

READ FULL TEXT

page 1

page 2

page 3

page 4

research
03/04/2020

Notes on Randomized Algorithms

Lecture notes for the Yale Computer Science course CPSC 469/569 Randomiz...
research
08/29/2013

Collecting Coupons with Random Initial Stake

Motivated by a problem in the theory of randomized search heuristics, we...
research
03/02/2018

On some discrete random variables arising from recent study on statistical analysis of compressive sensing

The recent paper [27] provides a statistical analysis for efficient dete...
research
11/04/2022

Significance improvement by randomized test in random sampling without replacement

This paper studies one-sided hypothesis testing under random sampling wi...
research
11/05/2018

On a generalization of iterated and randomized rounding

We give a general method for rounding linear programs that combines the ...
research
01/14/2023

Arcade Processes for Informed Martingale Interpolation and Transport

Arcade processes are a class of continuous stochastic processes that int...
research
08/22/2021

Algorithms for reachability problems on stochastic Markov reward models

Probabilistic model-checking is a field which seeks to automate the form...

Please sign up or login with your details

Forgot password? Click here to reset