Academics / Courses / DescriptionsCOMP_SCI 496: Modern Discrete Probability
Academics
/ Courses
/ Descriptions
VIEW ALL COURSE TIMES AND SESSIONS
Prerequisites
Strong background in probability and stochastic processes, at the level of IEMS 460-1 or permission of the instructor.Description
This is a graduate-level course focused on techniques and models in modern discrete probability. Topics include: the first and second moment methods, martingales, concentration inequalities, branching processes, percolation, and Markov chains. Examples will be drawn from random structure and algorithm applications. The goal of the course is to equip students to carry out their own research using the toolkit of discrete probability.
- Cross-listed with IEMS 490
TOPICS
1. First and Second Moment Methods (3 lectures)- Markov inequality
- Chebyshev inequality
- Paley–Zygmund inequality
- Applications: the Erd˝os–Rényi random graph model (connectivity threshold, subgraph counts, maximum clique size); percolation on Zd and on the binary tree
2. Chernoff Bounds and Large Deviations (3 lectures)
3. Martingales and Concentration (4 lectures)- Doob’s Upcrossing Inequality
- Martingale Convergence Theorem
- Optional Stopping Theorem
- Azuma–Hoeffding and McDiarmid inequalities; applications to graph coloring, balls and bins, longest common subsequence
- Galton–Watson trees
- Percolation on the d-ary tree
- Giant component in sparse Erd˝os–Rényi random graphs
- Mixing time
- Coupling
- Glauber dynamics
- Spectral methods
- Path coupling
- Lower bounds on mixing time
- MCMC
- Correlation inequalities (e.g. FKG bound)
- Janson’s inequality; application to triangles in Erd˝os–Rényi random graphs, chromatic number
- Efron–Stein inequality
- Talagrand’s inequality
GRADING
50% for problem sets, 20% for the take-home midterm, 30% for the take-home final exam.
COURSE COORDINATORS: Julia Gaudio
COURSE INSTRUCTOR : Julia Gaudio