Course Description
Units: 3-0-0-9 (Modular 2nd Half)
Pre-Requisites: None
Basics Of Probability Theory : [Weeks 1]
Sets, The concept of a discrete sample space in probability theory. The definition of an event. The definition of a probability distribution. Random variables, expectation and variance.
Distributions : [Weeks 2 & 3]
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.
Conditional Probability, Conditional expectation of a random variable with respect to an event. Bayes' Theorem and examples of applications in computer science.
[Weeks 4]
The concept of k-wise and mutual independence of random variables. Applications of independence and k-wise independence in computer science.
[Week 5]
Tail bounds: Markov inequality, Chebyshev's Inequality, Chernoff bound, and Examples of applications to the analysis of randomized algorithms.
[Week 6 & 7]
Introduction to the probabilistic method. Applications to random graphs and number theory. Lovasz Local Lemma and applications.
If time permits, one of the following topics can be covered: Information theory/ Markov chains/ Randomized algorithms/ Streaming.
[Extra Week 8]
Whatever material remains.
Books:
- William Feller, An introduction to probability theory and its applications.
- Sheldon Ross, A first course in probability.
- David Stirzaker, Elementary probability.
- Kai Lai Chung, A course in probability theory.