E0 232: Probability and Statistics

August - December 2012

Department of Computer Science & Automation
Indian Institute of Science



[Announcements]  [Course Description]  [Assignments]  [Academic Honesty]  [Schedule] 

Course Information

Class Meetings

Lectures: Tu-Th 11:30am-1:00pm, Central Lecture Hall L1
First lecture: Tue Aug 7

Instructor

Dr. Shivani Agarwal (shivani@csa)

TAs

Harish Guruprasad (harish_gurup@csa) (Office hours: MW 10-11am, CSA 230)
Saneem Ahmed (saneem@csa)

Mailing list

http://groups.google.com/group/probstat-aug2012-iisc

Announcements


Course Description

Probability is the mathematical study of uncertainty, and is not only a fascinating subject in its own right, but also forms an essential foundation for a broad range of subjects related to computer science, including algorithms (randomized algorithms, probabilistic analysis of algorithms), cryptography, graph theory, combinatorics, machine learning, data mining, game theory, information theory, communication theory, coding theory, complexity theory, and several others. Statistics, the science of developing probabilistic models and making associated inferences from data, also requires a strong foundation in probability. This course aims to provide a foundational introduction to probability, with a brief introduction to statistics at the end.

Textbooks

Prerequisites

Basic course in calculus.

Grading


Assignments

Assignment Policy

The following assignment policy will be strictly followed: * Except in the case of a documented medical/personal emergency, which must be supported by a medical certificate or signed letter submitted to the instructor and to the CSA office.

Note: In your assignment solutions, show all your calculations. You do not need to evaluate final answers in decimal points; it is sufficient to give your answers as sums or products of decimal numbers/fractions as appropriate.

Academic Honesty

As students of IISc, we expect you to adhere to the highest standards of academic honesty and integrity.

Assignments in the course are designed to support your learning of the subject. Copying will not help you (in the exams or in the real world), so don't do it. If you have difficulties learning some of the topics or lack some background, try to form study groups where you can bounce off ideas with one another and try to teach each other what you understand. You're also welcome to come to our office hours and we'll be glad to help you.

If any assignment/exam is found to be copied, it will automatically result in a zero grade for that assignment/exam and a warning note to your advisor. Any repeat instance will automatically lead to a failing grade in the course.

Tentative Schedule

  Date Topic Reading Notes
1 Tue Aug 07 Introduction. Set theory review. Sample spaces, events, probabilities. BT 1.1-1.2
2 Thu Aug 09 Conditional probability. Multiplication rule, total probability theorem, Bayes' rule. BT 1.3-1.4  
3 Tue Aug 14 Independence BT 1.5  
4 Thu Aug 16 Counting BT 1.6  
5 Tue Aug 21 Discrete random variables. Probability mass functions. Expectation, variance. BT 2.1-2.4 Assignment 1 due
6 Thu Aug 23 Multiple discrete random variables: joint PMFs, conditional & marginal PMFs, conditional expectation. BT 2.5-2.6  
7 Tue Aug 28 Multiple discrete random variables: independence, covariance, correlation. BT 2.7, 4.2  
8 Thu Aug 30 Continuous random variables. Probability density functions, cumulative distribution functions. BT 3.1-3.2  
9 Tue Sep 04 Multiple continuous random variables: conditioning, independence. BT 3.3-3.5 Assignment 2 due
10 Thu Sep 06 Continuous random variables: further examples. BT 3.6  
  Tue Sep 11 Midterm 1 (in class)    
11 Thu Sep 13 Further topics on random variables: derived distributions. BT 4.1  
  Tue Sep 18 Class canceled.    
12 Thu Sep 20 Further topics on random variables: iterated expectations, moment generating functions. BT 4.3-4.5, GS Ch 5 Assignment 3 due
13 Tue Sep 25 Further topics on random variables: concentration inequalities. BT 5.1, class notes  
14 Thu Sep 27 Convergence of random variables. Laws of large numbers. BT 5.2-5.3, class notes, GS Ch 7  
  Tue Oct 02 Institute Holiday (Gandhi Jayanti)    
15 Thu Oct 04 Central limit theorem BT 5.4  
16 Tue Oct 09 Bernoulli and Poisson processes BT Ch 6 Assignment 4 due
17 Thu Oct 11 Markov chains: introduction, classification of states, steady-state probabilities. BT 7.1-7.2  
  Tue Oct 16 Midterm 2 (in class)    
18 Thu Oct 18 Markov chains: probabilities of absorption, expected time to absorption. BT 7.3-7.4  
19 Tue Oct 23 Selected applications of probability in computer science: Randomized algorithms
Guest lecture by Dr. Neeldhara Misra
Lecture notes  
20 Thu Oct 25 Statistics I. Parameter estimation: bias, consistency, mean squared error; maximum likelihood estimator; confidence intervals. BT 9.1
Note on confidence intervals
Assignment 5 due
21 Tue Oct 30 Statistics II. Hypothesis testing: Type I and II errors; likelihood ratio tests; Neyman-Pearson lemma. BT 9.3-9.4, class notes  
  Thu Nov 01 Institute Holiday (Kannada Rajyotsava)    
22 Tue Nov 06 Statistics III. Bayesian inference: prior and posterior distribution; conjugate priors. BT 8.1, class notes  
23 Thu Nov 08 Statistics IV. Bayesian point estimates: MAP estimator, conditional expectation estimator. Bayesian binary hypothesis testing: MAP decision rule. BT 8.2-8.3  
  Tue Nov 13 Institute Holiday (Diwali)    
24 Thu Nov 15 Fun with Probability: Review & Preview   Assignment 6 due
  Tue 27 Nov Final exam (9:00-12:00, CLH L1)