Course Material

For practicum sessions on Local weak convergence click here

Date of Lecture	Material covered	Notes	Scribe
August 22	Motivation	Pages 1-9H of Lecture 1, Advice to graduate students	Scribe
August 24	Basic metric space theory	Pages 9I - 1.13, Additional readings on Metric spaces	Scribe
	Homework 0	See file	Scribe
August 29	Portmanteu theorem and convergence determining classes	Pages 1.14 - 1.24	Yiyao Luo pdf, tex
	Homework 1	See file	Scribe
August 31	Basic examples in \(\mathbb{R},\mathbb{R}^k,\mathbb{R}^\infty\)	Pages 1.14 - 1.24	Samopriya Basu tex, pdf
September 5	Basic examples: \(C[0,1]\), Product measures	Pages 2.1 - 2.8	Samopriya Basu tex, pdf
September 7	Covergence in probability, Continuous mapping theorem	Pages 2.9 - 2.21, Pages 3.1 - 3.4	Scribe
	Homework 2	See file	Scribe
September 12	Tightness and Prohorov’s theorem	Pages 3.5 - 3.19	Yiyun Luo tex, pdf
September 14	Weak convg. on \(\mathbb{R}\), Lindeberg CLT	Pages 4.1 - 4.8, Additional readings on CLT	Adam Waterbury tex, pdf
September 15	Practicum: Skorohod representation	Notes	Yiyun Luo tex, pdf
September 19	Stein’s method	Pages 4.10 - 4.22 Additional readings on Stein’s method	Aman Barot tex, pdf
	Homework 3	See file	Scribe
September 21	Poisson approximation, MOM, Characteristic functions	Pages 4.Poi-4.34, , Additional readings on MOM	Jin Wang
September 22	Practicum: Stein’s method	Notes, Additional readings	Peiyao Wang tex, pdf
September 26	Characteristic functions, Enter \(C[0,1]\)	Pages 4.34-4.35, Pages 5.1 - 5.11, Additional readings on Arzela-Ascoli	Scribe
September 28	\(C[0,1]\) continued	Pages 5.11-6.04	Zhengling Qi tex, pdf
October 3	Properties of Brownian motion	Pages 6.04-6.16, Additional readings on Brownian Motion	Duyeol Lee tex, pdf
October 5	Properties of Brownian motion contd	Pages 6.16-7.04	Miheer Dewaskar tex, pdf
	Homework 4	See file	Scribe
October 10	Strong Markov Property, Skorohod representation	Pages 7.05-7.16	Miheer Dewaskar
October 12	No class		-
	Homework 5	See file	Scribe
October 17	Donsker’s Theorem, Martingale FCLT	Pages 7.17-7.26	Michael Conroy tex, pdf
October 24	Martingale FCLT, Application to Random graphs	Pages 7.23-7.26 Pages 8.1-1-8.1-6 Further reading	Hang Yu tex, pdf
October 26	Application to Random graphs, Conditioned random walks	Pages 8.1-6-8.1-9, Pages 8.2-1 - 8.2-4	Scribe
October 31	Conditioned random walks, Tightness estimates in \(C[0,1]\), Introduction to Random trees	Pages 8.2-4-8.2-17, Pages 8.3-1 - 8.3-9	Ruituo Fan tex, pdf
	Homework 7	See file	Scribe
November 2	Introduction to Random trees	Pages 8.3-9 - 8.3-16, Pages 8.4-1 - 8.4-17, Further reading	Scribe
November 7	Random trees; Introduction to \(D[0,1]\); Skorohod topology	Pages 8.4-16 - 8.4-27, Pages 9.1 - 9.04, Further reading	Scribe
November 9	Introduction to \(D[0,1]\); Skorohod topology	Pages 9.04 - 9.19, Further reading	Weibin Mo tex, pdf
November 14	Tightness etc in \(D[0,1]\)	Pages 9.19 - 9.30, Further reading	Scribe
	Homework 8	See file	Scribe
November 16	Applications of \(D[0,1]\)	Pages 10.01 - 10.end, Further reading	Scribe
	Homework Cauchy Process capstone	See file	Scribe
November 21	Weak convergence of random measures	Pages 11.01 - 11.24, Further reading	Scribe
	Homework random measures capstone	See file	Scribe
November 27	Completing the proof of Wigner’s semi-circle law	Lecture 11	Scribe
November 30	Student talks 1	See Talks below for Schedule	Scribe
December 5	Student talks 2	See Talks below for Schedule	Scribe

