Modern Discrete Probability

ENEE729p / CMSC858Z / MATH729P, Spring 2023

Instructor : Alexander Barg
Department of Electrical and Computer Engineering/Institute for Systems Research
Office: 2361 A.V.Williams Building. E-mail: abarg at umd dot edu

TA : Madhura Pathegama, Email: pankajap at  umd dot edu

Class times:
Lectures: Monday, Wednesday 11:00 - 12:15, AJC 2132
Instructor availability outside class hours: Please approach me after class, and we will stay as long as needed to clear the questions. Otherwise, please send me an email.

Course Homepage: http://www.ece.umd.edu/~abarg/MDP

Course description: This is a graduate-level introduction to probabilistic reasoning for discrete systems. We will cover several foundational models and methods that are widely used in modern research of stochastic systems and phenomena. They find applications in learning, classification, data analysis, sparse recovery. The models include random graphs, Markov chains and mixing times, dynamics of graphical models, random matrices, as well as mathematical tools used in the analysis. The class will focus on specific systems, and one of the central topics will be threshold behavior.

Prerequisites Good knowledge of undergraduate probability theory on the level of STAT410 or ENEE620 (Chapters 1 and 2 in [B17] should suffice as an introduction. The concepts will be recalled as needed in class.). Exposure to mathematical reasoning, particularly linear algebra and analysis. The course does not rely heavily on measure-theoretic probability.

Textbook: None. The lectures draw on multiple sources, see references below.

Grading: 2-3 Homeworks (30%), End of course presentation (40%), Take home exam (30%)
Presentation topics and materials will be distributed halfway into the course.

Course contents: A subset of the following topics will be covered:

  1. Probabilistic method. First and second moment methods. Applications to random graphs and percolation. The Erdos-Renyi phase transition, branching processes [AS16,FK6]

  2. Inequalities and measure concentration. Martingales and the method of bounded differences [BLM13,AS16]. The Azuma-Hoeffding inequality, Talagrand's inequality [AS16,BLM13]. Logarithmic Sobolev inequalities, hypercontractivity, isoperimetry. Thresholds and sharp thresholds for monotone properties.

  3. Mixing of Markov chains. Glauber dynamics, Metropolis chains, coupling and mixing times [LPW17]. Card shuffling; Polya's urn models.

  4. Geometric problems. Random projections, the Johnson-Lindenstrauss lemma, and sparse recovery. Epsilon-nets and the VC dimension [BLM13,AS16].

  5. Influences of variables. Analysis on the Boolean cube. Discrete Fourier analysis. The Kahn-Kalai-Linial theorem [BLM13,GS14].

  6. Coupling and the Ising model. Gibbs measures. Fast mixing of the Ising model on graphs [LPW17].

Home assignments:  Problem set 1 (by 3/9) | Problem set 2 (by 04/09) | Final (by 5/14) |
Solutions: | Prob. set 1 | Prob. set 2

Detailed contents of the course:

   Random graphs
Lecture 1. (1/25) A quick reminder of probability theory: Random variables, moments. [B17, Ch.1,2]. Examples: The Erdős-Ko-Rado and Sperner theorems [AS16], Models of random graphs and the notion of thresholds [B17, Ch.10], [FK16].
Lecture 2. (1/30) The first and second moment methods. Ensembles $G_{n,m}$ and $G_{n,p}$.
  Reading: [R23], Sec.2.1.1, 2.3.1; [FK16], Sec.1.1 (up to lemma 1.2).
Lecture 3. (2/1) Thresholds for monotone properties. The Bollobas-Thomason theorem (every monotone property has a threshold)
  Reading: [FK], Sec.1.2 (up to Thm.1.12); [R23], Claim 2.2.5; [FK], Sec.2.1 (first few pages).
  [Corrected lecture notes on Canvas]
Lecture 4. (2/6) Evolution of random graphs: Sub-critical and super-critical phases.
  Reading: [R23], Sec 2.3.2; [FK], Sec.2.1 (up to Thm.2.5); Sec.2.2 (first few pages).
Lecture 5. (2/8) Subgraphs of random graphs and the connectivity threshold.
  Reading: [R23], Sec 2.3.2, [FK16, Sec.4.1].
Lecture 6. (2/13) Bond percolation on Z2
  Reading: [R23], Sec 2.2.4, Yadin, Sec.~2.1, 2.2; Concise discussion in [G18], Sec. 3.1
Lecture 7. (2/15) Bond percolation on Z2
  Reading: same as Lec. 6; also H. Duminil-Copin's overview of $\lambda({\mathbb H})=\sqrt{2+\sqrt 2}$
Lecture 8. (2/20) Random geometric graphs. Intersection graphs.
  Reading: [FK16] Sec.12.1 (first few pages), Sec.12.2 (first few pages).

   Martingale methods
Lecture 9. (2/22) Martingale methods: Convergence, stopping. Examples.
  Reading: [R23], Sec.3.1.3-3.1.4; [D19], Sec.4.1.1, 4.1.2; 4.3.
No lectures on February 27 and March 1
Lecture 10. (3/6) Convergence and convergence in $L^1$. Application to critical percolation on Td.
  Reading: [D19], Sec.4.1.1, 4.1.2; 4.3; [R23], Sec.3.1.4
Lecture 11. (3/8) Optional stopping, examples.
  Reading: [D19], Sec.4.8.
Lecture 12. (3/13) Bounded differences and Hoeffding inequality. Applications: Concentration of $\chi(G_{n,p}).$ Degree sequence in preferential attachment graphs.
  Reading: [R23], Sec.3.2.4-3.2.5
