ENEE 729p: Modern Discrete Probability
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
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:
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)[FK16] A. Frieze and M. Karonski, Introduction to random graphs, Cambridge University Press, 2016. Online version
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.