Quicklinks: General Information, Lecture Notes

Description

The goal of this course is to introduce students to fundamental models and techniques in graduate-level modern discrete probability. Topics to be covered will be taken from: percolation, random graphs, Markov random fields, random walks on graphs, probabilistic combinatorics, etc. No attempt will be made at covering these areas in depth. Rather the emphasis will be on illustrating common and important techniques.

The course is aimed at graduate students in mathematics, statistics, computer science, electrical engineering, physics, economics, etc. with previous exposure to basic probability theory (ideally measure-theoretic probability theory as covered in Math 733) and stochastic processes (as covered in Math 632), although there is no formal prerequisite.

General Information

• Instructor: Sebastien Roch
• Email: Use Piazza for all communications. I will use Piazza to send out corrections, announcements, etc. Please check our Piazza board regularly. Click here to sign up. It is a free service.
• Time and place: MoWeFr 1:20PM - 2:10PM in VAN VLECK B129
• Office hours: By appointment.
• Prerequisites: No formal prerequisite. A graduate course in measure-theoretic probability (e.g. MATH/STAT 733) will be very useful.
• Texts (not required): Topics to be covered will be taken (among other sources) from the following texts conveniently available online
  • [vdH] Random Graphs and Complex Networks. Vol. I by van der Hofstad
  • [LP] Probability on Trees and Networks by Lyons with Peres
  • [LPW] Markov Chains and Mixing Times by Levin, Peres and Wilmer
  • [St] A Mini Course on Percolation Theory by Steif
  • [Gr] Probability on Graphs by Grimmett
  • [Lu] Concentration-of-measure Inequalities by Lugosi
• Grades will be based on several homework assignments. See the syllabus on Piazza.

Lectures Notes

UPDATE [Sep 1, 2015]: The latest version of the lecture notes can be accessed here.

Here is an ambitious tentative outline. We will cover a subset of what follows. Lecture notes will be posted below as they become available.

Front and back matter (last updated: sep 16, 2014)

Some fundamental models [slides (last updated: oct 3, 2014)]

• Topics (tentative): Review. Percolation, random graphs, Markov random fields, random walks on networks, interacting particles on finite graphs.

Moments and tails [notes (last updated: oct 3, 2014)]

• Topics (tentative): First moment method. Second moment method. Chernoff-Cramer method. Applications to percolation on trees and lattices (critical value), Erdos-Renyi graphs (containment problem), Markov chains (Varopoulos-Carne bound), and Johnson-Lindenstrauss lemma.

Martingales and potential theory [slides for the first section and notes for the rest (last updated: oct 27, 2014)]

• Topics (tentative): Review. Azuma-Hoeffding inequality and method of bounded differences. Electrical networks. Applications to Markov chains (hitting and cover times, recurrence), Erdos-Renyi graphs (chromatic number), preferential attachment graphs (degree sequence), and uniform spanning trees (Wilson's method).

Coupling [slides for the first section and notes for the rest (last updated: nov 20, 2014)]

• Topics (tentative): Coupling inequality. Stochastic domination. FKG inequality. Bounding mixing via coupling. Applications to Markov chains (mixing times, Glauber dynamics), Erdos-Renyi graphs (degree sequence, Janson's inequality), 2d percolation (Harris' theorem), and Ising model (extremal measures).

Branching processes [slides for the first section and notes for the rest (last updated: nov 20, 2014)]

• Topics (tentative): Review. Comparison to branching processes. Applications to random walk on Galton-Watson trees, percolation on trees, and Erdos-Renyi graphs (phase transition).

Spectral techniques [slides for the first section (last updated: dec 1, 2014)]

• Topics (tentative): Spectral gap. Expansion. Eigenvalues and isoperimetry. Applications to Markov chains (mixing times, Glauber dynamics), expanders, and percolation (uniqueness of infinite cluster).

Correlation

• Topics (tentative): Correlation decay. Dependency graphs. Lovasz local lemma. Chen-Stein method. Exchangeability. Applications to Ising model (uniqueness, reconstruction), occupancy problems (birthday paradox, species sampling), and random partitions.

More on concentration and isoperimetry (We will not get this far, but notes will eventually be available.)

• Topics (tentative): Poincare inequalities. Canonical paths method. Talagrand's inequality. Influence. Applications to Markov chains (mixing times) and 2d percolation (Kesten's theorem).