Sets, The concept of a discrete sample space in probability theory. The definition of an event. The definition of a probability distribution. De Morgan’s Law, Union Bounds
Random variables, expectation, and variance.
Discrete distributions: Bernoulli trials, Geometric, Binomial and Hypergeometric and Negative Binomial distributions, Poisson distribution. Continuous distributions: normal and other continuous distributions. Exercises based on the analysis of applications to computer science.
Linearity of expectation. Higher moments of a random variable, moment generating function. Computing the moments of geometric, binomial, normal, and Poisson distributions.
OPTIONAL (if time permits): Function of One Random Variable: Change of Variables.
Conditional Probability, Conditional expectation of a random variable with respect to an event. Bayes' Theorem and examples of applications in computer science.
The concept of k-wise and mutual independence of random variables. Applications of independence and k-wise independence in computer science.
Tail bounds: Markov inequality, Chebyshev's Inequality, Chernoff bound, and Examples of applications to the analysis of randomized algorithms.
Cover one or more applications: For example,