Local weak convergence Lectures

I am planning to hold a focused module on local weak convergence on Fridays starting after Fall break. I will keep uploading lectures as I finish writing them. The practicum sessions are held on Fridays from 12:00 - 1:00 in Hanes 125

Date of Lecture	Material covered	Notes	Scribe
October 27	Basics of local weak convergence	Lecture 1 on LWC	Xi Yang tex, pdf
November 3	Introduction to factor models	Lecture 2 on LWC	Scribe
November 10	Belief propogation; LWC and the Ising model on sparse graphs	Lecture 3 on LWC	Scribe
November 17	Recursive distributional equations; going from trees to graphs	Lecture 4 on LWC	Scribe
December 1	LWC for weighted network models	Material	Scribe
	Homework 6	See file	Scribe

In addition to the references below see further readings on Local weak convergence for more research level papers on this topic from a wide array of fields.

Student talks

The last few days of the semester we will have student talks. I will setup the schedule after I have the entire list, but I have started collecting proposed topics below.

Date of Lecture	Speaker	Topic	Report
	#Day 1#	# Day 1#
11/30 (8:00-8:10)	Miheer Dewaskar	Graph Limits and Exchangeable Random Graphs	Talk Report
11/30 (8:12 - 8:22)	Hang Yu/Xi Yang	Random matrix theory and statistics	Talk Report
11/30 (8:24 - 8:34)	Michael Conroy/Adam Waterbury	Large deviations and Erdos-Renyi random graph	Talk Report
11/30 (8:36 - 8:46)	Samopriya Basu	Around the continuum random tree Chapter 2 of Evans	Talk Report
11/30 (8:48 - 8:58)	Peiyao Wang	Approximate message passing and compressed sensing	Talk Report
11/30 (9:00 - 9:10)	Yiyao Luo	Change point detection, CUSUM statistic	Talk Report
	#End of Day 1#	#End of Day 1#
	#Day 2#	# Day 2#
12/05 (8:00 - 8:10)	Ruituo Fan	Local weak convergence and probabilistic combinatorial optimization	Talk Report
12/05 (8:12 - 8:22)	Aman Barot	Asymptotic Fringe convergence of random trees	Talk Report
12/05 (8:24 - 8:34)	Duyeol Lee/Zhengling Qi	Central Limit Theorems and Bootstrap in High Dimensions	Talk Report
12/05 (8:36 - 8:46)	Weibin Mo	Non and semi-parametric MLE	Talk Report
12/05 (8:48 - 8:58)	Yiyun Luo	Random planar maps	Talk Report

Main references: Weak convergence

1. Convergence of Probability measures. Large parts of the course follow the 1968 book but we cover an assorted collection of special topics and examples.

2. Durret’s Probability Theory and examples Fantastic treatment of the Martingale FCLT in Chapter 8.

Main references: Local weak convergence

1. Aldous and Steele’s survey on the Objective method. Beautiful survey of the applications of the method in probabilistic combinatorial optimization by two masters in the field.

2. Benjamini and Schramm’s work on distribution limits of Planar graphs.

3. Dembo and Montanari’s work on Gibbs measures on sparse random graphs. Also see their Annals of Probability paper.

4. Side reading: Chapter 8 of Bishop’s pattern recognition and machine learning. Gives a nice overview of probabilistic graphical models. In particular Section 4 on message passing algorithms and their role in computing marginal distributions in the context of Markov random fields especially when the graphical structure is tree like was a fun read.

5. Montanari’s St. Flour lecture notes. Gives a number of complete proofs and a concise overview of the field.

Additional Readings

Advice for graduate students

• Aldous’s review of Spin glasses by Talagrand
• J. Michael’s Steele’s semi-random rants Lots of valuable advice for graduate students.
• Andrew Wiles’s advice for math research “But being stuck, Wiles said, isn’t failure. “It’s part of the process. It’s not something to be frightened of.””

Metric space fundamentals

• STOR BIOS Boot camp

Central Limit Theorem

• Alan Turing and the CLT Also has a nice description of the connections between statistics and Turing’s work during World War II in breaking the German enigma machine.
• Nice paper on extensions of the Lindeberg technique by Chatterjee Extensions of Wigner’s semi-circle law to exchangeable entries are also explored.

Stein’s method

• Nice survey on Normal approximation using Stein’s method
• Beautiful overview of Stein-Chen for Poisson approximation
• Remembering Wassily Hoeffding
• Beautiful thesis on exchangeable pairs and concentration inequalities
• Birthday problem and random trees Describes a way of constructing random trees using the birthday problem. Deep applications in a number of other areas including the study of the entrance boundary of the additive coalescent.

