Cécile Mailler, University of Bath

"Markov chains and Martingales - Application to discrete random structures"

Markov chains and martingales are powerful tools to study random structures such as trees or urns. Being able to recognise and study such probabilistic objects is a great help to the understanding of many stochastic models.

The aim of this lecture is to recall definitions of Markov chains and martingales in discrete and continuous time and results concerning them: we will especially focus on convergence theorems.

Throughout the lecture, we will show how to use those results to study random discrete structures, mainly trees and urns. We will see for example that a simple random walk is a Markov chain, that the profile of a random binary search tree can be encoded by a martingale or that a Pólya urns process hides converging martingales.