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:

*Probabilistic method.*First and second moment methods. Applications to random graphs and percolation. The Erdos-Renyi phase transition, branching processes [AS16,FK6]-
*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. -
*Mixing of Markov chains.*Glauber dynamics, Metropolis chains, coupling and mixing times [LPW17]. Card shuffling; Polya's urn models. -
*Geometric problems.*Random projections, the Johnson-Lindenstrauss lemma, and sparse recovery. Epsilon-nets and the VC dimension [BLM13,AS16]. -
*Influences of variables.*Analysis on the Boolean cube. Discrete Fourier analysis. The Kahn-Kalai-Linial theorem [BLM13,GS14]. -
*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

Reading: [R23], Sec.2.1.1, 2.3.1; [FK16], Sec.1.1 (up to lemma 1.2).

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]

Reading: [R23], Sec 2.3.2; [FK], Sec.2.1 (up to Thm.2.5); Sec.2.2 (first few pages).

Reading: [R23], Sec 2.3.2, [FK16, Sec.4.1].

Reading: [R23], Sec 2.2.4, Yadin, Sec.~2.1, 2.2; Concise discussion in [G18], Sec. 3.1

Reading: same as Lec. 6; also H. Duminil-Copin's overview of $\lambda({\mathbb H})=\sqrt{2+\sqrt 2}$

Reading: [FK16] Sec.12.1 (first few pages), Sec.12.2 (first few pages).

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

Reading: [D19], Sec.4.1.1, 4.1.2; 4.3; [R23], Sec.3.1.4

Reading: [D19], Sec.4.8.

Reading: [R23], Sec.3.2.4-3.2.5

Reading: [R23], Sec.3.2.4-3.2.5

Reading: [R23], Sec.3.2.4-3.2.5; [LPW17], Sec.1.1-1.4

Reading: Markov chain notes

Reading: [LPW17], Sec.2.1-2.3

Reading: [LPW17], Sec. 4.1-4.3; 5.1, 5.2

Reading: [LPW17], Sec. 5.1-5.3

Reading: [LPW17], Sec. 8.1-8.2

Reading: [LPW17], Sec. 6.4-6.5

Reading: [LPW17], Sec.8.3; Sec.7.1, 7.2

Reading: [LPW17], Sec.8.3; Sec.7.1, 7.2; [R23], Sec.5.3.3.

Reading: [LPW17], Sec.3.1-3.3, [R23], Sec.4.4.4

Reading: [LPW17], Sec.14.1-14.3

Reading: [LPW17], Sec.15.1, [R32], Sec.4.3.2

Reading: [OD14], Sec.1.1-1.5

Reading: [OD14], Sec.2.4-2.5; 9.1, 9.6

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.