Academics
  /  
Courses
  /  
Descriptions
COMP_SCI 496: 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, 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
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

 

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