MATH 548: Discrete probability

Omer Angel

September 2018

Lecture topics

2018-09-04 Course overview
2018-09-06 Electrical networks, harmonic functions, existence and uniqueness for Dirichelet problems, voltage as hitting probabilities. Following Lyons-Peres.
2018-09-11 Effective conductance and resistence, equivalence to recurrence and transience. Star and cycle spaces.
2018-09-13 Rayleigh Monotonicity Principle, random paths, Nash-Williams bound, Recurrence and transience of Z^d, resistance and return probabilities in Z^2.
Assignment 1 Due 2018-09-25. problems, LaTeX
Assignment 2 Due 2018-10-19. problems, LaTeX
2018-10-30 Ising model: Gibbs measures, existence of limits and phase transitions.
2018-11-01 Phase transition for mixing of the Ising model: Curie Weiss model and the lattice. Spectral methods for reversible Markov chains.
Assignment 3 Due 2018-11-15. problems, LaTeX
2018-11-08 Percolation: definitions, critical probability, transition in Z^d.
2018-11-13 Percolation: Harris-FKG inequality, 0-1-infinity rule for transitive graphs, uniqueness in amenable graphs. No percolation in Z^2 at p=1/2.
2018-11-13 Percolation: Russo's formula, Russo-Seymour-Welsh, Sharpness of the phase transition (Duminil-Copin + Tassion)
Assignment 4 Due 2018-11-29. problems, LaTeX

Outline

Class hours: Tue-Thu 14:00-15:30, MATX 1118. If you are interested in this course and have a conflict with this time, please let me know.
Office hours: after class or by appointment.
Contact: Math annex 1210,        604.822.6532        angel at math dot ubc dot ca

Course Outline

We will discuss some of problems and modern tools of discrete probability. Topics will be some of the following:
  1. Random walks: their relation with electrical networks, Green's function, harmonic potential.
  2. Analysis of Markov chains: Spectral theory, mixing times isoperimetric estimates, Markov chain Monte-Carlo simulations.
  3. Random graphs and percolation: Erdos-Renyi random graphs, random regular graphs, Galton-Watson trees, preferential attachment and small world phenomena.
  4. Ergodic theory: Birkhoff's and mean ergodic theorems, recurrence theorems, applications (van-der Waerden's and Szemeredi's theorems).
  5. Percolation: Russo-Seymour-Welsh technology, the Harris-Kesten theorem, critical and off-critical behaviour, conformal invariance (Smirnov's theorem).
  6. Introduction to statistical mechanical models: The Ising and Potts models.

Prerequisites

You should be familiar with basic probability and Markov chains. For maximal benefit, students should have some knowledge of measure theory, and Martingales.

Evaluation

The grade will be based on problem sets normally due one-two weeks after they are assigned. Late assignments will not be accepted for credit. You are encouraged to work on solving the problems together. However, each of you must write your solutions independently. You may share ideas but you may not share your written work.

Textbooks and References

There is no single book that covers all parts of the course well. the following cover various aspects of the course, and can be used as references.