WEBVTT
Kind: captions
Language: en
00:00:00.550 --> 00:00:05.850
Now we are moving into the second type, in
the second type this is a reducible Markov
00:00:05.850 --> 00:00:14.860
Chain, but here each close communicating class
consists of only one element that is nothing
00:00:14.860 --> 00:00:22.210
but the absorbing states but more than one
communicating class are possible, therefore
00:00:22.210 --> 00:00:29.339
this type is called with one or more absorbing
states, here also my interest is to find out
00:00:29.339 --> 00:00:36.399
the stationary distribution. The stationary
distribution here the interests are of the
00:00:36.399 --> 00:00:37.800
different way.
00:00:37.800 --> 00:00:44.100
One is the probability of the absorption,
the other one is the what is the mean time
00:00:44.100 --> 00:00:51.620
before absorption, so for that I'm making
further assumption the state space is going
00:00:51.620 --> 00:01:02.710
to be finite, so with the time making Canonical
form. The Canonical form consists of all the
00:01:02.710 --> 00:01:08.970
absorbing states that I label it as A and
all the transient states are T. Therefore,
00:01:08.970 --> 00:01:12.830
the state space S is a A union capital T.
00:01:12.830 --> 00:01:19.400
Therefore, the Canonical form I collect all
the absorbing states in the first few rows
00:01:19.400 --> 00:01:26.220
and then remaining will be the all the transient
states, since the absorbing states P ii is
00:01:26.220 --> 00:01:36.090
equal to 1, therefore you will have a identity
matrix for the sub matrix of the matrix P
00:01:36.090 --> 00:01:42.920
corresponding to A to A. Whereas A to T absorbing
states to the transient states that elements
00:01:42.920 --> 00:01:43.920
are going to be zero.
00:01:43.920 --> 00:01:51.560
So that is the submatrix with the entities
zero, whereas T to A will be some matrix capital
00:01:51.560 --> 00:01:55.950
R and T to T will be sub matrix Q.
00:01:55.950 --> 00:02:06.280
So if you go for what is the n step transition
probability since it is identity matrix again
00:02:06.280 --> 00:02:11.890
also you will have identity matrix, whereas
T to A that is going to be a function of n
00:02:11.890 --> 00:02:20.920
whereas T to T, will be a power n that is
Q raise to power n, as n tends to infinity
00:02:20.920 --> 00:02:26.880
the system won't be in the transient states
therefore Q power n will tend to zero submatrix
00:02:26.880 --> 00:02:33.020
as n tends to infinity, and these probabilities
are going to be zero for all i, j belonging
00:02:33.020 --> 00:02:38.540
to T, T is nothing but the set of transient
states.
00:02:38.540 --> 00:02:47.630
Our interest is here what is the probability
of absorption? Because we have a few one or
00:02:47.630 --> 00:02:55.150
more absorbing states so if the system starts
from some transient state what is the probability
00:02:55.150 --> 00:03:02.880
that the system will be absorbed into these
absorption states, so for that I am going
00:03:02.880 --> 00:03:09.660
to start with the Chapman Kolmogorov equation.
That's Chapman Kolmogorov equation for the
00:03:09.660 --> 00:03:14.520
(n + 1) th step the system going from the
state i to k.
00:03:14.520 --> 00:03:19.810
That probability same as what are all the
possible the system can go make a one step
00:03:19.810 --> 00:03:26.170
from i to j and then j to k in n steps all
the possibilities j belonging to S, where
00:03:26.170 --> 00:03:38.569
S is the state space. I know either I have
a one sorry, either I have a transient states
00:03:38.569 --> 00:03:47.220
or all other states are absorbing states.
Therefore, if k is going to be the absorbing
00:03:47.220 --> 00:03:52.600
state then P kk is equal to 1, that means
a one-step transition probability of system
00:03:52.600 --> 00:03:55.490
moving from state k to k that is 1.
00:03:55.490 --> 00:04:04.730
Therefore, i to k in (n + 1) steps that probability
I can split I can make i to k in one step
00:04:04.730 --> 00:04:13.321
then forever I will be in the state k plus
I would have move to the state i to j, where
00:04:13.321 --> 00:04:27.740
j is another transient state it could be same
also then j to k in n steps. Now I am defining
00:04:27.740 --> 00:04:34.550
what is the meaning of probability of absorption?
That I am denoting with the letter a suffix
00:04:34.550 --> 00:04:35.999
i, k that is nothing.
00:04:35.999 --> 00:04:43.969
But the probability that the system starts
in state i it starts in state i eventually
00:04:43.969 --> 00:04:54.080
get absorbed in a absorbing state k, so the
first letter is the starting state and the
00:04:54.080 --> 00:05:01.219
second k is the absorbing state, so this is
a probability of absorption starting from
00:05:01.219 --> 00:05:08.000
the state i to the absorption state k. Now,
I am taking the equation 1 as I make n tends
00:05:08.000 --> 00:05:16.430
to infinity in both side the, left hand side
will be a of i, k because as n tends to infinity
00:05:16.430 --> 00:05:23.039
so this will be a i k, similarly P jk of n
that is also a suffix jk.
00:05:23.039 --> 00:05:29.229
Therefore, I will have a ik, this side and
a jk, so this is sort of recursive equation
00:05:29.229 --> 00:05:34.680
so this is in the element form I can go for
in the matrix form.
00:05:34.680 --> 00:05:43.839
So I can write a ik as a matrix capital A,
therefore in the matrix form the previous
00:05:43.839 --> 00:05:53.280
this equation for all values of i this equation
as in the matrix form A is equal to R matrix,
00:05:53.280 --> 00:06:05.909
because this P i to k where i is the transient
state and k is the absorbing state so transient
00:06:05.909 --> 00:06:13.490
state to the absorption state - transient
state to the absorption state that submatrix
00:06:13.490 --> 00:06:15.509
is R.
00:06:15.509 --> 00:06:24.439
Therefore, in the matrix form capital A is
equal to R matrix + Q matrix that is a the
00:06:24.439 --> 00:06:31.479
one step transition of system is moving from
transient to transient multiplied by A matrix
00:06:31.479 --> 00:06:38.930
so I can do the simplification so I get A
matrix equals to I minus Q inverse R matrix,
00:06:38.930 --> 00:06:45.620
and here this I minus Q inverse that is nothing
but the fundamental matrix. So once you are
00:06:45.620 --> 00:06:51.219
able to calculate find out the fundamental
matrix multiplied by the R matrix that will
00:06:51.219 --> 00:06:58.879
give the probability of absorption starting
from the transient state and reaching absorption
00:06:58.879 --> 00:06:59.879
state.
00:06:59.879 --> 00:07:06.210
And these probabilities not independent of
initial state that is very important whereas
00:07:06.210 --> 00:07:13.379
the previous type of reducible Markov chain
that is a independent of initial state whereas
00:07:13.379 --> 00:07:22.350
here the probability of absorption is not
independent of the initial state i. So this
00:07:22.350 --> 00:07:29.939
you can visualize through one example that
I am going to present later.
00:07:29.939 --> 00:07:37.289
The next result interested in the reducible
Markov chain with one or more absorbing states
00:07:37.289 --> 00:07:44.389
that is a what is the time to absorption?
Basically our interest to get the meantime
00:07:44.389 --> 00:07:51.330
to absorption starting from the transient
state to a absorption state, that means how
00:07:51.330 --> 00:07:59.699
much time on average the system is spending
in the transient states before absorption
00:07:59.699 --> 00:08:00.849
that is very important.
00:08:00.849 --> 00:08:07.610
Because many application has reducible Markov
chain in which more than one absorption states
00:08:07.610 --> 00:08:16.349
are there with the transient state therefore
what is the mean time up to absorption that
00:08:16.349 --> 00:08:21.610
means how much time spending in the transient
states before the absorption so for that I
00:08:21.610 --> 00:08:28.659
am going to define the random variable Ti.
The Ti denotes the number of steps including
00:08:28.659 --> 00:08:35.130
the starting state i in which the Markov chain
reminds in a transient state before entering
00:08:35.130 --> 00:08:37.380
a absorption state.
00:08:37.380 --> 00:08:48.490
So there is a possibility the system would
have been spending at least one step before
00:08:48.490 --> 00:08:54.550
absorption or two steps or three steps and
so on, therefore that is going to be a random
00:08:54.550 --> 00:09:02.640
variable it is a discrete random variable
with the possible values are 1, 2, 3 and so
00:09:02.640 --> 00:09:08.370
on. Our interest is not only finding out the
distribution of Ti, our interest is to find
00:09:08.370 --> 00:09:16.690
out what is the mean time up to absorption,
from the transient state to a absorbing state.
00:09:16.690 --> 00:09:25.180
So this probability can be computed by find
out what is the probability of Ti is equal
00:09:25.180 --> 00:09:32.070
to n for some n, n can take the value 1, 2,
3 and so on. So that discrete random variable
00:09:32.070 --> 00:09:38.180
probability, probability mass function can
be computed in this way you find out what
00:09:38.180 --> 00:09:43.110
is the probability of Ti is greater than or
equal to n minus 1 minus what is the probability
00:09:43.110 --> 00:09:45.730
that Ti is greater than or equal to n.
00:09:45.730 --> 00:09:52.550
If you find the difference that is same as
the probability mass at n, but this is same
00:09:52.550 --> 00:10:00.670
as the Ti greater than or equal to n minus
1, that is same as the (n -1 )th step the
00:10:00.670 --> 00:10:06.490
system is in the transient state, if Ti is
going to be greater than or equal to n minus
00:10:06.490 --> 00:10:17.800
1, that means the system spends at least (n
– 1) steps in the transient states once
00:10:17.800 --> 00:10:22.160
it goes to the absorptions state then it need
cannot come back to the transient states.
00:10:22.160 --> 00:10:28.629
Therefore, the meaning of Ti greater than
or equal to n minus1 that is same as the (n-1)
00:10:28.629 --> 00:10:35.200
th step the system in the transient states,
so both the events are equivalent, therefore
00:10:35.200 --> 00:10:42.370
the probabilities are equal. Similarly, you
can argue Ti greater than or equal to n means
00:10:42.370 --> 00:10:50.000
at least n steps the system in the transient
state before absorption, that is same as in
00:10:50.000 --> 00:10:58.110
the n th step the system is in the transient
state.
00:10:58.110 --> 00:11:04.899
The probability of (n- 1) th step the system
is in the transient state that is same as
00:11:04.899 --> 00:11:09.820
what is the what are all the possibilities
the system would have move from state i to
00:11:09.820 --> 00:11:17.470
j in (n – 1) steps, you add all the possibilities
j belonging to T, you add all the possibilities
00:11:17.470 --> 00:11:25.069
of the transient states that summation will
give this probability similarly, for the Xn
00:11:25.069 --> 00:11:32.660
belonging to T, this is in the for fixed i,
where i is belonging to the transient state.
00:11:32.660 --> 00:11:39.949
now I will go for I know that for i, j belonging
to T, the n step transition probability is
00:11:39.949 --> 00:11:48.149
nothing but the submatrix that is Q power
n, if you recall the way we made Canonical
00:11:48.149 --> 00:11:57.509
form of a P matrix the T to T, that is a Q
matrix, therefore for any nth step that is
00:11:57.509 --> 00:12:04.529
going to be Q power n, so this is what I am
using for i, j belonging to T the sub matrix
00:12:04.529 --> 00:12:08.339
of P power n that is Q power n.
00:12:08.339 --> 00:12:15.970
Therefore, for i, j belonging to T, the n
step transition of system moving from i to
00:12:15.970 --> 00:12:23.839
j that is Q power n, therefore I can substitute
here in the above equation so the probability
00:12:23.839 --> 00:12:34.950
mass at n that is same as Q power n minus
1 into I minus Q into e vector, once I know
00:12:34.950 --> 00:12:40.649
the probability mass function for the discrete
random variable Ti then I can find out the
00:12:40.649 --> 00:12:49.230
mean, mean is nothing but summation n times
the probability mass at n Ti is equal to n.
00:12:49.230 --> 00:12:56.629
If I add submission over n, that is going
to be the meantime up to absorption that is
00:12:56.629 --> 00:13:03.220
going to be do the simple calculation you
will get a I minus Q inverse into e vector,
00:13:03.220 --> 00:13:08.000
this I minus Q inverse is nothing but the
fundamental matrix that means if you find
00:13:08.000 --> 00:13:13.760
out the fundamental matrix multiplied by the
R sub matrix you will get the probability
00:13:13.760 --> 00:13:20.300
of absorption if you multiplied by the e vector
you will get the mean time up to the absorption.