Skip to main content

MA3H2 Markov Processes and Percolation Theory

Lecturer: Roman Kotecký
Term(s):
Term 2

Status for Mathematics students: List A

Commitment: 30 lectures

Assessment: 3 hour exam 85%, assignments 15%

Prerequisites: As a prerequisite module students should have done MA359 Measure Theory or one of the following modules, MA253 Probability and Discrete Mathematics or ST213 Mathematics of random events. Alternatively, the students need to know the following basic key facts: probability measure , expectation and variance, law of large numbers, and Probability A module [as Probability A is a core module there are no further compulsory prerequisites].

Leads To: MA482 Stochastic Analysis,MA4F7 Brownian Motion, and MA4H3 Interacting Particle Systems, ST406 Applied Stochastic Processes with Advanced Topics, CO905 Stochastic models of complex systems and MA4L3 Large Deviation theory.

Content: This module provides an introduction to continuous-time Markov processes and percolation theory, which have numerous applications: random growth models (sand-pile models), Markov decision processes, communication networks.

The module first introduces the theory of Markov processes with continuous time parameter running on graphs. An example of a graph is the two-dimensional integer lattice and an example of a Markov process is a random walk on this lattice. Very interesting problems of such processes involve spatial disorder and dependencies (e.g. burning forests). Therefore, after the main part, an elementary introduction to percolation theory will be given which can be used to study such questions.

Percolation is a simple probabilistic model for spatial disorder, and in physics, chemistry and materials science, percolation concerns the movement and filtering of fluids through porous materials. Recent applications include for example percolation of water through ice which is important for the melting of the ice caps.

Let us briefly explain the mathematical setting. Percolation is a simple probabilistic model which exhibits a phase transition. The simplest version of percolation takes place on  \mathbb{Z} ^2 , which we view as a graph with edges between neighbouring vertices. All edges of  \mathbb{Z}^2 are, independently of each other, chosen to be open with probability  p and closed with probability  1-p . A basic question in this model is `What is the probability that there exists an open path from the origin to the exterior of the square  S_n=[-n,n]^2 ?' A limit as  n\to\infty of the question raised above is `What is the probability that there exists an open path from  0 to infinity?' This probability is called the percolation probability and is denoted by  \theta(p) . Clearly  \theta(0)=0 and  \theta(1)=1 , since there are no open edges at all when  p=0 and all edges are open when  p=1 . For some models there is a  0<p_{c}<1 such that the global behaviour of the system is quite different for  p<p_{c} and for  p>p_{c} . Such a sharp transition in global behaviour of a system at some parameter value is called a phase transition or a critical phenomenon, and the parameter value at which the transition takes place is called a critical value.

The basic mathematical methods and techniques of random processes and an overview of the most important applications will enable the student to use analytical techniques and models to study questions in modern applications in biological and physical systems, communication networks, financial market, decision processes.


Books:

We will not follow a particular book.

H.O. Georgii: Stochastics: introduction to probability theory and statistics, de Gruyter (2008). [basic introduction to stochastics and Markov chains (discrete time)]

J. Norris: Markov chains, Cambridge University Press [standard reference treating the topic with mathematical rigor and clarity, and emphasizing numerous applications to a wide range of subjects]

G. Grimmett, D. Stirzaker: Probability and Random Processes, OUP Oxford (2001) [chapter 6 on Markov chains]

G. Grimmett: Probability on Graphs, Cambridge University Press (2010). [Available Online, contains a nice introduction to processes on graphs and percolation]

B. Bollabás, O. Riordan: Percolation, Cambridge University Press (2006). [a modern treatment of percolation. The introduction and the chapter on basic techniques are relevant for the lecture]

G. Grimmett: Percolation, 2nd ed., Springer (1999). [the standard reference on percolation. It contains much more than covered in the lecture. The first two chapters are relevant for the lecture]


Additional Resources

yr1.jpg
Year 1 regs and modules
G100 G103 GL11 G1NC

yr2.jpg
Year 2 regs and modules
G100 G103 GL11 G1NC

yr3.jpg
Year 3 regs and modules
G100 G103

yr4.jpg
Year 4 regs and modules
G103

Archived Material
Past Exams
Core module averages