This is an evolving note, such that new concepts will constantly be added.

- Events
- If , then

- Expectations
- if and are independent
- If ,
- Law of large number: for infinite sequence of i.i.d. random variable , sample mean converges to as approaches

- Conditional Probabilities and Conditional Expectations
- Since ,
- Conditional density of given :
- Conditional expectation of given :
- Law of Total Expectation

- Variance
- if and are independent
- if the are independent

- Covariance
- Mean Square Error: , more detail explanation can be found on wikipedia.
- Inequalities
- Boole’s inequality (Union bound): for a countable set of events ,
- Jensen: for convex , ; for concave ,
- Markov: If then for all ,
- Chebyshev-Cantelli: for ,
- Chebyshev’s Association: let and be nondecreasing (nonincreasing) real-valued functions defined on the real line. If is a real-valued random variable then,
- Harris’: extends Chebyshev’s Association to functions
- Chernoff bound: for any , for any random variable ,
- Cauchy-Schwarz: if , then
- Hoeffding’s inequality: Let be a random variable with . Then for
- Hoeffding’s tail: Let be independent bounded random variable such that falls in the interval with probability one. Then for any , and
- Bernstein’s inequality: Let be independent real-valued random variables with mean, and assume that with probability . Let . Then, for any , .
- when , the upper bound behaves like instead of the guaranteed by Hoeffding’s tail.

- McDiarmid’s inequality: let be i.i.d. random variables, and let be s.t. . Then .
- Azuma-Hoeffding’s inequality: let be a martingale (see definition of martingale below) s.t. for some constant , then .

- Variables
- Rademacher random variables: s.t.
- Rademacher averages: for a set of vectors , the Rademacher average is defined as , where

- Martingale is a special sequence of random variables
- A discrete-time martingale is a discrete-time stochastic process that satisfies
- Let filtration then . e.g.

- A discrete-time martingale is a discrete-time stochastic process that satisfies

- Rademacher random variables: s.t.
- Other
- If , then with probability at least , .
- Moment generating function of a random variable is where