Method of moments

• Nice collection of worked out examples
• A powerful example by a master of the field (Svante Janson)
• Not MOM but a beautiful branch of applied probability: Power of two choices

Cramer-Wold device

• First 3 pages of this article has a nice application

Compactness/Arzela-Ascoli

• Comprehensive discussion of compactness etc on Terry Tao’s blog

Brownian Motion

As one might imagine, references for Brownian motion are almost infinite. The following two are most closely related to our class.

• Chapters 7 and 8 of Durrett: Probability Theory and examples
• Chapters 1 and 2 of Morters and Peres’s book on Brownian motion

Further reading on Critical random graphs

• The original Aldous classic
• Work of Janson, Knuth, Luczak and Pittel
• If you cared about the structure of maximal components
• Long paper with hopefully understandable introduction
• Minimal spanning tree (MST) on random graphs

Further reading on local weak convergence

See the main references for applications in settings like Factor models and machine learning. For more specialized applications:

• Asymptotic Fringe convergence of random trees (Aldous). One of the earliest papers on local weak convergence especially developed for trees. A classic!

• Graphical models and compressed sensing (Montanari): Surveys how message passing algorithms can be used to understand fundamental objects like the LASSO. See Donoho,Malekib and Montanari for a more technical description of the contributions. One line blurb from the abstract: “We introduce a simple costless modification to iterative thresholding making the sparsity–undersampling tradeoff of the new algorithms equivalent to that of the corresponding convex optimization procedures. The new iterative-thresholding algorithms are inspired by belief propagation in graphical models. Our empirical measurements of the sparsity–undersampling tradeoff for the new algorithms agree with theoretical calculations. We show that a state evolution formalism correctly derives the true sparsity–undersampling tradeoff.”

• Random matrix theory: See Bordenave and Lelarge; Bhamidi, Evans, Sen; See the following survey by Bordenave and Chafai for a beautiful description of the state of the art and many more references.

• Random Schrodinger operators: See Aizenmann and Warzel for rigorous results relating these problems to the “canopy” tree.

• Strategic learning on networks: Mossel, Sly and Tamuz

• Large deviations for graphs: Bordenave and Caputo

• Applications of such ideas in optimization: Here the number of applications are infinite! Just as a starting point, see for example

  • Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
  • Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality by Bayati, Shah and Sharma.
  • Also see Belief Propagation for Min-Cost Network Flow: Convergence and Correctness

• Community detection: See Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications and the multitude of papers that cite this for understanding how accurate the predictions of such methodology are for predicting “reconstruction limits” of models. See the work of Mossel, Neeman and Sly for a complete rigorous justification of these predictions.

Random trees

• We are mainly following this amazing survey on the state of the art: Random trees and applications by Jean-Francois Le Gall

• Another wonderful treatment: Steve Evans St. Flour lecture notes

• The following are the original Aldous classics: CRT 1, CRT 2 and CRT 3.

• Quanta magazine article on Unified Theory of randomness

• Application of trees in CS: Quora discussion

Skorohod topology

I still do not have great intuition for this space. In addition to the Chapter in Billingsley’s book, other places with good treatments of the fundamentals include:

• Chapter 3 of Ward Whitt’s book on Stochastic processes limits

• Chapter 6 of Jacod and Shiryaev’s book on Limit Theorems for Stochastic Processes

• Chapter 3 of Ethier and Kurtz’s book on Markov processes

Random measures

• The beginning of Chapter 3 of Ethier and Kurtz’s book on Markov processes as well as the 2000 edition of Billingsley do a great job in conveying how to view the space of probability measures \(\mathcal{P}(S)\) on a Polish space as complete seperable metric space using the Skorohod topology.

• For the most comprehensive treatment see Kallenberg’s masterful treatment in 2017. I mainly consulted the beginning of Chatper 1 and a little bit of Chapter 4. In particular the notion of a problem dependent “localizing” sequence was at first sight non-trivial to wrap my head around.

• Regarding random matrix theory, there are so many wonderful books and such deep results. For a quick overview, especially regarding the moment method, see this beautiful senior honor’s thesis Harvard thesis by Adina Roxanan Feier.

• Tracy Widom law and “At the Far Ends of a New Universal Law”

• Terrence Tao’s notes/book on random matrix theory

Topics to cover next time I teach this course