Lectures: Fridays 12:15-13:45, room H45a.
The final grade will be composed of 30% first HW set, 30% second HW set, 40% final project with presentation.
Here is the first problem set. Due April 12. You can ask me for help if you get stuck with something.
And here is the second problem set, due May 24, 3 pm.
Presentations: here is the list of topics. Due May 17.
1.) Feb 8. Pólya's theorem: recurrence/transience of SRW on Z^d. The d=1 case, plus sketching the CTRW approach. [PGG Section 1.1]
2.) Feb 15. Pólya's theorem continued: the CTRW approach in more detail. Speed of escape for SRW on the regular tree T_k. [PGG Section 1.1]
3.) Feb 22. One more word on the CTRW approach [PGG equation (1.3)]. Proving discrete return probability via Large Deviations bound on the Binomial distribution. Calculating the spectral radius of T_k. [PGG Section 1.1]
4.) March 1. Fekete's subadditive lemma, with three applications on transitive graphs: return probabilities, speed of SRW, connective constant. Detour on transitive graphs: Cayley graphs of groups, such as the free group. Stating the Kesten-Cheeger-Dodziuk-Mohar theorem on the equivalence of spectral radius < 1 and non-amenability of graphs. [PGG Sections 1.1, 2.1, 5.1]
5.) March 8.
Proving that amenable implies that a pyramid or Ponzi scheme cannot exist, and stating that the converse also holds. This provides some intuition for Folner's theorem: a finitely generated group is von Neumann-amenable (i.e., an invariant mean exists) iff any of its Cayley graphs is Folner-amenable. 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. For graphs, subexponential volume growth implies amenable. However, there are amenable transitive graphs of exponential growth: e.g., the lamplighter group. [PGG Sections 5.1 and 5.2]
6.) March 29. Reversible Markov chains, electric network random walks, and the self-adjointness of the Markov operator. [PGG Section 6.1] Rough sketch why the Kesten-Cheeger-Dodziuk-Mohar theorem is true. [A summary of PGG Sections 7.1 and 7.2]
7.) April 5. Introdution to why mixing times are interesting: Markov Chain Monte Carlo in statistical physics, card shuffling procedures as random walks on the symmetric group [LPW Sections 2.6 and 3.1]. L^p distances between probability measures. Total variation distance, coupling interpretation. Definition of the total variation mixing time, proof of d(\ell\tau_{mix})<2^{-\ell}. [LPW Chapter 4] Intutitive examples: complete graph, dumbbell graph, cycle.
8.) April 12. Sketch of TV mixing time 1/2 n \log n for the lazy RW on the hypercube {0,1}^n. Spectrum of finite reservable Markov chains. Spectral gap and Cheeger constant: the Alon-Milman or Jerrum-Sinclair bound. [PGG Section 7.3, LPW Sections 12.1-3, 13.2]
9.) April 26. Spectral gap and mixing times: lower and upper bounds. The spectrum of the cycle, the hypercube. [PGG Section 7.3, LPW Sections 12.1-3.]
10.) May 3. Definition of expander graphs. [PGG Section 7.3] Benjamini-Schramm convergence of finite graphs. [PGG Section 14.1] Introduction to percolation theory: definitions of p_c, the example of \Z and d-regular trees T_d, d\geq 3. [PGG Section 12.1]
11.) May 10. Percolation theory: 1/3 \leq p_c(\Z^2,bond)\leq 2/3 with Peierls method. I didn't have time to talk about invariant percolations and ergodicity, but you can find it in [PGG Section 12.1]. Rough overview of critical planar percolation. [PGG Section 12.4] I also didn't talk about the Ising model on finite and infinite graphs, but if you read the first 1 or 2 or 3 or 4 pages of PGG Section 13.1, you will get the idea.
N. Alon, J. Spencer. The Probabilistic Method. 3rd edition. Wiley Interscience, 2008. Here is a copy.
Rick Durrett. Probability: theory and examples. 4th edition. Cambridge University Press, 2010. https://www.math.duke.edu/~rtd/PTE/PTE4_1.pdf.
Rick Durrett. Random graph dynamics. Cambridge University Press, 2007. https://www.math.duke.edu/~rtd/RGD/RGD.pdf.
Christophe Garban, Jeff Steif. Noise sensitivity of Boolean functions and percolation. Cambridge University Press, 2014. http://math.univ-lyon1.fr/~garban/Fichiers/book.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