Loading...
Please wait, while we are loading the content...
CS265/CME309: Randomized Algorithms and Probabilistic Analysis Lecture #16: Martingales, the Doob Martingale, and Azuma-Hoeffding Tail Bounds
| Content Provider | Semantic Scholar |
|---|---|
| Author | Valiant, Gregory |
| Copyright Year | 2019 |
| Abstract | In this lecture we introduce the concept of a Martingale, which can be used to analyze many random processes. The technical core of this lecture will be the Azuma-Hoeffding tail bound, which gives a Chernoff style bound on tail probabilities of martingales. These bounds were independently proved by Azuma and Hoeffding in the 1960's [1, 2]. Crucially, these bounds will let us often effortlessly prove strong concentration results for sums of certain dependent random variables and other stochastic processes. The proof technique for the Azuma-Hoeffding bounds follow the same general approach as Chernoff bounds: applying Markov's inequality to the moment generating function for the random variable in question. Our analysis of this moment generating function, however, will crucially leverage the properties of martingales, as opposed to the properties of sums of independent random variables. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://theory.stanford.edu/~valiant/teaching/CS265/lectureNotes/l16.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
