Stochastic models
Spring 2015 at BME

Lecturer: Gábor Pete

Lectures: Fridays 12:15-14:00, room H45a

Email: my first name at math dot bme dot hu

Office hours: see here.

Topics planned: Percolation models. Basics of statistical physics. Card shuffling, random walks on graphs and groups, Markov chain mixing times, recurrence/transience. Random graph models: Erdős–Rényi, Barabási–Albert scale-free networks. Variants of random walks. Queuing models. Interacting particle systems and hydrodynamic limits. Self organized criticality: sandpile models. Solving PDEs with randomized games. Some recurring methods: couplings and stochastic domination, martingales, large deviations, ergodicity, spectral theory, discrete isoperimetric inequalities.

Grading:

There will be homeworks. Here is the list, which will keep growing as the course progresses. Please hand in solutions in two installments, by April 3 and April 30 Thu 2 pm (in my Department Office pigeonhole), for 15 + 15 points. 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.

There will also be final projects, to be worked out in pairs. This will consist of reading and understanding a research article or book section, giving a 15 + 15 minutes presentation by the two of you, and solving one or two extra homework problems related to the presentation. Here is a list of topics, together with some extra problems. You can also suggest topics that you would like to learn about.

First presentation day: May 15, in class. Second presentation day: May 18, Monday, 12:15-14:00, location TBA. The extra problems are to be handed in at the time of your presentation. The maximal score for the project is 30 points. Partners are responsible for each other, so they will usually get the same score, except for extreme cases.

Grades: 2 from 30 points, 3 from 38 points, 4 from 46 points, 5 from 54 points.

Here are the points earned so far.

Diary:

1.) Feb. 13.

Pólya's theorem on the recurrence and transience of SRW on \Z^d, and exponential decay of return probabilities on the tree T_d, using a large deviation inequality. [PGG Section 1.1]

Definition of d-dimensional isoperimetry [PGG Section 5.1]. Stating the Varopoulos (1985) and Kesten-Cheeger-Dodziuk-Mohar (1959-1988) theorems on return probabilities. [PGG Thm 8.1 and Thm 7.3]

2.) Feb. 20.

Stating and proving the Azuma-Hoeffding large deviation inequality. Existence of large deviations rate function using subadditivity. [PGG Section 1.2]

Starting to compute the spectral radius (exponential rate of decay of the return probabilities) of the d-regular tree. [PGG Section 1.1]

3.) Feb. 27.

Finishing the computation of the spectral radius of the d-regular tree. Notion of universal covering tree of graphs, and the extremality of the spectral radius of the d-regular tree among all d-regular graphs. [PGG Sections 1.1 and 2.1]

The Erdős-Rényi random graphs G(n,p) and G{n,M}. Standard coupling for different values of p. Notion of stochastic domination. [PGG Section 12.3, vdHof Chapter 4]

4.) March 6.

Stating Strassen's theorem on stochastic domination. Phase transition for subgraph containment in G(n,p), via the First and Second Moment Methods. Some intuition for the phase transition for connectedness. Notion of a threshold window. [PGG Section 12.3, vdHof Chapter 4]

5.) March 13.

Appearance of a giant component in G(n,p) should be related to the phase transition for Galton-Watson trees, since G(n,\lambda/n) converges locally to the Poi(\lambda) GW tree.

For the GW phase transition, two different proofs so far: 1) generating functions, together with stating the GW duality. 2) First and second moment methods and martingale convergence.

For the special case of Geom(1/2)-1 offspring distribution, contour process is exactly a simple random walk excursion, hence the Gambler's Ruin (coming from a MG Optional Stopping Theorem) yields that P[critical Geom GW reaches level n]=1/n. For the tail of the volume of the tree, we stated for SRW that \P_1[\tau_0 > n^2] \asymp \P_1[\tau_{\sqrt{n}} < \tau_0 ] = 1/\sqrt{n} holds, which implies the same for the volume. [PGG parts of Sections 12.1 and 6.3, LyP Sections 5.1, 5.7.]

6.) March 20.

Third proof for GW phase transition (using a Markovian exploration process), and showing that it implies that the largest component in G(n,\lambda/n) has size O_\lambda(\log n) with probability tending to 1. For the critical case, we used the Chung-Fuchs theorem [see Durrett: Probability, Section 4.2]: for a 1-dim random walk on \R, if S_n/n converges to 0 in probability (a WLLN), then S_n is recurrent: it almost surely visits any open interval infinitely often.

Detour about Chung-Fuchs: Non-example 1: from SRW on \Z^3, can get a RW on \Z that is symmetric, but not recurrent. Non-example 2: RW with Cauchy increments does not satisfy WLLN (since S_n/n = X_1 in distribution, using the conformal invariance of 2-dim Brownian motion), but it is recurrent.

7.) March 27.

Largest component in G(n,\lambda/n) for \lambda>1 is of order c_\lambda n, and for \lambda=1 it is of order n^{2/3}. (Erdős-Rényi called this a double jump: from \log n to n^{2/3} to n.)

On the way, we discussed the Doob h-transform of Markov chains (as a special case, SRW on \Z, starting from any positive integer, conditioned not to hit 0, the discrete version of the Bessel(3) process), discrete harmonic functions for Markov chains, and the size-biased version of random variables, and their appearance as the gap containing a given point in a stationary point process on \R. [PGG Sections 12.3, 6.3]

8.) April 3.

Chromatic number concentration via Azuma-Hoeffding. The general Bollobás-Thomason (1987) phase transition result. Coarse and sharp phase transitions: stating vaguely the Friedgut-Bourgain (1999) theorem, and introducing discrete Fourier analysis. [PGG Sections 6.3, 12.3]

Barabási-Albert power-law random graphs, via ODE approximation. [Durrett RGD, Section 4.1]

9.) April 10.

Stating Russo's formula, and sketch of proof. [PGG Section 12.3] or [Grimmett]

Percolation on transitive graphs: the notion of p_c, Kolmogorov's 01 law, 1/3 \leq p_c(\Z^2,bond) \leq 2/3, and p_c(T_d)=1/d-1. [PGG Section 12.1]

Stating the Benjamini-Schramm conjectures on p_c < 1 and \theta(p_c)=0, with the known cases. [PGG Section 12.2] Definition of Cayley graphs of groups. [PGG Section 2.1]

Stating the Harris-Kesten theorem on p_c(\Z^2,bond)=p_c(\Delta,site)=1/2, and Smirnov's theorem on the conformal invariance of critical site percolation on \Delta, plus the universality conjecture. [PGG Section 12.4] or [Grimmett]

10.) April 17.

Tóth Bálint substitutes me, talking about forest fire models.

11.) April 24.

A few more words on percolation critical exponents. Ergodicity of percolation. The number of infinite clusters, conjectural characterization of amenability. [PGG Sections 12.1 and 12.2]

Ising model of magnetization. [PGG Section 13.1, Grimmett]

12.) May 8.

The FK random cluster model. FKG inequality and stochastic domination.

A few words on Markov chain mixing times.

13.) May 15 and May 18.

Bibliography:

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.

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. 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