Stochastic models
Spring 2021 at BME

Lecturer: Gábor Pete

Lectures: Fridays 10:15-11:45, online on MS Teams

Grading:

The final grade will be composed of 20% for each of three HW sets, and 40% for a final project with presentation.

Here is the first problem set, due March 11 midnight.
And here is the second problem set, due April 21 midnight.
And here is the third problem set, due May 17 Monday noon.
It is OK to think about the problems together, you can also ask me for help, but the solutions should be written up individually. Mindless copying will be frowned upon.

Presentations: here is the list of topics. Due May 14.

Diary:

The OneNote write-ups of the lectures can be found on MS Teams.

1.) Feb 12. Pólya's theorem: recurrence/transience of SRW on Z^d. [PGG Section 1.1] Definition of isoperimetric dimension of graphs. [PGG Section 5.1]

2.) Feb 19. Sketching the speed of escape for SRW on Z^d and on the regular tree T_d. Calculating the spectral radius of T_d. [PGG Section 1.1]

3.) Feb 26. Fekete's subadditive lemma, with two applications on transitive graphs: return probabilities and speed of SRW. Small detour on bounded discrete harmonic functions. Larger detour on transitive graphs: Cayley graphs of groups, such as the free group and the lamplighter groups. [PGG Sections 1.1, 2.1, 5.1, or Lyons-Peres Section 3.4.]

4.) March 5. Volume growth versus isoperimetry, with the lamplighter graphs as examples. Definition of amenability. Stating the Kesten-Cheeger-Dodziuk-Mohar theorem on the equivalence of spectral radius < 1 and non-amenability of graphs, and more generally, for reversible Markov chains, which we have defined, together with the Markov operator and some basic properties: self-adjointness, operator norm. [PGG Sections 5.1, 6.1.]

5.) March 12. More on reversibility for finite state Markov chains. Connection between operator norm of a Markov operator and the random walk spectral radius. The easy direction of the Kesten-Cheeger theorem: amenability implies ||P||=1. Proving that amenable implies that a Ponzi pyramid scheme cannot exist, and stating that the converse also holds. [PGG Sections 7.1, 7.2.]

6.) March 19. von Neumann amenability (i.e., an invariant mean exists). Showing that the free group F_2 has a paradoxical decomposition, which implies that it cannot have an invariant mean. Stating the Banach-Tarski paradox. [PGG Sections 5.1 and 5.2] The basic question of Markov chain mixing times. Mentioning two applications: sampling domino tilings and the volume of convex bodies. The intuition for mixing in two basic examples: cycle and hypercube. [PGG Section 7.3. LPW book Chapters 1-4.]

7.) March 26. The total variation distance between probability measures. The intuition for mixing in TV distance in further basic examples. Spectral gap and its implication for uniform mixing as an upper bound. Computing the spectrum of the cycle. [PGG Section 7.3. LPW Chapters 4, 12.]

8.) April 9. Computing the spectrum of the hypercube. Relaxation time. Cheeger's inequality for finite chains: isoperimetry and spectral gap. Definition of expander graphs. [PGG Section 7.3, LPW Chapter 12]

9.) April 16. The coupling method for upper bounding the mixing time. [PGG Section 7.3, LPW Chapter 5] Random regular graphs, a few similar models. Multiple edges. Isoperimetry. [?]

10.) April 23. Benjamini-Schramm convergence of finite graphs: definition, basic examples. Convergence of eigenvalue distribution. [PGG Section 14.1]

11.) April 30 (plan). Erdős-Rényi phase transition, Galton-Watson phase transition, detour on martingales. Percolation on \Z^2.

12.) May 7 (plan). Ising model of magnetization. Random cluster models.

Bibliography:

Rick Durrett. Probability: theory and examples. 5th edition. Cambridge University Press, 2019. https://services.math.duke.edu/~rtd/PTE/PTE5_011119.pdf.

Rick Durrett. Random graph dynamics. Cambridge University Press, 2007. https://www.math.duke.edu/~rtd/RGD/RGD.pdf.

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, Vol. I. Cambridge University Press, 2017. 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 and Yuval Peres. Probability on trees and networks. Cambridge University Press, 2016. http://mypage.iu.edu/%7Erdlyons/prbtree/prbtree.html

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