Martingales
Lists
Only you see this
Abstract
Martingales are sequences of random variables satisfying certain conditions that arise in numerous applications, such as random walks and gambling problems. We focus here on three useful analysis tools related to martingales: the martingale stopping theorem, Wald's inequality, and the Azuma–Hoeffding inequality. The martingale stopping theorem and Wald's equation are important tools for computing the expectation of compound stochastic processes. The Azuma–Hoeffding inequality is a powerful technique for deriving Chernoff-like tail bounds on the values of functions of dependent random variables. We conclude this chapter with applications of the Azuma–Hoeffding inequality to problems in pattern matching, balls and bins, and random graphs.
BibTeX
@inproceedings{mitzenmacher2005martingales,
author = {Michael Mitzenmacher and Eli Upfal},
title = {{Martingales}},
booktitle = {Cambridge},
year = {2005},
doi = {10.1017/cbo9780511813603.013},
}Loading related content...