## Probability and Computing - Monsoon Semester (2014-15)

Time: Tu 14:00-17:00
Location: D405
Instructor:

#### 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
This page has been accessed at least times since 10 August, 2014.