An Introduction to Markov Chains (Step by Step)

What if I told you that it had been mathematically proven that the orange and red properties in Monopoly by Hasbro are the most profitable (i.e., they are the most landed-on properties)?

Jenn (B.S., M.Ed.) of Calcworkshop® teaching markov chains

Jenn, Founder Calcworkshop^®, 15+ Years Experience (Licensed & Certified Teacher)

And when playing the game of RISK, the best strategy for world domination is to attack when you have twice as many armies on a neighboring territory and if the number of troops your opponent has is at most half your own.

How do we know this?

Markov Chains!

Now, we briefly looked at linear difference equations and migration matrices, which lay the foundation of Markov Chains, in our lesson dealing with Applications of Linear Systems and Linear Models in Business. Still, this lesson will dig deeper and allow us to see how Markov Chains, along with stochastic matrices, transition, and migration matrices, help us to study chance processes and give us insight into how the outcome of a given experiment can affect the result of the following experiment.

In fact, modern probability theory studies chance processes (i.e., the likelihood of occurrence) for which the knowledge of previous outcomes influences predictions for future experiments and is used for such things as:

Predicting the weather conditions given the weather on a preceding day
A student’s grades based on a sequence of exams in a course
How population moves or migrates from one place to another
Classic board games such as Chutes and Ladders, Monopoly, and Risk

Understanding Probability Vectors and Stochastic Matrices

To get a better understanding of all of this, let’s first talk about the fact that a probability vector $\vec{x}$ in $R^{n}$ is a non-negative vector where entries are probabilities that add up to 1 (i.e., 100%). And a stochastic matrix $P$ is an $n \times n$ matrix whose columns are probability vectors.

How Markov Chains Work

Therefore, a Markov Chain is a sequence of probability vectors, $\vec{x_{0}}, \vec{x_{1}}, \dots$ where $\vec{x_{0}}$ is the initial state, together with a stochastic matrix $P$ , such that $\vec{x_{1}} = P \vec{x_{0}}, \vec{x_{2}} = P \vec{x_{1}}, \vec{x_{3}} = P \vec{x_{2}}, \dots$ .

Thus, a Markov chain is a first-order difference equation representing probabilities and is described as $\vec{x_{K + 1}} = P \vec{x_{k}}$ for $k = 0, 1, 2, \dots$ , where $\vec{x_{k}}$ is called the state vector (steady state vector).

Alright, so let’s practice creating a stochastic matrix $P$ .

An Example: Predicting Ice Cream Sales

Suppose an ice cream shop offers three flavors: chocolate, strawberry, and vanilla, and is regularly frequented by local customers. In the following directed graph, vertices (nodes) represent the three states (i.e., chocolate, strawberry, and vanilla), and the arrow represents the transition and their probability.

Find Stochastic Matrix (Markov Chain Graph)

The graph above shows that seventy percent of those who ordered a chocolate cone on their last visit will do so again on their next visit. Still, ten percent who previously chose chocolate will choose strawberry next time, and twenty percent will choose vanilla.

Find Stochastic Matrix (Markov Chain Table)

Using the direct graph, we will make the following stochastic matrix where each column equals 1 and demonstrates the likelihood of a current state (ice cream choice).

$\begin{array}{r} P = [\begin{array}{lll} 0.7 & 0.3 & 0.1 \\ 0.1 & 0.4 & 0.1 \\ 0.2 & 0.3 & 0.8 \end{array}] \end{array}$

Now let us assume that the outcome of today’s ice cream sales shows that $55 %$ of customers chose chocolate, $5 %$ chose strawberry, and $40 %$ selected vanilla.

$\begin{array}{r} \vec{x_{0}} = [\begin{array}{l} 0.55 \\ 0.05 \\ 0.40 \end{array}] \end{array}$

So, using this information, let’s see if we can predict what tomorrow’s ice cream sales are likely to be knowing $\vec{x_{K + 1}} = P \vec{x_{k}}$

