ENEE 729p: Modern Discrete Probability

Fall 2019

Instructors : Alexander Barg, Ohad Elishco
Department of Electrical and Computer Engineering/Institute for Systems Research
Office: 2361 A.V.Williams Building. E-mails: abarg at  umd  dot edu and elishco at  gmail  dot com

Class times:
Lectures: Monday, Wednesday 12:30 - 1:45pm, AJC2121
Instructor availability outside class hours: Please approach us after class, and we will stay as long as needed to clear the questions. Otherwise, please send one of us 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: The lectures draw on multiple sources. Most topics of the course are covered in the book by Pierre Brémaud referenced as [B17] below. This will be our main textbook.

Grading: 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 10/2) | Problem set 2 (by 11/4) | Problem set 3 (by 12/4) | Final (by 12/16) |
Solutions: | 1 | 2 | 3 |

Detailed contents of the course: (approximate outline)

Random graphs
Lecture 1. A quick reminder of probability theory: Random variables, moments. [B17, Ch.1,2]. Examples: The Erdős-Ko-Rado and Sperner theorems [AS16], Models of random graphs and the notion of thresholds [B17, Ch.10], [FK16].
Lecture 2. The first and second moment methods. Ensembles $G_{n,m}$ and $G_{n,p}$. [B17, Sec10.2], [FK16, Ch.1].
Lecture 3. (9/4) Thresholds for monotone properties. The Bollobas-Thomason theorem (every monotone property has a threshold) [FK16, Ch.1]
Lecture 4. Evolution of random graphs: Sub-critical and super-critical phases. [B17, Sec.10.2], [FK16, Ch.11]
Lecture 5. (9/11) Threshold for connectivity [FK16, Sec.4.1]. The critical regime and the Giant Component [B17, Sec.10.2.3], [AS16].

Percolation; Random geometric graphs
Lecture 6. (9/16) Bond percolation on Z2 [B17,Ch.10], [PL16].
Lecture 7. (9/18) The Galton-Watson branching process and percolation on regular trees. [PL16, Ch.5]
Lectures 8-9. (9/23,9/25) Random geometric graphs. Intersection graphs. [FK16, Ch.11]

Martingales; Concentration of measure
Lectures 10-11. (9/30, 10/2) Martingale methods: Convergence, stopping. Gambler's ruin and Polyá's urn models. Application to critical percolation on Td. [B17,Ch.17]
Lecture 12. (10/7) Doob's uncrossing inequality, convergence of martingales. Optional stopping theorems. [B17,Sec.17.3]
Lectures 13-14. (10/9,10/14) Concentration of measure: an introduction to classical inequalities (Chernoff, Hoeffding, Bennett/Bernstein). [BLM13, Ch.2] Extension to martingales; method of bounded differences. [B17], Sec.17.2

Analysis of Boolean functions, Isoperimetry
Lectures 15-17. (10/16-10/23) Fourier analysis of Boolean functions. Noise sensitivity and the Kahn-Kalai-Linial theorem. [GS14, Ch.1,2,5], [BLM13, Ch.9]
Lecture 18. (10/28) Completing KKL theorem. Introduction to isoperimetry. [BLM13], Sec.4.4, Ch. 7, Ch. 9
Lecture 19. (10/30) Influences and isoperimetry. Harper's theorems. Margulis-Russo lemma. [BLM13], Sec.4.4, Ch. 7, Ch. 9

Random walks; Markov chains; mixing and sampling
Lecture 20. (11/4) Introduction to Markov chains. Recurrence and ergodicity. [B17, Ch.6,7], [LPW17, Ch.2]
Lecture 21. (11/6) Stationary distribution. Examples of Markov chains. Mixing of Markov chains: distance to stationarity. [B17, Ch.6,7], [LPW17, Ch.4]
Lecture 22. (11/11) Coupling and bounds on the mixing time. Mixing for random walks on the hypercube and the cycle. [B17, Ch.16; Sec 20.3], [LPW17, Ch.4]
Lecture 23. (11/13) Bounds for mixing time of reversible Markov chains. Upper bounds via strong stationarity time. [LPW17, Ch. 6], [B17, Ch. 20]
Lecture 24. (11/18) Lower bounds on mixing. Hypercube walk and Top-to-Random shuffle. The bottleneck bound and Cheeger's constant. [B17, Ch. 20], [LPW17, Ch. 7],
Lecture 25. (11/20) Markov chain Monte Carlo. Metropolis algorithm and Glauber dynamics. [B17, Ch.19], [LPW17, Ch.3]
Lecture 26. (11/25) Path coupling, transportation method, and mixing rates of Glauber dynamics. [LPW17, Ch.14]
Lecture 27. (12/2) The Ising model. Mixing rate for Glauber dynamics at high temperature. [LPW17, Ch.14], [B17, Ch.9]
Lecture 28. (12/4) Random (sub-Gaussian) vectors and random matrices; Covariance estimation; applications to clustering [V18], Ch.2,3
Lecture 29. (12/9) Approximate isometries, including random projections (Johnson-Lindenstrauss). [V18], Ch.4,5

Student presentations

Textbook and supplementary sources:

[B17] P. Brémaud, Discrete Probability Models and Methods, Springer, 2017. (google book preview)

