Home > Teaching > CS 798F: Introduction to Probability for Computer Science

CS 798F: Introduction to Probability for Computer Science

Course Description:

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.

 

Course Syllabus:

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:

  1. Martingale and techniques based on them, Azuma-Hoeffding bound
  2. Lipschitz functions of Gaussian variables
  3. Markov chains, stochastic matrices and its properties. Applications/Examples