Stochastic Models

1. Pólya’s theorem on recurrence versus transience of Z^d. Green's function. The spectral radius of the d-regular tree.
2. Three notions of amenability: von Neumann, Følner, Kesten. Paradoxical decompositions, Ponzi pyramid scheme. The easy direction of the Kesten-Cheeger theorem: a Følner sequence implies that the Markov operator has norm 1. An example of an amenable Cayley graph with exponential volume growth.
3. Fekete's subadditive lemma, with three applications: return probabilities; the connective constant and the speed of random walks on infinite transitive graphs.
4. Total variation mixing time of finite Markov chains. Coupling definition of the TV distance, and using it for upper bounds on the mixing time.
5. The spectrum of finite reversible Markov chains, with some examples. Upper and lower bounds on the mixing time using the relaxation time.
6. Percolation theory: definitions of critical density, basic examples, Peierls contour method, Harris-FKG inequality.
7. The Ising model on finite graphs: definition, spatial Markov property, basic properties of the partition function, definition of long range order.