Lecture 13. (3/15) Lec.12 cont'd: Degree sequence in preferential attachment graphs. Multi-armed bandits.
  Reading: [R23], Sec.3.2.4-3.2.5
Lecture 14 (3/20) Regret estimate for 2-armed bandits.
  Reading: [R23], Sec.3.2.4-3.2.5; [LPW17], Sec.1.1-1.4

   Markov chains; mixing and sampling
Lecture 14(a) General intro to Markov chains (a 3-part recording on Canvas)
  Reading: Markov chain notes
Lecture 15. (3/27) Markov chains: Overview of basic properties. Examples.
  Reading: [LPW17], Sec.2.1-2.3
Lecture 16. (3/29) Strong Markov property. Total variation distance and rate of convergence.
  Reading: [LPW17], Sec. 4.1-4.3; 5.1, 5.2
Lecture 17. (4/3) Coupling and bounds on the mixing time. Distance to stationarity. Mixing of random walks on the hypercube and cycle.
  Reading: [LPW17], Sec. 5.1-5.3
Lecture 18. (4/5) Reversibility. Random walks on finite groups. The symmetric group and card shuffling.
  Reading: [LPW17], Sec. 8.1-8.2
Lecture 19. (4/10) Strong stationary time. Mixing times for Top-to random and riffle shuffle.
  Reading: [LPW17], Sec. 6.4-6.5
Lecture 20. (4/12) Mixing time for riffle shuffle. Lower bounds on mixing: The bottleneck bound, examples.
  Reading: [LPW17], Sec.8.3; Sec.7.1, 7.2
Lecture 21. (4/17) Lower bounds for mixing. Random expanders. Mixing of random walks on expanders.
  Reading: [LPW17], Sec.8.3; Sec.7.1, 7.2; [R23], Sec.5.3.3.
Lecture 22. (4/19) Markov chain Monte Carlo. Metropolis algorithm and Glauber dynamics.
  Reading: [LPW17], Sec.3.1-3.3, [R23], Sec.4.4.4
Lecture 23. (4/24) Path coupling; Dobrushin's contraction theorem. Fast mixing of Glauber dynamics for colorings.
  Reading: [LPW17], Sec.14.1-14.3
Lecture 24. (4/26) Gibbs random fields. The Ising model.
  Reading: [LPW17], Sec.15.1, [R32], Sec.4.3.2

   Boolean analysis; Influences and isoperimetry
Lecture 25. (5/1) Fourier analysis of Boolean functions. Noise sensitivity and influences
  Reading: [OD14], Sec.1.1-1.5
Lecture 26. (5/3) Noise sensitivity and stability. Hypercontraction. Arrow's theorem and the KKL theorem
  Reading: [OD14], Sec.2.4-2.5; 9.1, 9.6
Lecture 27. (5/8) Influences and isoperimetry. Harper's theorems. Margulis-Russo lemma.
  Reading: [BLM13], Sec.4.3-4.4; 7.1, 9.6

References:

Main
[FK16] A. Frieze and M. Karonski, Introduction to random graphs, Cambridge University Press, 2016. Online version, 2022.
[LPW17] D. A. Levin and Y. Peres, Markov chains and mixing times, 2nd Ed., American Mathematical Society, 2017. Online version
[R23] (previous edition [R15]) S. Roch, Modern Discrete Probability: An Essential Toolkit. Lecture Notes, close to our set of topics.
[OD14] R. O'Donnell, Analysis of Boolean functions, Cambridge University Press, 2014. Online version

Supplementary
[G18] G. Grimmett, Probability on Graphs, Cambridge University Press, 2018. Online version
[BLM13] S. Boucheron, G. Lugosi, P. Massart, Concentration inequalities, Oxford University Press, 2013. Online version
[D07] R. Durrett, Random Graphs Dynamics, Cambridge 2007 Online version
[GS14] C. Garban and J. E. Steif, Noise sensitivity of Boolean functions and percolation, Cambridge University Press, 2014, Online version
[PL16] R. Lyons and Y. Peres, Probability on trees and networks, Cambridge University Press, 2016. Online version
[V18] R. Vershynin, High-dimensional probability. An Introduction with Applications in Data Science, Cambridge University Press, 2018. Online version
[AS16] N. Alon and J. Spencer, The probabilistic method, 4th Ed. (or earlier), J. Wiley & Sons, 2016. Online version
[vH16] R. Van Handel, Probability in high dimension, Lecture notes for APC 550 course (Princeton University), 2016. online
[B17] P. Brémaud, Discrete Probability Models and Methods, Springer, 2017. (google book preview)

General references on probability
[D19] R. Durrett, Probability: Theory and Examples, 2019 [online]
[W91] D. Williams, Probability with Martingales, Cambridge University Press, 1991

Similar courses: Princeton, Wisconsin, MIT

Student presentations
1. The dates are Wed. 5/10, 10:00-1:00 and Fri 5/12, 11:00-2:00, AJC 2132.
2. Please team up into groups of two (a small number of groups of one is also permissible) and sign up here. Signing is on a first-come first-serve basis.
3. Your task is to present a problem and explain a solution, summarizing the main steps of the proof. You are not expected to present the entire contents of the paper; please isolate the main result(s) and focus on it/them. If the problem is motivated by interesting applications, please do mention them, too. Your goal is to enable your audience to take something home with them as a result of your presentation.