In this video, I'll introduce some basic concepts of stochastic processes and Markov chains.
A stochastic process is also called a random process. It describes how a random variable
evolves over time. Let Xt be the value of some variable at time
t. Xt is a random variable and it is not known
with certainty before time t. An example of Xt is the number of students
in a classroom t minutes after the class starts. Some students may come in late. So, we don't
know the value of Xt for sure before time t.
Xt is called the state of the stochastic process. If the state of a stochastic process can be
observed at discrete time instants, then it is called a discrete-time stochastic process.
If the state of a stochastic process can be observed at any continuous time, then it is
called a continuous-time stochastic process. In this introductory course, we only discuss
discrete-time stochastic processes. A discrete-time stochastic process is a Markov
chain if, for t = 0, 1, 2… and so on, the states have the following relation. This is
an equation. The LHS is a conditional probability. It represents
the probability that at time t+1 the state is it+1, given that at time 0, the state is
i0, at time 1, the state is i1, at time t the state is it.
The RHS is also a conditional probability. It represents the probability that at time
t+1 the state is it+1, given that at time t the state is it.
This equation means the probability distribution of the state at time t+1 depends only on the
state at time t. It does not depend on the states before time t.
The initial state of the Markov chain can be described by an initial probability distribution.
Let qi be the probability that the chain is in state i at time 0.
If we have a total of s different states, then we call the vector q = [q1, q2, …, qs]
the initial probability distribution of the Markov chain.
The sum of q1 through qs is equal to 1 or 100%.
This conditional probability represents the probability that the system will be in state
j at time t+1, given it is in state i at time t.
A Markov chain is called a stationary Markov chain if this probability is independent of
time t. That means, the probability that the system
will be in state j at time t+1, given it is in state i at time t is equal to the probability
that the system will be in state j at time t, given it is in state i at time t-1, which
is also equal to the probability that the system will be in state j at time 1, given
it is in state i at time 0. Since this probability does not change, we
give it a shorter name pij. pij is called the transition probability from
state i at a previous time to state j at the current time.
If we have a total of s states, the transition probabilities from one state to another can
be displayed as an s x s matrix, like this. Since these elements are all probabilities,
they should all be greater than or equal to 0, but less than or equal to 1.
Also, the probability in each row must sum to 1. That means, if the Markov chain is in
state i at time t, it must transit to one of the s states at time t+1. So the sum should
be equal to one. There is no such requirement for the columns.
After all these preparation, let's see an example. This is a gambling problem.
Suppose that you start with $20 at time 0. You bet $10 each time in a gamble.
You win with a probability of 0.3, and lose with a probability of 0.7 in each gamble.
You will continue to gamble until you have $0 or $40. $0 means you don't have any money
left. $40 means you win $20 from your opponent and the opponent does not have any money left.
Now, let's try to model this problem as a Markov chain.
We use Xt to represent the money you have after each gamble at time t.
At the beginning of the game, you have X0=$20. When you gamble for the first time, there
is a 30% chance that you will win. That means you will have $30 afterwards. There is a 70%
chance that you will lose. That means you will have $10 afterwards.
If you have $30 now and continue to gamble, there is a 30% chance that you win and you
will have $40. There is a 70% chance that you lose and you will have $20.
If you have $10 now and continue to gamble, there is a 30% chance that you win and you
will have $20. There is a 70% chance that you lose and you will have $0.
If you have $0, the game is over and you will be trapped in this state with a probability
of 100%. Similarly, if you have $40, the game is also
over and you will be trapped in this state with a probability of 100%.
This is called a state transition diagram. Each node represents a state. Let's mark the
states as 1, 2, 3, 4, and 5. Each arc (i, j) represents the transition
probability pij. Based on this diagram, we can write out the
state transition probability matrix. For example, p32=0.7, it means, from state
3 to state 2,the transition probability is 0.7 or 70%.
Because we start at state 3, so the initial probability distribution is this. It means
we are 100% at state 3 at the beginning. This is a Markov chain because the amount
of money you have at time t+1 only depends on the amount of money at time t. It does
not depend on the amount of money you have before t.
Let's see another example. A box contains two white golf balls.
Choose a ball randomly and then ﬂip a coin. If the ball is white and the coin shows heads,
paint the ball red and put it back. If the ball is white and the coin shows tails,
paint the ball blue and put it back. If the ball is painted, then directly change
the color from red to blue or from blue to red and put it back, no matter whether the
coin shows heads or tails. Now, let's build the Markov chain for this
problem. Xt is defined as a vector w, r, and b, which
are the numbers of white, red, and blue balls respectively in the box at time t.
At the beginning, X0 = [2, 0, 0]. That means 2 white balls, 0 red balls, and
0 blue balls. Now, let's pick a ball randomly. It must be
a white ball. Then ﬂip a coin. If the coin shows heads, paint the ball red. Then, the
number of white balls will be reduced by 1, and the number of red balls will be increased
by 1. We end up in the state (1,1,0). The probability of being heads is 50%. So the
transition probability is 0.5. If the coin shows tails, paint the ball blue.
Then, the number of white balls will be reduced by 1, and the number of blue balls will be
increased by 1. We end up in the state (1,0,1). The probability of being tails is 50%. So
the transition probability is 0.5. Now, let's consider the second state. Let's
pick a ball randomly. It will be a red ball with a 50% probability. If it's red, we directly
change its color and paint it blue. Then, the number of red balls will be reduced by
1, and the number of blue balls will be increased by 1. We end up in the state (1,0,1). So the
transition probability is 0.5. When we pick the ball, it will be a white
ball with a 50% probability. If it's white, and if the coin shows heads, paint the ball
red. Then, the number of white balls will be reduced by 1, and the number of red balls
will be increased by 1. We end up in the state (0,2,0). The probability of being heads is
50%. So the transition probability is 0.5*0.5=0.25. If it's white, and if the coin shows tails,
paint the ball blue. Then, the number of white balls will be reduced by 1, and the number
of blue balls will be increased by 1. We end up in the state (0,1,1). The probability of
being tails is 50%. So the transition probability is 0.5*0.5=0.25.
Similarly, we can determine other states and the corresponding transition probabilities.
Let's mark the states as 1, 2, 3, 4, 5, and 6.
Based on this diagram, we can write out the state transition probability matrix.
Because we start at state 1, so the initial probability distribution is this.
This is also a Markov chain. Okay, I just introduced some basic concepts
of stochastic processes and Markov chains. Thanks for watching.