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