Loading...
Please wait, while we are loading the content...
CS265/CME309: Randomized Algorithms and Probabilistic Analysis Lecture #6: Moment-Generating Functions, Chernoff Bounds, and Randomized Routing on the Hypercube
| Content Provider | Semantic Scholar |
|---|---|
| Author | Valiant, Gregory |
| Copyright Year | 2019 |
| Abstract | Continuing the theme from Lecture 5 on tail bounds, in today’s class we will begin by proving some Chernoff bounds. Chernoff bounds, in their most simple form, apply to sums of independent random variables, and roughly state that the probability that the sum deviates from its expectation by more than c standard deviations, decreases inverse exponentially with c. To see the intuition for why we should expect this, consider the Central Limit Theorem: |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://theory.stanford.edu/~valiant/teaching/CS265/lectureNotes/l6.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
