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:


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 Counter times since 10 August, 2014.


Prahladh Harsha
Valid HTML 4.01! Valid CSS!