## 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