Academics
  /  
Courses
  /  
Descriptions
  /  
Keep
IEMS 490: Selected Topics in Modern Discrete Probability


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, Chernoff bounds and large deviations, 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. 

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 (connectivitythreshold, subgraph counts); percolation on \mathbb{Z}^d and on the binarytree
  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
  4. Branching Processes (2 lectures)
    • Galton–Watson trees
    • Percolation on the d-ary tree
    • Giant component in sparse Erd˝os–Rényi random graphs
  5. Markov Chains (6 lectures)
    • Mixing time
    •  Coupling
    • Glauber dynamics
    • Spectral methods
    • Path coupling
    • Lower bounds on mixing time
    • MCMC
  6. Additional Techniques (4 lectures)
    • 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
View Syllabus