Skip to main content

MA3H2 Content

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.


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]