$\begin{array}{r} \vec{x_{2}} = [\begin{array}{lll} 0.7 & 0.3 & 0.1 \\ 0.1 & 0.4 & 0.1 \\ 0.2 & 0.3 & 0.8 \end{array}] [\begin{array}{l} 0.55 \\ 0.05 \\ 0.40 \end{array}] = [\begin{array}{c} 0.44 \\ 0.115 \\ 0.445 \end{array}] \end{array}$

This indicates that $44 %$ of customers will select chocolate, $11.5 %$ will choose strawberry, and $44.5 %$ will desire vanilla.

But wouldn’t it be really nice if the ice cream shop could accurately predict the likelihood of ice cream choices for its customers? This way, they make enough of the preferred ice cream without having it left over.

From State Vectors to Steady State Vectors

Introducing the steady state vector, sometimes called the equilibrium vector!

The most exciting aspect of Markov Chains is that it does not depend upon which state the chain was in before the current state, and it can accurately predict long-term behavior.

If $P$ is a stochastic matrix, then the state vector for $P$ is a probability vector $q$ such that $\vec{P q} = \vec{q}$ .

But rather than computing numerous iterations of our Markov chain, $\vec{x_{K + 1}} = P \vec{x_{k}}$ for $k = 0, 1, 2, \dots$ , we’re going to cut to the chase and find out when there is no longer a change in the system from one choice to the next.

This is done by utilizing the following technique:

$\begin{aligned} \vec{P \vec{x}} & = \vec{x} \\ \vec{P x} - \vec{x} & = \vec{0} \\ (P - I) \vec{x} & = \vec{0} \end{aligned}$

Thus, we can find the steady state vector for $P$ by row reducing the augmented matrix $\vec{q} = [\begin{array}{ll} (P - I) & \vec{0} \end{array}]$

Calculating the Steady State Vector: A Practical Example

Okay, so using our ice cream shop example, let’s calculate the steady state vector if

$\begin{aligned} P & = [\begin{array}{lll} 0.7 & 0.3 & 0.1 \\ 0.1 & 0.4 & 0.1 \\ 0.2 & 0.3 & 0.8 \end{array}] \end{aligned}$

First, we find $P - I$

$\begin{aligned} P - I & = [\begin{array}{ccc} 0.7 & 0.3 & 0.1 \\ 0.1 & 0.4 & 0.1 \\ 0.2 & 0.3 & 0.8 \end{array}] - [\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}] \\ = [\begin{array}{ccc} - 0.3 & 0.3 & 0.1 \\ 0.1 & - 0.6 & 0.1 \\ 0.2 & 0.3 & - 0.2 \end{array}] \end{aligned}$

Now we will augment the matrix with the zero vector and row reduce

$\begin{aligned} [\begin{array}{cccc} - 0.3 & 0.3 & 0.1 & 0 \\ 0.1 & - 0.6 & 0.1 & 0 \\ 0.2 & 0.3 & - 0.2 & 0 \end{array}] & \sim [\begin{array}{cccc} 1 & 0 & - 0.6 & 0 \\ 0 & 1 & - 0.267 & 0 \\ 0 & 0 & 0 & 0 \end{array}] \end{aligned}$

Next, we will write our findings in parametric vector form.

$\begin{array}{r} \begin{array}{c} x_{1} & = 0.6 x_{3} \\ x_{2} & = 0.267 x_{3} \\ x_{3} & = x_{3} \end{array}} \vec{x} = x_{3} [\begin{array}{c} 0.6 \\ 0.267 \\ 1 \end{array}] \end{array}$

Lastly, we will take our solution and make it stochastic. Remember, the sum of the column vector must total 1. Therefore, we will sum the column and divide each entry by that amount.

$\begin{array}{r} \underset{total = 1.867}{\underset{⏟}{[\begin{array}{c} 0.6 \\ 0.267 \\ 1 \end{array}]}} \Rightarrow [\begin{array}{c} 0.6 / 1.867 \\ 0.267 / 1.867 \\ 1 / 1.867 \end{array}] = [\begin{array}{l} 0.32 \\ 0.14 \\ 0.54 \end{array}] \end{array}$

