Discrete-Time Markov Chains and Monte Carlo Methods

University of Colorado Boulder via Coursera

Go to class Write review

Details

Go to class

Provider

Coursera
Pricing

Paid Course
Languages

English
Certificate

Paid Certificate Available
Duration & workload

1 day 8 hours 32 minutes
Sessions

On-Demand
Subtitles

English

Found in

Part of

Foundations of Probability and Statistics

Overview

Coursera Flash Sale

40% Off Coursera Plus for 3 Months!

Grab it

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.

Syllabus

Getting Started

Welcome to the course! This module contains logistical information to get you started!

Markov Chains I: The Basics

In this module we will review definitions and basic computations of conditional probabilities. We will then define a Markov chain and its associated transition probability matrix and learn how to do many basic calculations. We will then tackle more advanced calculations involving absorbing states and techniques for putting a longer history into a Markov framework!

Markov Chains II: Limiting Distributions

What happens if you run a Markov chain out for a "very long time"? In many cases, it turns out that the chain will settle into a sort of "equilibrium" or "limiting distribution" where you will find it in various states with various fixed probabilities. In this Module, we will define communication classes, recurrence, and periodicity properties for Markov chains with the ultimate goal of being able to answer existence and uniqueness questions about limiting distributions!

Markov Chains III: Stationary Distributions and First-Step Analyses

In this Module, we will define what is meant by a "stationary" distribution for a Markov chain. You will learn how it relates to the limiting distribution discussed in the previous Module. You will also spend time learning about the very powerful "first-step analysis" technique for solving many, otherwise intractable, problems of interest surrounding Markov chains. We will discuss rates of convergence for a Markov chain to settle into its "stationary mode", and just maybe we'll give a monkey a keyboard and hope for the best!

Simulation and Markov Chain Monte Carlo Algorithms

In this Module we explore several options for simulating values from discrete and continuous distributions. Several of the algorithms we consider will involve creating a Markov chain with a stationary or limiting distribution that is equivalent to the "target" distribution of interest. This Module includes the inverse cdf method, the accept-reject algorithm, the Metropolis-Hastings algorithm, the Gibbs sampler, and a brief introduction to "perfect sampling".

Reinforcement Learning and Markov Decision Processes

In reinforcement learning, an "agent" learns to make decisions in an environment through receiving rewards or punishments for taking various actions. A Markov decision process (MDP) is reinforcement learning where, given the current state of the environment and the agent's current action, past states and actions used to get the agent to that point are irrelevant. In this Module, we learn about the famous "Bellman equation", which is used to recursively assign rewards to various states and how to use it in order to find an optimal strategy for the agent!