Probability and Computing  Monsoon Semester (201415)
Time: Tu 14:0017:00
Location: D405
Instructor:
Homepage:
http://www.tcs.tifr.res.in/~prahladh/teaching/201415/probability
Problem Sets and Exams
 PS1 [ pdf (out: 2 Sep, due: 16 Sep) ]
 PS2 [ pdf (out: 14 Oct, due: 28
Oct) ]
Lectures
 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.11.4), Sud (Lec. 4,
last section; Lec. 5, section 1)]
 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) ]
 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) ]
 Sep 9: Tail bounds: Chebyshev and Chernoff
Variance, Chebyshev's Inequality, Chernoff bounds, sampling,
randomized load balancing
Ref: [ MU (Chap. 34) ]
 Sep 16: Poisson Distribution and Hashing
Balls and Bins, Poisson distribution, Hashing techniques
 Sep 23: Hashing and Random graphs
fingerprinting, Bloom filters, Random Graphs
(ErdosRenyi Model, Bollobas degree sequence model, BarabasiAlbert
preferential alignment model)
 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, timereversibility;
Applications: Pagerank and Metropolis algorithms.
 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
 Introduction, examples: verifying matrix multiplication, mincut
 Discrete probability, random variables, conditioning, independence
 Linearity of Expectation, Jensen's inequality, testing primes
 Birthday Problem, Binomial + Geometric rv's, MAXCUT
 Moments and Deviations: Markov's, Chebyshev's inequalities
 Chernoff Bounds, Application: load balancing
 Balls and bins, posson approximation
 Hashing, fingerprinting, bloom filters
 Probabilistic Method
 Markov Chains, Applications: Pagerank, Metropolis
 Continuous Random Variables
 Poisson Process
 Continuous Markov Chains
 Gaussian Random Variables, Central Limit Theorem
 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
[GM]

G. Grimmett and D. Stirzaker.
Probability and Random Processes.
3rd Ed. Oxford University Press, 2001.
[ .html ]

[MU]

M. Mitzenmacher and E. Upfal.
Probability and Computing.
Cambridge University Press, 2005.

[Sud]

Madhu Sudan.
6.966, Algebra and Complexity Theory, 1998.
A course offered at MIT (Fall 1998).
[ .html ]

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