Markov Chains Clearly Explained! Part - 1
Summary
TLDRIn this 'Normalized Nerd' video, the presenter introduces Markov chains, a concept used across various fields like statistics, biology, economics, physics, and machine learning. The video explains Markov chains through a restaurant example that serves three types of food with a predictable pattern based on the previous day's meal. The Markov property, which states that the future state depends only on the current state, is highlighted. The presenter also discusses the stationary distribution, or equilibrium state, which represents the long-term probability distribution of states. The video demonstrates how to find this distribution through simulation and linear algebra, using an adjacency matrix and eigenvector equations to solve for the stationary state.
Takeaways
- 😀 Markov chains are used in various fields such as statistics, biology, economics, physics, and machine learning.
- 🍔 The video uses a restaurant example with three food types (hamburger, pizza, hot dog) to explain Markov chains, where the probability of serving a food type depends on what was served the previous day.
- 🔢 A Markov chain is represented by a diagram with weighted arrows indicating the probability of transitioning from one state to another.
- 📈 The Markov property states that the future state depends only on the current state, not on the sequence of previous states.
- 🎯 The sum of the probabilities (weights) of outgoing transitions from any state must equal 1, as they represent a complete probability distribution.
- 🚶♂️ A random walk along the chain can be used to explore the probabilities of each state over time.
- 📊 After many steps, the probabilities converge to a stationary distribution, also known as the equilibrium state, which does not change over time.
- 📚 Linear algebra can be used to find the stationary state more efficiently than simulation, by representing the Markov chain as an adjacency matrix and solving for the eigenvector corresponding to the eigenvalue of 1.
- 🔍 The stationary state can reveal long-term probabilities, such as the restaurant serving hamburgers about 35% of the time, pizza 21%, and hot dogs 44% of the time.
- 🔬 The eigenvector method also allows for the detection of multiple stationary states by checking for multiple eigenvectors with an eigenvalue of 1.
- 📈 The results from the linear algebra method can be compared with simulation results to validate the findings and understanding of the Markov chain.
Q & A
What is a Markov chain?
-A Markov chain is a mathematical concept used in various fields such as statistics, biology, economics, physics, and machine learning. It represents a sequence of possible events where the probability of each event depends only on the state attained in the previous event.
Why are Markov chains interesting?
-Markov chains are interesting because they simplify the process of predicting future states by only considering the current state, without needing to know the sequence of events that led up to it. This makes them useful for modeling real-world problems with complex dependencies.
What is the restaurant example in the script illustrating?
-The restaurant example illustrates how a Markov chain works. The restaurant serves only one of three foods each day, and the probability of serving a particular food depends on what was served the previous day. This creates a predictable pattern that can be represented as a Markov chain.
What does the term 'state' refer to in the context of Markov chains?
-In the context of Markov chains, 'state' refers to a situation or condition that can result in a particular outcome. In the restaurant example, the state is the type of food being served on a given day.
What is the Markov property?
-The Markov property is the fundamental characteristic of a Markov chain, stating that the probability of transitioning to a future state depends only on the current state and not on the sequence of events that preceded it.
Why is the sum of the weights of outgoing arrows from any state equal to 1 in a Markov chain?
-The sum of the weights of the outgoing arrows from any state equals 1 because these weights represent probabilities. For probabilities to be valid, they must add up to one, ensuring that all possible outcomes are accounted for.
What is a stationary distribution in the context of Markov chains?
-A stationary distribution, also known as the equilibrium state, is a probability distribution of the states in a Markov chain that does not change over time. It represents the long-term probabilities of being in each state after a large number of transitions.
How can you find the stationary state of a Markov chain?
-One way to find the stationary state of a Markov chain is through simulation, running a large number of steps and observing the convergence of probabilities. Alternatively, linear algebra can be used by setting up and solving the eigenvector equation for the transition matrix with the eigenvalue equal to 1.
What is an adjacency matrix and how is it used in representing a Markov chain?
-An adjacency matrix is a way to represent a directed graph, such as a Markov chain, where the elements of the matrix denote the weight of the edge connecting two vertices. In the context of Markov chains, it is called the transition matrix and is used to calculate the probabilities of transitioning from one state to another.
How does the script demonstrate the use of linear algebra to find the stationary state?
-The script demonstrates the use of linear algebra by showing how to set up an eigenvector equation for the transition matrix with an eigenvalue of 1. Solving this equation yields the stationary state, which represents the long-term probability distribution of the states in the Markov chain.
How can you determine if there are multiple stationary states in a Markov chain?
-To determine if there are multiple stationary states, you can look for the existence of more than one eigenvector with an eigenvalue equal to 1 for the transition matrix. Each eigenvector represents a different stationary state.
Outlines
🍔 Introduction to Markov Chains with a Restaurant Example
The video begins with an introduction to Markov chains, a concept used across various disciplines like statistics, biology, economics, physics, and machine learning. The presenter uses a restaurant example to illustrate the concept, where the restaurant serves only one of three foods—hamburger, pizza, or hot dog—based on what was served the previous day. This creates a predictable pattern, represented by a Markov chain diagram with weighted arrows indicating the transition probabilities between states. The Markov property is highlighted, which states that the future state depends solely on the current state, not on the sequence of past states. This property simplifies the handling of complex real-world problems.
📊 Markov Chain Properties and Simulation of a Random Walk
The video continues by discussing the properties of Markov chains. It emphasizes that the sum of the transition probabilities from any state must equal 1, as they represent a complete set of probabilities. The presenter then introduces a simulation of a random walk along the Markov chain to explore the probability distribution of states over time. By conducting a random walk for 10 consecutive days, the presenter demonstrates how the probabilities for each food item change and eventually seeks to determine if these probabilities converge to fixed values in the long run, indicating a stationary or equilibrium state.
🔍 Efficient Calculation of Stationary States Using Linear Algebra
The presenter acknowledges that the simulation method for finding stationary states may not be efficient and suggests using linear algebra as a more effective approach. The Markov chain is represented by an adjacency matrix, also known as the transition matrix, where each element denotes the transition probability between states. The goal is to find the stationary state, which is a row vector representing the long-term probability distribution of states. The presenter explains that this can be achieved by solving for the eigenvector of the transition matrix with an eigenvalue of 1, which corresponds to the stationary distribution. The method is shown to yield a close result to the one obtained from the simulation, validating the stationary state probabilities for the restaurant example.
Mindmap
Keywords
💡Markov Chains
💡Normalized Nerd
💡Machine Learning
💡State
💡Transition
💡Markov Property
💡Stationary Distribution
💡Adjacency Matrix
💡Eigenvector
💡Linear Algebra
Highlights
Introduction to Markov chains and their applications in various fields such as statistics, biology, economics, physics, and machine learning.
Explanation of the concept of Markov chains with an example of a restaurant serving three types of food with a specific rule based on the previous day's serving.
Use of weighted arrows in a diagram to represent the transitions between states in a Markov chain.
The Markov property, which states that the future state depends only on the current state, not on the sequence of previous states.
The requirement that the sum of the weights of outgoing arrows from any state in a Markov chain must equal 1, representing the total probability.
Discussion of special properties of certain Markov chains that deserve individual videos.
Exploring the Markov chain through a random walk simulation to understand the probability distribution of states over time.
The observation that probabilities may converge to fixed values in the long run, known as the stationary distribution or equilibrium state.
A Python script used to simulate a random walk for 100,000 steps to observe the convergence of probabilities to the stationary distribution.
Introduction to a more efficient method to find the stationary state using linear algebra and adjacency matrices.
Representation of a Markov chain as a directed graph and its translation into an adjacency matrix for efficient analysis.
The use of a row vector to represent the probability distribution of states and its multiplication with the transition matrix to find future probabilities.
The concept of a stationary state as an eigenvector equation where the eigenvalue is 1, representing a state that does not change over time.
The condition that the elements of the stationary state vector must sum up to 1, as it represents a probability distribution.
The method to determine if there are multiple stationary states by checking for more than one eigenvector with an eigenvalue of 1.
Comparison of the stationary state found using linear algebra with the results from the simulation, validating the findings.
Encouragement for viewers to request more videos on Markov chains and a call to action to subscribe and share the video.
Transcripts
hello people from the future welcome to
normalized nerd
today i'm gonna talk about markov chains
this is a concept that is used in many
places
from statistics to biology from
economics to physics and of course in
machine learning
i guess some of you have heard of markov
chains before but don't have a clear
idea about it
i hope by the end of this video you will
have a fair understanding of markov
chains
and you will know why they are so
interesting if you are new here then
please subscribe to my channel and hit
the bell icon
i make videos about machine learning and
data science regularly
so let's get started well as you know me
i like to start with an example
assume there's a restaurant that serves
only three types of foods
hamburger pizza and hot dog
but they follow a weird rule on any
given day
they serve only one of these three items
and it depends on what they had served
yesterday
in other words there is a way to predict
what they will serve tomorrow
if you know what they are serving today
for example there is a 60 chance that
tomorrow will be a pizza day
given that today is a hamburger day
i'm gonna represent it in the diagram as
weighted arrows
the arrow originates from the current
state and
points to the future state i'm using the
term
state because that's the convention
let's see another one
there's a 20 chance that tomorrow again
they will serve hamburgers
and that is represented as a
self-pointing arrow
well each arrow is called a transition
from one state to the other now i'm
gonna show you
all the possible transitions the diagram
you are seeing right now
is actually a markov chain yes the
concept is
that simple now let's discuss some
properties of the markov chain
the most important property of the
markov chain is that the future state
depends only on the current state not
the steps before
mathematically we can say the
probability that
n plus 1 x step will be x depends
only on the nth step not the complete
sequence of steps that came before n
at first glance this might not seem so
impressive
but on a closer look we can see that
this property
makes our life a lot easier while we
tackle some complicated real world
problems
let's understand it a little better
suppose the restaurant served
pizza on the first day hamburger on the
second
and again pizza on the third day now
what is the probability
that they will serve hot dogs on the
fourth day
well we just need to look at the third
day and it turns out to be
0.7 this is the heart of markov chains
and it's known as the markov property
the second important property is that
the sum of the weights of the outgoing
arrows
from any state is equal to 1.
this has to be true because they
represent probabilities
and for probabilities to make sense they
must add up to one
here i should probably tell you that
there are certain markov chains with
special properties
but they deserve individual videos on
their own so here i'm just gonna stick
to the basic kind of markov chains
now that you know what a markov chain
actually is let's explore
our markov chain by doing a random walk
along the chain
initially we are on a hamburger day
let's see what they serve for 10
consecutive days
so after 10 steps we have a situation
like this
now we want to find what is the
probability corresponding to
each of the food items aka
the probability distribution of the
states
well it's pretty simple just divide the
number of
occurrences of an item by the total
number of days
for hamburger it's 4 upon 10 for pizza
it's 2 upon 10 and it's 4 upon 10 for
hot dogs
it's obvious that if we change the
number of steps
then these probabilities will vary but
we are interested in
what happens in the long run do these
probabilities converge to fixed values
or they continue to change forever i
wrote a python script to simulate the
random work for hundred thousand steps
i found that the probabilities converge
to these values
and this probability distribution has a
special name
which is the stationary distribution or
the equilibrium state this simply means
that this
probability distribution doesn't change
with time
for this markov chain okay so we have
managed to find the stationary state
but this method doesn't seem to be very
efficient
is it moreover we don't know if there
exists any other stationary states well
a better way to approach this problem is
linear algebra
let me show you first of all let us
think about
how we can represent this markov chain
more efficiently
well this is essentially a directed
graph
so we can represent it by an adjacency
matrix
if you don't know what it is then please
don't worry it's very simple
the elements in the matrix just denote
the weight of the
edge connecting the two corresponding
vertices for example
the element in the second row and first
column denotes the weight
or the transition probability from pizza
to hamburger if an element is 0 then it
just means that there's no edge
between the two vertices this matrix is
also called
transition matrix let's denote it by a
remember that our goal is to find the
probabilities of
each state conventionally we take a row
vector
called pi whose elements represent the
probabilities of the states
basically pi denotes the probability
distribution of the states
suppose in the beginning we are on a
pizza day
so the second element which corresponds
to the pizza becomes one
and other two remain zero now see what
happens when we multiply this row vector
with our transition matrix
we get the second row of the matrix in
other words
we get the future probabilities
corresponding to the pisa state
then we take this result and put it in
the place of
pi zero
we will do this once again
now if there exists a stationary state
then
after a certain point the output row
vector should be exactly same
as the input vector let's denote this
special row vector as
pi so we should be able to write pi
a equals pi if you have ever taken a
course of linear algebra then you should
find this equation somewhat similar
to a very famous equation yes i'm
talking about
the eigenvector equation consider lambda
equal to 1 and just
reverse the order of multiplication and
you have got our equilibrium state
equation
how to interpret this you might ask well
we can imagine that
pi is a left eigenvector of matrix a
with eigenvalue equal to 1. please pause
the video if you need a moment to
convince yourself
now the eigenvector must satisfy another
condition
the elements of pi must add up to 1
because it denotes a probability
distribution
so after solving these two equations
we get the stationary state as this
it tells us that the restaurant will
serve hamburger about 35
of the days pigs are about 21 and hot
dog about 46 percent
using this technique we can actually see
if there are more than one stationary
states
can you guess how we just need to see if
there exists
more than one eigenvectors with
eigenvalue equal to 1.
isn't it super elegant now let's compare
this result
with the previous one that we got from
our simulation
look how close they are they kind of
validate each other
by now you should have a very good
understanding of markov chains
and you should be able to identify
markov chains successfully
obviously there is much more to learn
about different kinds of markov chains
and their properties
that cannot be covered in a single video
if you want me to make more videos on
this topic
then please let me know in the comment
section if you like this video
do share it and please please please
subscribe to my channel
stay safe and thanks for watching
[Music]
you
Посмотреть больше похожих видео
[CS 70] Markov Chains – Finding Stationary Distributions
Introdução - Cadeias de Markov (Markov Chains) - Outspoken Market
Hidden Markov Model Clearly Explained! Part - 5
Markov Models | Markov Chains | Markov Property | Applications | Part 1
Markov Chains and Text Generation
Aula 25 - Introdução à Cadeia de Markov - Python para Finanças Quantitativas
5.0 / 5 (0 votes)