Loading...
Please wait, while we are loading the content...
Similar Documents
Lecture 2 The Chernoff bound and some applications
| Content Provider | Semantic Scholar |
|---|---|
| Abstract | The Chernoff bound and some applications In this lecture we see a powerful concentration bound for sums of independent random variables, the Chernoff bound, and some applications of this bound. First let's get back to the streaming algorithm Count-Min Sketch. The idea is that if the h i are independent, for each element x it is likely that there is an i such that x is the only element mapped to h i (x), in which case c i,h i (x) will return an accurate count of the number of occurrences of x in the stream. We will prove the following theorem. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://courses.cms.caltech.edu/cs139/notes/lecture02.pdf |
| Alternate Webpage(s) | http://users.cms.caltech.edu/~vidick/teaching/CS139_Winter16/notes/lecture02.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