This yields us a steady-state vector that predicts the future sales of ice cream to be approximately $32 %$ chocolate, $14 %$ strawberry, and $54 %$ vanilla. Vanilla is clearly the preferred ice cream of choice for this local shop.

Next Steps

In this lesson, you will:

Create stochastic matrices, transition matrices, and migration matrices
Use the process of Markov chains to predict the future
Find the steady state vector

Get ready for an exciting experience!

Video Tutorial w/ Full Lesson & Detailed Examples

markov-chain-applications-example

Get access to all the courses and over 450 HD videos with your subscription

Monthly and Yearly Plans Available

Get My Subscription Now

Still wondering if CalcWorkshop is right for you?
Take a Tour and find out how a membership can take the struggle out of learning math.

4.9 / 5

1,128 Reviews

Kevin S.10-30-24 - CO, United States

I had never even heard of discrete math before I had to take it for my Bachelor's in Cybersecurity. I had actually hoped that my math days were done! I suffered through class not understanding any of the presentations until I stumbled across Calcworkshop. I used the Calcworkshop lessons more than I used my instructor's lectures and my book. I ended up with a high B (just 12 points away from an A) thanks to Jenn. Without her easy to understand style of teaching, I'm not sure I would have even passed the class. Thank you so much!!!

Richard10-29-24 - Norway

Very well structured and site. It is well structured giving a good overview of the different topics regarding all mathematics where you easily can choose which path is applicable to your specific needs.The video lectures are superb with introduction to the topic followed by a detailed theoretically explaination and what I personally get most out of is; heaps of examples where you are taken and shown, step by step, the prosess of solving the problem. They also includd practice sheets and solutions to test yourself after each chapter. There is a lot to undertake on this site, but it provides an easy and understandable interface to map out what you need to do. The site has been very helpfull for me and I highly recommend it.

RobWP10-26-24 - United States

I am taking this course for mainly linear algebra review. It is a course that I have had but fairly long ago. I'm currently working in masters in data science and linear algebra namely transformations is something that has come up and I thought I need a good review on. I so far what I have liked about the course is, the common sense approach. Her approach makes it easy to remember the concepts because of her common sense approach. I like the fact that she gives information that is not really in any textbooks. I can vouch for that because not only have I used textbook recently to review I have had a formal class in the past that used textbooks. She goes over things thoroughly and for the price it's very much worth it. I have had many quarters of formal calculus and differential equations courses and I am kind of anxious to look to see what her approach to calculus is. I can't really answer how this class would be for a novice or someone who has not had linear algebra the past, but I really don't think they need to worry about that. Her method I feel will make a novice be successful and to understand the material. She is very easy to understand. Gives good examples but doesn't beat a dead horse either. What I like about her introductory remarks is that she says what linear algebra is all about and she points out what the core of the linear algebra is about and what you need to know. Having taken it before I would have to agree and she is dead on spot.

Robbin03-18-25 - CO, United States

Very well organized, helpful and comprehensive. It is great also to have access to prior course material so you can easily go back and refresh if you need to. Jenn is very clear and the number of examples leaves one comfortable with each topic. Couldn't be happier.

RCJK03-07-25 - ID, United States

I had to take Calculus I and II as accelerated classes while working full time. It was my first time taking this courses and was very overwhelming. Calcworkshop really made learning the subjects easier for me by having all the subjects easy to find and easy to understand explanations. I received a B in both classes which I am extremely happy with doing the classes in double time.

Jacqueline S.03-07-25 - SC, United States

Jenn is awesome!Her breakdown of the topic is beyond what you would expect. She is showing you how to arrive at the answer instead of doing a simple equation. Most people need to know the why it give confidence and structure to the learning process. This is what Jenn is great at, she knows how to deliver the information to a non math mind in a way that instills knowledge that you can forever draw from as you move forward. It's really well thought out. She is a true master teacher. Thanks for all that you do for us! Hugs n Blessings... JS

Rose M.03-07-25 - CA, United States

Best instructor ever, I have never had Math explained in a way that was so interesting. Her lectures and instruction is explained perfectly, and I will continue to use this for all my future math courses.

A Reviewer03-07-25 - United States

