## MATH-500 Probability

Syllabus

 Date Topic Homework Due 1 9/4 Probability space, union bound, random graph HW#1 Problems: 1.2: 4: 1.3: 2, 3, 4, 5 9/11 2 9/6 Lower bound on Ramsey number, Inclusion-Exclusion 3 9/11 Secretary's problem, Bonferroni ineq., isolates in random graphs HW#2 9/18 4 9/13 Continuity, conditional probability, paradoxes, prisoners 5 9/18 Independence, Euler function, symmetric random walk HW#3: 1.5: 2,3,4,5; 1.7: 3,5 9/25 6 9/20 Min-Cut randomized algorithm 7 9/25 Bloom filters 8 9/27 class cancelled 9 10/2 LLL with proof 10 10/4 LLL -- applications (Ramsey numbers, rainbow colorings of reals) HW#4 10/11 11 10/11 Problem solving (HW#2,3) 12 10/16 Random variables, Bernoulli Thm., Bernstein ineq. 13 10/18 Applications of Bernstein ineq., Jordan's Thm. 1/2 of FINAL EXAM: from Sec. 1.8 A(2.16.29) P(7,21,31) S(13,15,19) K(17,28,39) D(23,32,35) SJ(18,25,38) 11/20 14 10/23 Singular distribution, random vectors HW#5: 2.5:5, 2.7: 2a,11,12,13b,15,16 10/30 15 10/25 Expectation 16 10/30 Probabilistic method via expectation 17 11/1 Problem solving (HW#4) 18 11/6 Joint distributions 19 11/8 Problem solving (HW#5) HW#6: 3.1:3; 3.2:3,4; 3.3: 2,3,8-9; 3.4: 1,2,3,4,7,8; 3.5: 3,4; 3.6: 6a; 3.7: 1ef, 4,6,10; 3.8: 5 11/20 20 11/13 Random walks 21 11/15 More random walks 22 11/20 Yet more random walks 23 11/27 Generating functions (and random walks) 24 11/29 Branching processes (no random walks) HW#7: 5.4:1,3,5,6; 5.3:1; 3.11:24,29,30,32; 3.9:4,5 (choose each three different problems) 12/4 25 12/4 Markov chains 26 12/6 Markov Chain Monte Carlo 27 12/11 Approximate counting 28 12/17 8:30-11:00 AM Final Exam