Stochastic models
Fall 2014 at the Central European University

Lecturer: Gábor Pete

Lectures: Wednesdays 10:30-13:00, 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:

Last year's exam projects are here. I will update them soon.

Homeworks:

Here. The list will keep growing. Please hand in the solutions to four of them by Nov 12. Another four by Dec 8 Monday Rényi Kutszem in person or by Dec 12 in email.

Diary:

1.) Sept. 24. Snapshots of future topics: Pólya’s theorem on random walks, percolation theory, amenability of graphs, TASEP and Burgers' equation.

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.) Oct. 1. Proof of Azuma-Hoeffding. Return probabilities on the d-regular tree T_d, by computing the radius of convergence of Green’s function. Speed of random walk on transitive graphs exists, and is positive on the tree T_d. Stating the Kesten-Cheeger-Dodziuk-Mohar theorem. Notion of Cayley graphs of groups; lamplighter graphs. Exponential volume growth does not imply non-amenability. [PGG Sections 1.1, 1.2, 5.1]

3.) Oct. 8. Rate of escape of SRW on lamplighter groups. Stating the Kaimanovich-Vershik theorem (1983) on the equivalence of zero speed and the Liouville property for bounded harmonic functions. Martingales and discrete harmonic functions for Markov chains. Liouville property on Z^d and lamplighter groups over Z and Z^2, non-Liouville property for lamplighter over Z^3 and for T_d. [parts of PGG Sections 6.1, 6.3, 9.1, 9.2]

4.) Oct. 15. Restating the Kaimanovich-Vershik theorem, including asymptotic entropy, but Poisson boundary only vaguely. Proof of Entropy \leq Speed * VolumeGrowth, and Non-amenability implying positive speed. Using the bounded martingale convergence theorem to relate the Liouville property to Poisson triviality. Speed exponent on \Z \wr \Z is 3/4. Groups are at least diffusive, via Mok's theorem on equivariant harmonic embeddings into Hilbert space. Quasi-isometry invariance of growth and amenability. Stating Gromov's polynomial growth theorem and the Milnor-Wolf theorem on the growth of solvable groups. A way to construct strange groups: Grigorchuk's self-similar group of intermediate volume growth. [PGG Sections 9.1, 9.3, part of 9.4, part of 10.1, 10.2, part of 3.1, part of 15.1]

5.) Oct. 22. Tying up some loose ends about couplings, quasi-isometries, and ends. Reversibility of Markov chains. Electric networks and discrete potential theory: Markov operator, gradient, co-gradient, voltage, flow, current, effective resistance. [PGG Section 6.1. Can also have a look at Levin-Peres-Wilmer Chapters 1 and 9, or Lyons-Peres Chapter 2.]

6.) Oct. 29. Definition and probabilistic interpretation of effective conductance to infinity. Introducing Doob's h-transform, then realizing it was not needed. Dirichlet energy and transience: Thomson's principle, Terry Lyons' theorem, finding a flow of finite energy in Z^3. [PGG Chapter 6, or Lyons-Peres Chapter 2]

7.) Nov. 5. Computing the strength of the gradient of f(x)=G^Z(o,x)/C_x, messed up last time. Kanai's theorem on the quasi-isometry invariance of transience. [PGG Sections 6.1,6.2] p_{2n}(x,y)/\pi(y) is maximized at x=y in recurrent chains. \|P\| \leq 1. 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] General isoperimetric inequalities, and the evolving set process. [PGG Sections 5.1, 8.2, beginning of 8.3]

8.) Nov. 12. Markov chain mixing times: Total Variation distance and couplings. Spectrum of hypercube and cycle. Stating the Alon-Milman theorem. [PGG Section 7.3, or Levin-Peres-Wilmer Chapters 4, 5, 12.]

9.) Nov. 19. Proof of lemma on the speed of uniform convergence to stationarity assuming an absolute spectral gap. Definition of Kazhdan (T) groups, simple (non-)examples, construction of expanders. Random d-regular bipartite multigraph on n+n vertices converges in the Benjamini-Schramm sense to the d-regular tree, and it's not hard to believe that it's also an expander with good probability. [PGG Sections 7.3, 7.4, Exercise 14.16] Basics of percolation theory: Harris-FKG inequality, 1/3 \leq p_c(Z^2) \leq 2/3. Remarks on the p_c < 1 conjecture. [First part of PGG Sections 12.1 and 12.2]

10.) Nov. 26. The phase transition in Galton-Watson trees, with three different methods. Stating the phase transition for the giant cluster in the Erdős-Rényi graph. [PGG Sections 12.1 and 12.3]

11.) Nov. 27. Phase transition for triangle containment in the Erdős-Rényi graph. The Margulis-Russo formula. Stating vaguely the Fridgut-Bourgain theorem on sharp and coarse thresholds for global and local properties. Critical percolation on planar lattices: self-duality at p=1/2, the Russo-Seymour-Welsh inequality, and its implication that \theta(1/2)=0. [PGG Sections 12.3 and 12.4]

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