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