Random Processes on Graphs and Lattices

Random Processes on Graphs and Lattices (STATS221, Winter 2020)

Building on undergraduate probability (Stats116), and on previous exposure to Markov chains (Stats217), we cover modern topics in the study of random processes on graphs and lattices, in a non-measure-theoretic way. Specifically:

The connection between reversible Markov chains, electrical networks and flows.
The study of random graphs, uniform spanning trees, Percolation and self-avoiding walks.
Dynamics of interacting particles: the contact process, voter model and the exclusion process.
Gibbs states, in particular the Ising, Potts and Random-Cluster models.

Whereas Stats218 and Stats219 aim at studying martingales and Brownian motion, by focusing on discrete objects we give in Stats221 complete proofs (without measure theory or functional analysis background).

In contrast with Stats217, we deal here with topics of active current research (and in the course of the term, you will encounter quite a few well known open problems and tantalizing conjectures).

Prerequisites: Students should be comfortable with Markov chains and Poisson process, at the level of Stat217 (syllabus) and with real analysis at the level of Math115 (syllabus).

Text (on reserve at science library):

Grimmett, Probability on Graphs, second edition.

Meeting: Sequoia 200, Tu/Th 12:00-1:20pm.

Instructor: Amir Dembo, office hours (held up to 3/8): Seqouia 129, Th 3:30-4:20pm, or e-mail adembo at stanford.edu (please include STATS221 in your email subject).

CA: Theo Misiakiewicz, office hours (held up to 3/5): Sequoia 207, Tu 5:00-6:00pm; Sequoia 105, We 5:00-6:00pm or e-mail (please include STAT221 in your email subject).

Grading : Judgement based on consistent Homework effort (35%) with remaining (65%) grade based on in-class presentation. Specifically, registered students present material not covered in lectures and attend all other student presentations (each student delivering a 25min presentation within a team of 2-3 that covers a topic of mutual interest). Revised: Grade based solely on Homework effort (100%).

Presentations: (Thurday, 3/12, 12:00-1:20pm, Friday, 3/20, 12:15-3:15pm at Sequoia 200). CANCELED!

Homework of 2020: Problems from the text book as listed on HW1--HW8 are due each Thursday 12:00pm, on a weekly basis (Solutions: see Canvas page). Collaboration allowed in solving the problems, but you are to provide your own independently written solution. Please deliver your assignment to class on due date (late homework solutions will not be graded).

Schedule (from text; preferable to read before class):

1/6        Tu(1.1;1.2;1.6)            Th(1.3;1.4) 
1/13       Tu(1.4;1.5;2.1)            Th(2.1;2.2)   
1/20       Tu(2.2)                    Th(3.1;3.4;3.2)
1/27       Tu(3.2;3.5;4.1)            Th(4.1;4.2)
2/3        Tu(4.3;4.4)                Th(4.5;4.7) 
2/10       Tu(6.1;6.2;6.3)            Th(6.3;6.4;6.5)                       
2/17       Tu(6.5;7.1)                Th(7.3;7.2)
2/24       Tu(8.1;8.2;10.1)           Th(10.2;10.3)
3/2        Tu(10.3;10.4)              Th(11.1;11.2)
3/9        Tu(---)                    Th(---)

See also seminar for current activity in related areas.