Discrete-Time Markov Chains and Monte Carlo Methods
Keep adding new skills with 10,000+ programs for $239 (usually $399). Save now.
Discrete-Time Markov Chains and Monte Carlo Methods
This course is part of Foundations of Probability and Statistics Specialization
Instructor: Jem Corcoran
2,508 already enrolled
Included with
Ask Coursera
15 reviews
Recommended experience
15 reviews
Recommended experience
What you'll learn
Analyze long-term behavior of Markov processes for the purposes of both prediction and understanding equilibrium in dynamic stochastic systems
Apply Markov decision processes to solve problems involving uncertainty and sequential decision-making
Simulate data from complex probability distributions using Markov chain Monte Carlo algorithms
Skills you'll gain
Tools you'll learn
Details to know
See how employees at top companies are mastering in-demand skills
Build your subject-matter expertise
- Learn new concepts from industry experts
- Gain a foundational understanding of a subject or tool
- Develop job-relevant skills with hands-on projects
- Earn a shareable career certificate
There are 6 modules in this course
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.
Welcome to the course! This module contains logistical information to get you started!
What's included
8 readings4 ungraded labs
8 readings•Total 49 minutes
- Course Updates and Accessibility Support•1 minute
- Earn Academic Credit for Your Work!•10 minutes
- Course Support•8 minutes
- Assessment Expectations•5 minutes
- AI Citation and Acknowledgement•10 minutes
- Course Resources and Reading•4 minutes
- Coding in Python or R?•8 minutes
- What is a "Calculator" Notebook?•3 minutes
4 ungraded labs•Total 62 minutes
- Introduction to Jupyter Notebooks and R•30 minutes
- Introduction to Jupyter Notebooks and Python•30 minutes
- Empty R Calculator Notebook•1 minute
- Empty Python Calculator Notebook•1 minute
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!
What's included
12 videos6 assignments2 programming assignments
12 videos•Total 138 minutes
- Introduction to Stochastic Processes•7 minutes
- Conditional Probability for Events and Random Variables•14 minutes
- "Unraveling" Conditional Probability•12 minutes
- Definition of a Markov Chain•13 minutes
- Missing Time Steps in a Markov Chain•13 minutes
- Conditional Independence•9 minutes
- Time Homogeneity and the Transition Probability Matrix•9 minutes
- Basic Markov Chain Calculations•11 minutes
- The Chapman-Kolmogorov Equations•15 minutes
- Absorbing States, Part 1•12 minutes
- Absorbing States, Part 2•15 minutes
- A Longer History in a Markov Framework•8 minutes
6 assignments•Total 74 minutes
- AI Policy Quiz•5 minutes
- Basic Markov Chain Calculations I•25 minutes
- Basic Markov Chain Calculations II•30 minutes
- Quick Check-In•3 minutes
- Quick Check-In•5 minutes
- Quick Check-In•6 minutes
2 programming assignments•Total 180 minutes
- Introduction to Markov Chains (R)•90 minutes
- Introduction to Markov Chains (Python)•90 minutes
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!
What's included
9 videos3 assignments2 programming assignments
9 videos•Total 122 minutes
- Introduction to Limiting Distributions•5 minutes
- Communication Classes for a Markov Chain•14 minutes
- Classification of States: Recurrence and Transience•16 minutes
- Expected Number of Returns to a Transient State•21 minutes
- Alternative Characterization of Recurrence and Transience•12 minutes
- Recurrence and Transience are Class Properties•9 minutes
- The Random Walk•17 minutes
- Existence and Uniqueness of the Limiting Distribution•16 minutes
- Total Variation Norm Distance Between Distributions•13 minutes
3 assignments•Total 68 minutes
- Classification of States•30 minutes
- Limiting Distibutions and the Random Walk•30 minutes
- Quick Check-In•8 minutes
2 programming assignments•Total 180 minutes
- Limiting Distributions and Classification of States (R)•90 minutes
- Limiting Distributions and Classification of States (Python)•90 minutes
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!
What's included
11 videos3 assignments2 programming assignments
11 videos•Total 150 minutes
- Introduction to Stationary Distributions•14 minutes
- Finding a Stationary Distribution•12 minutes
- "Long-Run Proportion of Time" Questions•9 minutes
- Existence and Uniqueness of the Stationary Distribution•24 minutes
- Expected Hitting Time•16 minutes
- Expected Return Time•12 minutes
- Probability of Hitting One State Before Another•8 minutes
- Expected Number of Visits to a an Intermediate State•10 minutes
- Mean Pattern Times, Part 1•16 minutes
- Mean Pattern Times, Part 2•19 minutes
- Rate of Convergence to Stationarity: The Eigenvalue Connection•11 minutes
3 assignments•Total 68 minutes
- Stationary Distributions and Expected Hitting Times•30 minutes
- First Step Analyses and Mean Pattern Times•30 minutes
- Quick Check-In•8 minutes
2 programming assignments•Total 180 minutes
- Stationary Distributions and First Step Analysis (R)•90 minutes
- Stationary Distributions and First Step Analyses (Python)•90 minutes
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".
What's included
13 videos2 assignments2 programming assignments4 ungraded labs
13 videos•Total 176 minutes
- The Goal of Discrete and Continuous Random Variable Simulation•12 minutes
- "Interval Chopping" for Discrete Random Variable Simulation•10 minutes
- The Inverse CDF Method•13 minutes
- The Accept-Reject Method, Part 1•17 minutes
- The Accept-Reject Method, Part 2•11 minutes
- Discrete-Time Markov Chains on a Continuous State Space•10 minutes
- Reversibility or Detailed Balance•5 minutes
- Introduction to the Metropolis-Hastings Algorithm•17 minutes
- An Example of the Metropolis-Hasting Algorithm•12 minutes
- A Higher-Dimensional Metropolis-Hasting Algorithm Example•17 minutes
- Introduction to the Gibbs Sampler•17 minutes
- An Example of the Gibbs Sampler•17 minutes
- Introduction to Perfect Simulation•20 minutes
2 assignments•Total 60 minutes
- Basic Simulation Algorithms•30 minutes
- Markov Chain Monte Carlo Algorithms•30 minutes
2 programming assignments•Total 150 minutes
- Monte Carlo Simulation (R)•75 minutes
- Monte Carlo Simulation (Python)•75 minutes
4 ungraded labs•Total 90 minutes
- Checking a Random Number Generator with a Histogram (R)•15 minutes
- Checking a Random Number Generator with a Histogram (Python)•15 minutes
- Gelman and Rubin's R Statistic (in R)•30 minutes
- Gelman and Rubin's R Statistic (in Python)•30 minutes
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!
What's included
5 videos2 assignments2 programming assignments4 ungraded labs
5 videos•Total 85 minutes
- Markov Decision Processes: The Problem and Notation•15 minutes
- Rewards and Value Functions•22 minutes
- The Bellman Equation•16 minutes
- Value Function Computations•12 minutes
- Finding the Optimal Policy•19 minutes
2 assignments•Total 40 minutes
- Markov Decision Processes, Part 1•20 minutes
- Markov Decision Processes, Part 2•20 minutes
2 programming assignments•Total 60 minutes
- Policy Iteration in R•30 minutes
- Policy Iteration in Python•30 minutes
4 ungraded labs•Total 20 minutes
- Example State Value Function Computation in R•5 minutes
- Example State Value Function Computation in Python•5 minutes
- Example Optimal Policy Calculation in R•5 minutes
- Example Optimal Policy Calculation in Python•5 minutes
Earn a career certificate
Add this credential to your LinkedIn profile, resume, or CV. Share it on social media and in your performance review.
Build toward a degree
This course is part of the following degree program(s) offered by University of Colorado Boulder. If you are admitted and enroll, your completed coursework may count toward your degree learning and your progress can transfer with you.¹
Instructor
Offered by
Explore more from Probability and Statistics
- Status: Free TrialD
Dartmouth College
Course
- 2
28DIGITAL
Course
- Status: PreviewJ
Johns Hopkins University
Course
- Status: Free TrialT
The Hong Kong University of Science and Technology
Course
Why people choose Coursera for their career
Learner reviews
- 5 stars
66.66%
- 4 stars
26.66%
- 3 stars
0%
- 2 stars
0%
- 1 star
6.66%
Showing 3 of 15
Reviewed on Apr 8, 2026
Strong mathematical foundation for AI.
More visualizations would make it even more effective.
Frequently asked questions
To access the course materials, assignments and to earn a Certificate, you will need to purchase the Certificate experience when you enroll in a course. You can try a Free Trial instead, or apply for Financial Aid. The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile.
Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.
More questions
Financial aid available,