This is the webpage for the course of Math 159 – Discrete Probabilistic Methods.
Lecture times: Tuesday and Thursday, 1:30 PM – 2:50 PM (Hewlett Teaching Center, Rm 101).
Instructor: Jacopo Borga, jborga_at_stanford.edu. Office hours: Tuesday 11:00 AM-12:15 PM (Building 380, 382-Q2).
Assistant: / Office hours: /
Description: In this course we will cover a range of different topics related to discrete probability. A primary focus will be the probabilistic method, where one may introduce probability to prove seemingly non-probabilistic facts. The primary textbook for the course will be “The probabilistic method” by Alon and Spencer, though we may sometimes refer to other books or papers.
As a prerequisite for this course, students are assumed to have an understanding of basic probability theory, reflected by passing MATH 151 or STAT 116 at A− or higher grade, or by consent of the instructor. Some background in combinatorics will be helpful but not essential.
Program: Here is a tentative program for this course (it will be updated as the course progresses):
Week 1: Introduction to the probabilistic method (Ch1 of A-S)
Week 2: Linearity of expectation and First moment method (Ch2 of A-S)
Week 3: Second moment method, Chernoff bound (Ch4 and Appendix A of A-S)
Week 4: Chernoff bound, Local Lemma (Ch5 of A-S, Moser-Tardos)
Week 5: Correlation inequalities, Janson inequalities (Ch6-7 of A-S)
Week 6: Martingales and tight concentration (Ch8 of A-S)
Week 7: Extra topics, if time
Week 8: Student presentations
Week 9: Student presentations
Week 10: Student presentations
Homework: Regarding homework, the textbook has some very good exercises, but they are quite difficult!
There will be four problem sets, due every second Friday at 10:00 PM, on Gradescope. They will be posted on Canvas. We will set up Gradescope to actually accept submissions until a day later, as a grace period in case of last-minute technical difficulties. Any other delay will be not accepted (i.e., no grading for late submissions).
Exam and Grading: Your grade will be determined by consistent Homework (40%) and an in-class presentation (60%). I’ll finalize the details of this once enrollment number stabilize, but here is some initial information:
- The format will be that in the last few weeks of quarter, 2/3/4 students will present each class (for 20 minutes each). There may also be some overflow sessions outside of usual class time, to avoid taking up too much lecture time.
- I will post a list of 10 topics for the presentations. Each topic should be presented in a session by 2/3/4 students.
- You must coordinate with 1/2/3 other students to jointly present on a single topic (each person presenting for 20 minutes). This will allow you to cover something much more interesting than you might be able to in just 20 minutes on your own. Please think carefully about what might be feasible to cover in the allowed time (you can use the amount of stuff I cover in lectures as a guide).
- I will ask questions during your presentation (and encourage other students to do the same). You will be expected to fully understand the details and ideas behind any proofs you present.
- Attendance during student presentations will be mandatory, without a good reason.
- You are strongly invited to discuss your presentation during office hours and at least one week before the official date.
- Three days before the scheduled date for your presentation you should send me a single LaTeX file with the notes on the material that you intend to present.
- Students must be ready to start their presentation at 1.30PM sharp.
Calendar for presentations: T.B.A.