[FK16] A. Frieze and M. Karonski, Introduction to random graphs, Cambridge University Press, 2016. Online version
[LPW17] D. A. Levin and Y. Peres, Markov chains and mixing times, 2nd Ed., American Mathematical Society, 2017. Online version
[BLM13] S. Boucheron, G. Lugosi, P. Massart, Concentration inequalities, Oxford University Press, 2013. Online version
[GS14] C. Garban and Jeffrey 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
[R15] S. Roch, Modern Discrete Probability: An Essential Toolkit. Lecture Notes, close to our set of topics.
[G18] G. Grimmett, Probability on Graphs, Cambridge University Press, 2018. Online version
[W91] D. Williams, Probability with Martingales, Cambridge University Press, 1991 (an undergraduate course)

Student presentations

1. Please team up into groups of two (a small number of groups of one is also permissible).
2. The list of papers is given below. It's OK if you suggest a paper of your choice, but please receive instructor's approval in advance. If you cannot locate the paper, please let me know, and we will find ways to access it. Some of the papers, cited in their final version, may be available on preprint servers such as arXiv.
3. Your presentation should be 17min long (this may change later depending on the number of groups) and prepared on slides. It is expected that only one student from each group will give the presentation; however, it is imperative that the entire group takes active role in preparing it.
4. 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.

We will have two dates for presentation: Friday Dec. 6 and Tuesday Dec. 10 (time and place are given in the shared Excel sheet). Please send me an email to sign up for one of the two dates (first come first serve).

List of papers
1. D. B. Wilson. Generating random spanning trees more quickly than the cover time, Proc. 1997 ACM Sympos. Theory of Computing (STOC), pages 296–303.
2. N. Alon and M. Krivelevich. The concentration of the chromatic number of random graphs Combinatorica, vol. 17, no. 3, 1997, pp.303–313.
3. D. Achlioptas. Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journal of Computer and System Sciences, vol.66, no. 4, 2003, pp.671–687.
4. D. Achlioptas, A. Naor, and Y. Peres. Rigorous location of phase transitions in hard optimization problems, Nature, vol.435, 2005, pp.759–764.
5. M.T. Barlow and E. A. Perkins, Symmetric Markov chains in $Z^d$: How fast can they move? Probability Theory and Related Fields, vol. 82, 1989, pp. 95--108.
6. E. J. Candes, J. Romberg, and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory, vol. 52, no.2, 2006, pp. 489–509.
7. P. Diaconis and R.Freedman, De Finetti's theorem for Markov chains, The Annals of Probability, vol. 8, no. 1, 1990, pp.115-130.
8. M. Ajtai, J. Komlos, and E. Szemeredi, The longest path in a random graph, Combinatorica, vol. 1, 1981, pp.1-12.
9. D. Aldous and B. Flannery, Two applications of urn processes, Probability in the Engineering and Informational Sciences, vol. 2, 1988, pp. 293-307.
10. D. Aldous and P. Diaconis, Shuffling cards and stopping times, The American Mathematical Monthly, vol. 93, no. 5, pp. 333–348.
11. E. Lubetzky and A. Sly, Cutoff phenomena for random walks on random regular graphs, https://arxiv.org/abs/0812.0060 (Duke Matehmatical Journal, vol. 153, no. 3, 2010, pp. 475-810.
12. N. Madras and D. Randall, Factoring graphs to bound mixing rates, Prov. 37 IEEE Sympos. on Foundations of Computer Science, 1996, pp. 194-203.
13. K. Marton, Bounding d-distance by information divergence, The Annals of Probability, vol.24, 1996, pp. 857-866.
14. B. Recht, A simpler approach to matrix completion, arXiv:0910.0651 (Jounral of Machine Learning Research, vol.12, pp.3413-3430, 2011).
15. E. Friedgut, Hunting for sharp thresholds, Random Structures and Algorithms, vol. 25, no.1-2, 2005, pp. 37-51.
16. S. Blackburn and S. Gerke, Connectivity of the uniform random intersection graphs, arXiv:0805.2814 (Discrete Mathematics, vol. 209, no. 16, 2009, pp. 5130-5140).
17. L. Shepp, Covering the circle with random arcs, Israel Journal of Mathematics, vol.11, no. 3, 1972, pp.328-345.
18. R. Pemantle, Phase Transition in Reinforced Random Walk and RWRE on Trees, The Annals of Probability, vol. 16, no.3, 1988, pp.1229-1241.
19. G.-Y. Chen and L. Saloff-Coste, Comparison of cutoffs between lazy walks and Markovian semigroups, Journal of Applied Probability, vol. 50, no. 4, 2013, pp. 943-959.
20. C. Kenyon, E. Mossel, and Y. Peres, Glauber dynamics on trees and hyperbolic graphs, 42nd IEEE Sympos. Foundations Comp. Sci., pp.568-578.
21. P. Diaconis and L. Saloff-Coste, What do we know about the Metropolis algorithm, Journal of Computer and System Sciences, Volume 57, Issue 1, August 1998, Pages 20-36.
22. P. Diaconis and L. Saloff-Coste, Logarithmic Soboloev inequalities for finite Markov chains, The Annals of Applied Probability, 1996, vol.6, no. 3, pp.696-750.