In the last example of the previous clip,
we have observed that the initial state of where
the Markov chain starts can matter, and that in some cases,
the influence of the initial state
never vanishes in the long run.
So when we wanted to calculate the probability of ending up
in state one, knowing that you started in state one,
give you that probability, and if you started in state three,
you had another long term probability.
And in case you were started in state two,
then you were equally likely to end up being in state one
or in state three.
We have said that this was due to the fact
that some states are not accessible
from some other states.
Our goal here is to make such a statement more
precise and formal.
In order to do so, we will classify the states of a Markov
chain in a transition diagram into two types, recurrent
and transient.
A state is said to be recurrent if starting
from that state, no matter where you go,
there is always a path to come back.
A state is said to be transient if it is not recurrent.
It means that starting from that state,
there is at least one place where you can go,
and then there will be no paths back to it.
For example, starting from state eight, no matter where you go,
there is always a path back to eight.
So eight will be said to be a recurrent state.
For the same reason, seven will also
be a recurrent state, as well as six.
Now, what about five?
From five, the only state where you can go to
is five itself, so five is also a recurrent state.
Let us look now at a state like state four.
From four, there is the possibility
of a path going through two, then one,
and then going to five, from which
there is no path back to four.
So four cannot be a recurrent state.
It is then called a transient state.
For the same reason, starting from three,
there is the possibility that after doing many transitions
around here, eventually, you will end up being in either two
and then go to six, or you will eventually be in one
and then go to five.
And from five or from six, there will be no path back to three,
so three is also a transient state.
And it is clear that for the same reason,
one will be a transient state, and two will also
be a transient state.
Now, if a state is transient, like three, four, one, or two,
it means that it will be visited only a finite number of times.
And in the long run, the probability
of being in a transient state will converge to zero.
The recurrent states of a Markov chain
can be grouped in different classes.
Here, in this example, we have two such classes.
Here, this is one class, and here you have another class.
What is so special about these classes?
Well, within one class, for example, in this class,
all recurrent states have a way to communicate
between each other, but there is no communication
between recurrent states of different classes.
From that recurrent state here, you
have no communication with that recurrent state here.
No communication in the sense that there
is no path joining that state to that state
or that state to that state.
The existence of more than one class of recurrent states,
like in this example, in a Markov chain,
will be the telling sign that initial states
will matter in that chain.
It's pretty clear here that if your Markov chain starts
in state five, you will never end up in state six, seven,
or eight, and if you start in one of the states
six, seven, eight, you will never end up in state five.
So depending on where you started,
the long range probability of being eventually in state six
will not be the same.