Lectures: Thursdays 16:15-17:45, room H46. And here is a link to our MS Teams channel.
The final grade will be composed of 20% for each of three HW sets, and 40% for a final project with presentation.
The grading scheme: 2 from 40%, 3 from 55%, 4 from 70%, 5 from 85%.
It is OK to think about the HW problems together, you can also ask me for help, but the solutions should be written up individually. Mindless copying will be frowned upon.
Here is the first problem set, due April 27 in class.
Here is the second problem set, due May 18 in class.
And here is the third problem set, due June 8.
Presentations: here is the list of topics.
1.) March 2. Stating Pólya's theorem: recurrence/transience of SRW on Z^d. For recurrence, it is enough to prove that the expected number of returns is infinite. Finding the 1-dimensional return probability using Stirling, and sketching the degree 1/2 rate of escape, recalling the CLT and WLLN. [PGG Section 1.1]
2.) March 9. (Recording of class is available on MS Teams.) The Azuma-Hoeffding Large Deviations bound. Finishing computing the Z^d return probability. Linear speed of escape on the regular tree T_d. Calculating the spectral radius of T_d (including the notion of coupling, Springheim's theorem, Fekete's subadditive lemma.) [PGG Section 1.1, and Section 1.2 Proposition 1.8]
3.) March 16. Two lower bounds for the return probability on the tree constructed by gluing an infinite half-line to a regular tree: 1. easier: \exp(-c\sqrt{n}). 2. using the reflection principle and Catalan numbers: cn^{-3/2}. [For the latter, see Durrett PTE Theorem 4.9.1 and Lyons-Peres Proposition 7.35.] Vertex-transitive graphs. Cayley graphs of groups (e.g., Z^d, free group, SL_2(Z)). Remark (which we have not proved): the Petersen graph is a transitive graph that is not a Cayley graph of any group. [PGG Section 2.1 and Lyons-Peres Section 3.4.]
4.) March 23. Volume growth and isoperimetric inequalities. Fast volume growth does not imply transience. Amenability of groups (von Neumann's invariant means) and their Cayley graphs (existence of Folner sets). The notion of Banach-limits. The free group is non-amenable, since it has a paradoxical decomposition. Stating the Banach-Tarski paradox. The lamplighter graph (with \Z_2 lamps over a \Z street) has exponential growth but is amenable. Sketching the return probability lower bound p_n(o,o) > c \exp(-c\sqrt{n}). [PGG Sections 5.1 and 5.2.]
5.) March 30. Reversibility of Markov chains. Reversible Markov chains are exactly the simple random walks on symmetrically edge-weighted graphs. Reversibility of \pi is equivalent to the self-adjointness of the Markov operator wrt to the \pi-weighted inner product. Every eigenvalue of any Markov operator has absolute value at most 1. The set of eigenvalues does not depend on whether we look at left of right eigenvectors. Every eigenvalue of a self-adjoint operator is real. On a finite Markov chain 1 is an eigenvalue (a right eigenvector: a constant vector; left eigenvector: a stationary measure), and the speed of convergence to the stationary distribution should be possible to determine by a spectral decomposition (to be elaborated in a later class). [LPW Chapter 1 and Section 12.1. PGG Section 6.1 first two pages, Section 7.3 first page]
6.) April 13. For infinite groups and reversible Markov chains, stating and sketching the equivalence of amenability in the senses of Folner and Kesten. [PGG Section 7.2, Lyons-Peres Section 6.2] Note: for this and the neighbouring lectures on non-amenability and expanders, you can also check out these two lectures of mine in India: Lecture 1 and Lecture 2.
7.) April 20. The spectrum of some finite Markov chains: the cycle C_n and the hypercube {0,1}^k. Sketching why the mixing time on C_n should be of order n^2 (basically, the Central Limit Theorem), and on {0,1}^k of order k\log k (basically, the coupon collector's problem). An upper bound on the uniform mixing time using the spectral gap, and noticing that it gives reasonable but suboptimal results for C_n and {0,1}^k. Defining expander graphs, in the spectral and isoperimetric senses. Stating the Cheeger inequalities of Alon-Milman (1985/86), Lawler-Sokal (1988), Jerrum-Sinclair (1989), implying that the two definitions of expanders are equivalent. [LPW Sections 12.1-4, 13.2, PGG Section 7.3]
8.) April 27. Constructing random d-regular graphs via the configuration model, sketching a proof that they are not far from a uniform simple d-regular graph (see HW2 Exercises 20 and 21), and trying to prove that they are expanders (see HW2 Exercise 22). [LPW Section 13.6] The basics of Total Variation distance between probability measures. A precise notion of mixing time for Markov Chains. Introducing the coupling method for proving upper bounds on the mixing time. [LPW Sections 4.1-4.5, PGG Section 7.3]
9.) May 4. Upper bounds on the mixing time for SRW on the cycle and the hypercube, via the coupling method. [LPW Section 5.3.] From finite to infinite: Benjamini-Schramm (local weak) convergence. Example: the canopy tree. [PGG Section 14.1; Spectral Collective's two videos: https://youtu.be/7Gj9BH4IZ-4, https://youtu.be/7vkgMQCWsHM]
10.) May 11. Benjamini-Schramm convergence implies convergence of the spectral measure. The giant component phase transition for the Erdős-Rényi random graph G(n,p), via branching processes. Starting the Smoluchowski coagulation approach. [Balázs Ráth's lecture notes]
11.) May 18. Finishing the Smoluchowski coagulation approach to the Erdos-Renyi phase transition. Percolation theory: definition of p_c on an infinite graph, Kolmogorov's 0/1 law, finding p_c of \Z, of a binary tree, and giving the bounds 1/3 \leq p_c(\Z^2) \leq 2/3. [PGG Section 12.1]
12.) May 25. (plan) The Ising model of magnetization. [PGG Section 13.1]
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