Probability and Computing - Monsoon Semester (2014-15)

Time: Tu 14:00-17:00
Location: D405
Instructor:
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2014-15/probability

Problem Sets and Exams

1. PS1 [ pdf (out: 2 Sep, due: 16 Sep) ]
2. PS2 [ pdf (out: 14 Oct, due: 28 Oct) ]

Lectures

1. Aug 19: Introduction to discrete probability
   Probability in Computing, Examples: Verifying Matrix Multiplication, MINCUT, factorization of quadratic polynomials; Discrete probability modeling, conditioning.
   Ref: [ MU (Chap. 1), GS (Sec 1.1-1.4), Sud (Lec. 4, last section; Lec. 5, section 1)]
   
   
2. Aug 26:Application to primes and random variables
   Independence; Primes: picking a random prime, testing primality; birthday problem; random variables; expectation; linearity of expectation
   Ref: [ MU (Chap 2) ]
   
   
3. Sep 2: Applications of linearity of expectation
   probability mass functions; conditional expectation; binomial and geometric rvs; Applications: MAXCUT, Coupons collectors' problem, randomized quicksort; Markov's inequality
   Ref: [ MU (Chap 2) ]
   
   
4. Sep 9: Tail bounds: Chebyshev and Chernoff
   Variance, Chebyshev's Inequality, Chernoff bounds, sampling, randomized load balancing
   Ref: [ MU (Chap. 3-4) ]
   
   
5. Sep 16: Poisson Distribution and Hashing
   Balls and Bins, Poisson distribution, Hashing techniques
   
   
6. Sep 23: Hashing and Random graphs
   fingerprinting, Bloom filters, Random Graphs (Erdos-Renyi Model, Bollobas degree sequence model, Barabasi-Albert preferential alignment model)
   
   
7. Oct 8: Markov Chains
   Finite space, discrete time Markov chains, stationary distributions, Irregularities: periodicity, reducibility; regular Markov chains, Fundamental theorem for finite state Markov chains, time-reversibility; Applications: Pagerank and Metropolis algorithms.
   
   
8. Oct 14: Markov Chains and continuous random variables
   Proof of Fundamental theorem for finite state Markov chains; Introduction to continuous random variables, uniform and exponential distributions, probability density functions (pdfs), cumulative density functions (cdfs), joint pdfs
   
   

Tentative list of topics

1. Introduction, examples: verifying matrix multiplication, mincut
2. Discrete probability, random variables, conditioning, independence
3. Linearity of Expectation, Jensen's inequality, testing primes
4. Birthday Problem, Binomial + Geometric rv's, MAXCUT
5. Moments and Deviations: Markov's, Chebyshev's inequalities
6. Chernoff Bounds, Application: load balancing
7. Balls and bins, posson approximation
8. Hashing, fingerprinting, bloom filters
9. Probabilistic Method
10. Markov Chains, Applications: Pagerank, Metropolis
11. Continuous Random Variables
12. Poisson Process
13. Continuous Markov Chains
14. Gaussian Random Variables, Central Limit Theorem
15. Martingales

Requirements

Students taking the course for credit will be expected to:

• Do problem sets (approx 1 pset every 2 weeks, 6 psets)
• Give the final exam
• Grading:
  • Problems Sets - 75%
  • Final Exam - 25%

References

This page has been accessed at least times since 10 August, 2014.

Prahladh Harsha