Introduction to Probability for Computer Science. The course intends to cover the basics of probability and then introduce high dimensional probability. In the later part, we consider applications from Computer Science.
Basics-0
Random experiments, sample space, sigma-field*, review of sets theory, probability set function*. Mutually exclusive events and probability function, exhaustive events, the inclusion-exclusion formula. Some inequalities: Boole's or union bound and generalization, examples. Probability set function continuity*. Conditional probability, Bayes' theorem, independence of sets of events.
Basics-1
Random Variables/Functions from the sample space to reals, discrete random variables and probability mass function, continuous random variables and cumulative distribution function (cdf), properties of cdf, transformation of variables Y = g(X) and conditions, defining probability density function (pdf), examples, transformations of variables. Expectation of random variables, examples from continuous and discrete domains, expectation of function of random variables, linearity of expectation and examples. Basic statistics: expectation, variance, high order expectations, moment generating function, Markov, Chebychev inequalities, exponential moment method, convexity, Jensen's inequality, examples.
Multivariate Distributions
Random vector, joint cumulative distribution function, discrete random vectors and joint probability mass function, continuous cdf and joint pdf, marginal pdfs and pmfs. Expectations, mgf of random vectors, transformations of bivariate random variables, examples. Conditional distributions and expectations, total variance law. Correlation coefficient, independent random variables and connections to product form of joint pdf, joint cdf, product expectation. Extension to multiple random variables, mutual independence, mgfs, simple transformations of multiple random variables, examples. Covariance matrix, matrices of random variables, linear combinations of random variables.
Special Distributions
Bernoulli, Binomial, Rademacher, geometric, multinomial distributions, sampling with and without replacement, Poisson, Gamma, chi-square, beta, normal and multivariate normal distribution and some of its properties.
Tail Probability Concentration bounds
Markov, Chernoff and Hoeffding’s bounds, Bernstein bounds, applications, examples, Johnson-Lindenstrauss' Lemma, applications
Possible additional topics Time permitting: