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 Bré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:

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

Solutions: | 1 | 2 | 3 |

**Textbook and supplementary sources:**

[B17] P. Brémaud, **Discrete Probability Models and Methods**, Springer, 2017. (google book preview)

[LPW17] D. A. Levin and Y. Peres,

[BLM13] S. Boucheron, G. Lugosi, P. Massart,

[GS14] C. Garban and Jeffrey E. Steif,

[PL16] R. Lyons and Y. Peres,

[V18] R. Vershynin,

[AS16] N. Alon and J. Spencer,

[vH16] R. Van Handel,

[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.