Stochastic models
Fall 2013 at the Central European University

Lecturer: Gábor Pete

Lectures: Thursdays 10:45-13:15, Zrínyi utca 14, room 301

Email: my first name at math dot bme dot hu

Office hours: see here.

Course syllabus: here in .doc format

Exams:

Details for the exam projects are here.

Homeworks:

Here. The list will keep growing. Please hand in the solutions to four of them by Oct 24. Another four by Nov 28.

Diary:

1.) Sept 19. Pólya’s theorem (1920): random walk on Z^2 is recurrent, while transient on Z^d for d>2. Return probability after n steps (heat kernel decay): n^{-d/2}. Use of Stirling’s formula, the Central Limit Theorem, and the Azuma-Hoeffding large deviations bound. [See my PGG book, linked below, Section 1.1]

2.) Sept. 26. Return probabilities on the d-regular tree T_d, by computing the radius of convergence of Green’s function. Proof of Azuma-Hoeffding. Speed of random walk on transitive graphs exists, and is positive on the tree T_d. Notion of Cayley graphs of groups; free groups, lamplighter graphs. Rate of escape of SRW on lamplighter graphs. [PGG Sections 1.1, 1.2, 2.1, Thm 9.5]

3.) Oct. 3. Martingales and discrete harmonic functions. Liouville property for bounded harmonic functions on recurrent graphs and Z^d and lamplighter groups over Z and Z^2. Stating the Kaimanovich-Vershik theorem (1983) on equivalence of Liouville property and zero speed. [PGG Sections 6.3, 9.2]

4.) Oct. 10. Non-Liouville property for T_d. Reversibility of Markov chains. Electric networks and discrete potential theory: Markov operator, gradient, co-gradient, voltage, flow, current, effective resistance. [PGG Sections 9.2, 6.1. Can also have a look at Levin-Peres-Wilmer Chapters 1 and 9, or Lyons-Peres Chapter 2]

5.) Oct. 17. Dirichlet energy and transience. Amenability of graphs (Følner 1955). Exponential growth does not imply non-amenable: lamplighter groups. Quasi-isometry invariance of transience, growth and amenability. [PGG Sections 6.2, 3.1, 5.1]

6.) Oct. 24. Exponential rate of heat kernel decay is the same as spectral radius and the Markov operator norm. Rough sketch of proof of the Kesten-Cheeger-Dodziuk-Mohar theorem on the spectral radius characterization of non-amenability. [PGG Sections 7.1, 7.2]

7.) Oct. 31. Stating the generalization by Varopoulos at al: d-dimensional isoperimetry implies a decay of p_n(x,x) < Cn^{-d/2}; exponential growth implies x/log x isoperimetry, which implies p_n(x,x) < \exp(-c n^{1/3}). Cheeger constant for finite chains, and Alon-Milman bounds for the spectral gap. Examples of spectra of graphs and mixing times of random walks: complete graph, hypercube, cycle, expanders. [PGG Sections 7.2, 7.3]

8.) Nov. 7. Large spectral gap implies fast uniform mixing. Different notions of mixing time of random walks on finite graphs: relaxation time, uniform distance, total variation distance. Coupling characterization of total variation distance. Stating the Lovász-Kannan and Morris-Peres theorems using the isoperimetric profile. Random d-regular graph has large essential girth. [PGG Sections 7.3, 8.2]

9.) Nov. 14. Example showing that maximal expected hitting time might be much larger than uniform mixing time. The Erdős-Rényi (1960) graph model. Standard coupling. Notion of phase transitions. First and second moment method for containing a triangle. [PGG Section 12.2]

10.) Nov. 21. Another look at sharp thresholds: Russo's formula. Galton-Watson trees and the giant cluster in the Erdős-Rényi graph. Barabási-Albert graphs.

11.) Nov. 28. Percolation on transitive graphs.

12.) Dec. 5. Some models of statistical physics.

Bibliography:

Geoffrey Grimmett. Probability on graphs. Cambridge University Press, 2010. http://www.statslab.cam.ac.uk/~grg/books/pgs.html.

Remco van der Hofstad. Random graphs and complex networks. Book in preparation, http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf

David Levin, Yuval Peres, Elizabeth Wilmer. Markov chains and mixing times. American Mathematical Society, 2008. http://pages.uoregon.edu/dlevin/MARKOV/.

Russ Lyons with Yuval Peres. Probability on trees and networks. Book in preparation, to appear at Cambridge University Press. http://mypage.iu.edu/%7Erdlyons/prbtree/prbtree.html

Gábor Pete. Probability and geometry on groups. Book in preparation. PGG.pdf