Discrete-Time Markov Chains and Monte Carlo Methods

A Markov chain can be used to model the evolution of a sequence of random events where probabilities for each depend solely on the previous event. Once a state in the sequence is observed, previous values are no longer relevant for the prediction of future values. Markov chains have many applications for modeling real-world phenomena in a myriad of disciplines including physics, biology, chemistry, queueing, and information theory. More recently, they are being recognized as important tools in the world of artificial intelligence (AI) where algorithms are designed to make intelligent decisions based on context and without human input. Markov chains can be particularly useful for natural language processing and generative AI algorithms where the respective goals are to make predictions and to create new data in the form or, for example, new text or images. In this course, we will explore examples of both. While generative AI models are generally far more complex than Markov chains, the study of the latter provides an important foundation for the former. Additionally, Markov chains provide the basis for a powerful class of so-called Markov chain Monte Carlo (MCMC) algorithms that can be used to sample values from complex probability distributions used in AI and beyond. Outside of certain AI-focused examples, this course is first and foremost a mathematical introduction to Markov chains. It is assumed that the learner has already had at least one course in basic probability. This course will include a review of conditional probability and will cover basic definitions for stochastic processes and Markov chains, classification and communication of states, absorbing states, ergodicity, stationary and limiting distributions, rates of convergence, first hitting times, periodicity, first-step analyses, mean pattern times, and decision processes. This course will also include basic stochastic simulation concepts and an introduction to MCMC algorithms including the Metropolis-Hastings algorithm and the Gibbs Sampler.