I needed help with college precalculus, they provided more than enough help that allowed me to succeed and get the scores I needed.

Jujuana03-05-25 - MO, United States

I love the videos the way each lesson is explained step by step. I love that she has examples that you can go over again and again in order to understand the way algebra works. I was lost because my instructor was flying through each lesson and I was totally lost. I attached my syllabus and they helped me stay focus on what I was working and give me a guide to go back and refresh what I went over in class.

Stacey01-31-25 - AZ, United States

Hello, I highly recommend getting a subscription to Jenn and her Calcworkshop teaching math service. I did a general, "go from bad to good at math", Google search and found out about Calcworkshop through responses to the topic on reddit. I've just started watching her videos and found them to be extremely helpful. I'm going back to college after a long absence and math was never my strong suit. So I'm starting at the very bottom of her available subjects and going from there. Just watching a couple of the videos has taken me from being dragged along not understanding to following along just fine in my math class. I'm moving from the "I'll never get this", to the "I look forward to understanding this", mindset in approaching math. This for me is huge, and even though I have a long way to go, I'm confident I will get there thanks to Jenn. Totally worth it!

Kathy W.01-14-25 - WA, United States

Calcworkshop is an outstanding source to learn math and understanding math concepts. Jenn is an outstanding master teacher. Every lesson is clearly presented making understanding easy to grasp. Practice lessons with accompanying answers are given for each section. I am 82, a retired teacher and lifelong learner. Learning calculus has always been on my bucket list. Calcworkshop is helping me reach my goal.

Cheryl01-14-25 - NY, United States

Calc workshop is the absolutely best resource for math and I have seen almost everything that exists out there. I have even recommended it to my daughter's school so that all the kids could use the videos during the summer months for the subject they plan to study in the fall. They are guaranteed to get a A if they have watched the videos and completed the problems before taking the class. Students who are weak in areas can access lower level classes and those who seek to advance above grade level can do so. The videos and exercises are crystal clear and the excellent presentations raise the bar for teachers everywhere. I have always believed that one great math teacher is important in the education process. The videos, exercises and problems are excellent. It is not possible to have ANY knowledge gaps. I have never seen anything on the market that even begins to compete with it!

Justin N.12-22-24 - OK, United States

Calculus can be a scary subject. I know I was scared. I had been out of any math class for over 23 years. I had taken an 8 week Calculus 1 class and felt like I was overloaded. Going into Calculus 2 I found CALCWORKSHOP.com. I used the training videos and material to really dive back into Calc 1 and prepare for Calc 2. Long story short with the material provided and ample study time, I finished Calc 2 with a 95%. Thanks Jenn!

Shelby12-10-24 - OH, United States

CalcWorkshop was a wonderful resource as someone going onto a college calculus 1 class after not having taken a math course in a year! Jenn always explained things in a logical order that built upon previous lessons, and the way she explained topics was always easy to understand. Calcworkshop saved this semester for me, and I couldn't be more grateful to have found this site. :)

Jordan Q.12-09-24 - AR, United States

Anyone struggling with math at any level would greatly benefit from this product. I signed up for it immediately after getting a D on my first exam in calculus 2 and ended up getting A's and B's on the remaining exams, getting a B overall in the class. Jenn breaks down the topics, without skipping any steps, in a way that makes them very easy to understand. I highly recommend this product!

N8Booker11-28-24 - MA, United States

I'm in school to get my degree Networking and Cybersecurity and I'm in my first year. I've been away from school for quite a long time so the concepts that are being taught although not foreign to me, have so much dust on them from a lack of being used in real world applications regularly.I stumbled upon CalcWorkshop by pure chance and it has been a game changer for me. Jen filled in the gaps in between what my Professor is teaching at a rapid fire pace and where my brain grasps and applies it. If not for Jen's approach, I'd have failed my test I took miserably!Am I grateful? It goes beyond words and not I recommend her workshops to everyone!

Kevin S.10-30-24 - CO, United States

Richard10-29-24 - Norway

RobWP10-26-24 - United States

RCJK03-07-25 - ID, United States

Jacqueline S.03-07-25 - SC, United States

See more reviews on Shopper Approved