Markov Chains and Algorithmic Applications

This course aims to familiarise students with the theory of Markov Chains and provide an overview of how this theory can be applied to problems in financial mathematics, data science, and network science using different randomised algorithms. The course aims to introduce the theory of Markov chains, focusing on their applications for scientific computing. We will emphasise the mixing properties of finite-state, discrete-time, reversible Markov chains, which determine how quickly a chain reaches its stationary distribution from any starting state. While this may initially seem simple, it is crucial for analysing Markov Chain Monte Carlo and Hidden Markov models. It also connects to classical questions in statistical physics, numerical integration, randomised algorithms, and combinatorial optimisation. Furthermore, it has applications in distributed computing, large-scale graph mining, text analytics and high-dimensional optimisation.