This is the webpage for the course of Math 159 – Discrete Probabilistic Methods.
IMPORTANT NEWS: There is a 3 hours session on June 1st, 2022 to complete the remaining student’s presentations (see below for more information on student’s presentation). This is to allow all students to give their presentation before the Exam session.
Lecture times: Monday+Wednesday+Friday, 12:15 PM – 1:15 PM (380-380D)
Instructor: Jacopo Borga, jborga_at_stanford.edu. Office hours: Monday 11.00 AM-12:15 PM (Building 380, 382-Q2).
Assistant: Yang Liu, yangpliu_at_stanford.edu. Office hours: Tuesday 2-4PM (Building 380, 380-T) + Thursday 2-4PM (online on Zoom).
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 (very) 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! Historically in this course homework has accounted for no credit at all. This year we’ll be awarding some bonus credit (up to 15%) for homework. It will not be mandatory: in principle if you do an excellent job on the presentation but do not complete any homework problems, you will still get a good grade (be warned that if you put no effort into the course, you will most likely not end up doing a good job on the presentation).
There will be three 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 primarily be determined by an in-class presentation. I’ll finalise the details of this once enrollment number stabilise, but here is some initial information:
- The format will be that in the last few weeks of quarter, three 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 1h-session by 3 students.
- You must coordinate with two 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 12.15PM sharp (since we have exactly 3x20min-slots each class).
Calendar for presentations (30 slots): Before the end of week 3 (04/15/2022) each group of 3 students must send me an email with the names of the members of the group and what time slots you would like to avoid (with a precise explanation on why this is the case).
- 05/16 (12:15 PM – 1:15 PM) —>
- 05/18 (12:15 PM – 1:15 PM) —>
- 05/20 (12:15 PM – 1:15 PM) —>
- 05/23 (12:15 PM – 1:15 PM) —>
- 05/25 (12:15 PM – 1:15 PM) —>
- 05/27 (12:15 PM – 1:15 PM) —>
- 05/30 (12:15 PM – 1:15 PM) —>
- 06/01 (12:15 PM – 1:15 PM) —>
- 06/01 (1:15 PM – 2:15 PM) —>
- 06/01 (2:15 PM – 3:15 PM) —>