## Notes further updated

The lecture notes have been updated some more. Thanks to all who have provided me timely scribe notes. Please read what other scribes have written and if this gives you ideas for improving your own notes, please send me a new version of your notes. It would be most welcome.

## Lecture notes

The first set of lecture notes, covering the basics and the first algorithm we saw (Misra-Gries; scanned PDF here) is now ready. This is also linked from the course website. I will add to these notes soon, to include the Flajolet-Martin and AMS algorithms for DISTINCT-ELEMENTS. Also, Radhika and Andrew will add to the notes to include Count-Min Sketch, CountSketch and the BJKST algorithm.

I’ll announce each significant update to the lecture notes on this blog.

Please notify me, or write a comment here, if you spot an error or a typo in the notes, or wish to say something related to all this. Let this blog be at least somewhat informal!

## Probability theory reference

By now, we have introduced the idea of randomized algorithms, and to analyse their performance, we have used some basic probability theory. To recap, the important concepts are:

- Probability spaces, events, union bound
- Random variables, expectation, linearity of expectation
- Independent events, independent random variables
- Variance, standard deviation

Most importantly, we have introduced the notion of *large deviation* inequalities, or *tail inequalities*. Briefly, these inequalities assert that a certain random variable is not too likely to deviate much from its expected value. The important inequalities (so far) are:

- Markov’s inequality: If is a random variable and a constant, then
.
- Chebyshev’s inequality: If , then
.
- Chernoff bound: If and are independent and identically distributed indicator random varibles, then
; .

Going forward, it will be vital to have these inequalities at your fingertips, ready for use. An excellent reference covering all of this material is the early chapters of the book *Randomized Algorithms*, by Motwani and Raghavan.

leave a comment