WEBVTT
Kind: captions
Language: en
00:00:00.470 --> 00:00:10.900
I am going to give one more example this has
3 states and this is a state transition diagram
00:00:10.900 --> 00:00:15.120
and the values are nothing, but the rates
in which the system is moving from one state
00:00:15.120 --> 00:00:17.850
to other states.
00:00:17.850 --> 00:00:22.999
So that is the difference between the state
transition diagram of a DTMC and the CTMC.
00:00:22.999 --> 00:00:28.109
So this is a rate in which the system is moving
from one state to another state and some arcs
00:00:28.109 --> 00:00:34.800
are not there that means there is a no way
the system is moving from the state 2 to 3
00:00:34.800 --> 00:00:37.180
in a small interval of time.
00:00:37.180 --> 00:00:41.150
Whereas all the other possibilities I have
given.
00:00:41.150 --> 00:00:47.740
So the corresponding Q matrix it is a three
cross three matrix and you can make out all
00:00:47.740 --> 00:00:53.760
the row sum are going to be 0 and the diagonal
elements are minus of some of other values
00:00:53.760 --> 00:01:03.640
the same rows and other than the diagonal
elements the values are greater than or equal
00:01:03.640 --> 00:01:04.640
to 0.
00:01:04.640 --> 00:01:13.810
My interest is to find out the time dependent
solution for this example also.
00:01:13.810 --> 00:01:21.830
I can make a forward Kolmogorov equation P
dash of t is equal to P of t times Q it is
00:01:21.830 --> 00:01:27.480
a 3 cross 3 matrix therefore I will have a
3 equations and I have one equation I can
00:01:27.480 --> 00:01:32.460
have summation of probabilities equal to 1
and I can start with the initial condition
00:01:32.460 --> 00:01:39.370
the system being in the state 1 at time 0
the probability is 1, I can start with that
00:01:39.370 --> 00:01:45.460
and I can solve those three equations with
the initial condition and I can get the solution
00:01:45.460 --> 00:01:47.210
that is a one way.
00:01:47.210 --> 00:01:54.630
Since it is a finite state CTMC there are
many ways to get the time dependent solution
00:01:54.630 --> 00:02:00.921
basically you have to solve the system of
different differential equations with the
00:02:00.921 --> 00:02:03.000
initial conditions.
00:02:03.000 --> 00:02:09.179
Here I am using the Eigen value method that
means find the Eigen values for the Q matrix.
00:02:09.179 --> 00:02:15.950
Therefore, use the Eigen value and Eigen vector
concept and you get the P11 of t with the
00:02:15.950 --> 00:02:22.740
unknown k1, k2, k3 and to find the unknown
to k1, k2, k3 use the initial condition.
00:02:22.740 --> 00:02:30.450
Here I am using the initial condition as well
as the Q matrix values the q 11 that means
00:02:30.450 --> 00:02:37.760
the element corresponding to the 1, 1 that
is nothing but the P dash of 1, 1 of 0.
00:02:37.760 --> 00:02:43.010
Similarly, if I go for Q square matrix and
q11 of 2.
00:02:43.010 --> 00:02:51.260
The element in the 1, 1 in the Q square matrix
that is nothing but P double dash of 1, 1
00:02:51.260 --> 00:02:52.319
of 0.
00:02:52.319 --> 00:03:02.129
Therefore now I can use these three initial
conditions to get the unknown values k1, k2
00:03:02.129 --> 00:03:03.410
and k3.
00:03:03.410 --> 00:03:08.890
So once I know the k1, k2, k3, I can substitute
that for the P11 of t is equal to this much.
00:03:08.890 --> 00:03:19.540
Similarly, I can go for finding the P1, 2
of t and P1, 3 of t.
00:03:19.540 --> 00:03:27.000
I do not want P1, 3 in the same way because
once I know the P1, 1 of t and P1, 2 of t.
00:03:27.000 --> 00:03:32.989
So P 1, 3 of t is nothing but 1 minus of that
those two probabilities because there is summation
00:03:32.989 --> 00:03:35.150
of probabilities is equal to 1.
00:03:35.150 --> 00:03:41.070
So this is the other way of getting the time
dependent solution the transition probability
00:03:41.070 --> 00:03:50.819
of system being in the state j given that
it was in the state I at time 0.
00:03:50.819 --> 00:04:01.330
Suppose the CTMC has the finite state space
then I can use the exponential matrix also
00:04:01.330 --> 00:04:05.520
to get the time dependent solution that what
I have given this way.
00:04:05.520 --> 00:04:09.950
So start with the forward equation.
00:04:09.950 --> 00:04:17.220
Therefore, the solution is going to be P of
t is equal to P of 0 e power Qt.
00:04:17.220 --> 00:04:26.840
P of t is a matrix P of 0 is the matrix e
power Qt that is also again going to be a
00:04:26.840 --> 00:04:32.430
matrix exponential matrix therefore I am writing
it e power Qt is nothing but Q is the matrix
00:04:32.430 --> 00:04:35.940
and t is the real value.
00:04:35.940 --> 00:04:39.080
So if greater than or equal to 0 therefore
e power Qt is going to be I matrix.
00:04:39.080 --> 00:04:49.130
I matrix is nothing but the identical matrix
of order whatever the state number plus the
00:04:49.130 --> 00:04:56.360
summation n is equal to 1 to infinity of Q
power n times t power n divided by n factorial.
00:04:56.360 --> 00:05:01.090
So the whole thing is going to be exponential
matrix and using that you can get the P of
00:05:01.090 --> 00:05:02.500
t.
00:05:02.500 --> 00:05:08.461
I am not going detailed for how to compute
this e power Qt and so on, but whenever you
00:05:08.461 --> 00:05:15.150
have CTMC the finite space through this method
also one can get the time dependent solution.
00:05:15.150 --> 00:05:22.259
So with this I have completed the examples
for the CTMC to find out the time dependent
00:05:22.259 --> 00:05:23.870
or transient probabilities.
00:05:23.870 --> 00:05:32.800
Now, I am moving into the limiting distribution
the way we discuss the limiting distribution
00:05:32.800 --> 00:05:38.550
for the DTMC the same concept can be used
for the CTMC also.
00:05:38.550 --> 00:05:46.960
The change is instead of one step transition
probability matrix here we have to use the
00:05:46.960 --> 00:05:50.400
Infinitesimal Generator Matrix in a different
way.
00:05:50.400 --> 00:05:57.950
So I am first giving the Ergodic Theorem,
whenever the CTMC is irreducible that means
00:05:57.950 --> 00:06:04.330
all the states are communicating with all
other states.
00:06:04.330 --> 00:06:07.080
Since all the states are communicating with
all other states.
00:06:07.080 --> 00:06:12.340
So if one is of the particular type it is
a positive recurrent then all the other states
00:06:12.340 --> 00:06:13.949
are going to be a positive recurrent.
00:06:13.949 --> 00:06:19.240
If one is going to be a null recurrent then
all the other states also going to be a null
00:06:19.240 --> 00:06:20.240
recurrent.
00:06:20.240 --> 00:06:27.759
So here I am making the assumption the CTMC
is irreducible as well as all the states are
00:06:27.759 --> 00:06:34.889
positive recurrent then the limiting distribution
always exist.
00:06:34.889 --> 00:06:41.610
Suppose, it is independent of the initial
state, it need not be a independent of initial
00:06:41.610 --> 00:06:47.310
states suppose the same thing is independent
of initial state then I can write that limiting
00:06:47.310 --> 00:06:50.160
probability is Pij of t.
00:06:50.160 --> 00:06:51.920
Since it is independent of i.
00:06:51.920 --> 00:06:54.500
I can write it as the pi j.
00:06:54.500 --> 00:07:03.210
Then I can form a vector and since it is a
limiting distribution it is a probability
00:07:03.210 --> 00:07:04.210
distribution.
00:07:04.210 --> 00:07:07.380
Therefore, the probabilities are these probabilities
are always greater than or equal to 0.
00:07:07.380 --> 00:07:09.729
And the summation of probability is going
to be 1.
00:07:09.729 --> 00:07:14.819
It would not be less than 1 that is the Ergodic
theorem says.
00:07:14.819 --> 00:07:21.069
Whenever you have a irreducible CTMC with
all the states are positive recurrent then
00:07:21.069 --> 00:07:26.669
as t tends to infinity the system has the
distribution limiting distribution.
00:07:26.669 --> 00:07:35.330
If it is independent of initial states, then
you can label with the pi j as the probabilities.
00:07:35.330 --> 00:07:40.710
And this probability distribution satisfies
it is a probability mass function therefore
00:07:40.710 --> 00:07:45.430
it satisfies the probability mass function
conditions.
00:07:45.430 --> 00:07:52.490
That means whenever you have a dynamical system
in which it is irreducible model and all the
00:07:52.490 --> 00:07:57.319
states are positive recurrent that means the
mean recurrence time is going to be finite
00:07:57.319 --> 00:07:58.319
value.
00:07:58.319 --> 00:08:07.169
Then that system is called it as a Ergodic
system or the Ergodic concept can be used
00:08:07.169 --> 00:08:12.600
therefore as t tends to infinity you can get
the limiting distribution.
00:08:12.600 --> 00:08:16.789
If it is independent of initial state means,
whatever be the state, you are going to do
00:08:16.789 --> 00:08:24.229
it for the discrete end stimulation for the
dynamical system that is for a Ergodic system
00:08:24.229 --> 00:08:32.030
then the initial condition state does not
matter to get the limiting distribution.
00:08:32.030 --> 00:08:38.569
Later we are going to give some few examples
how to find out the limiting distribution.
00:08:38.569 --> 00:08:41.610
I am explaining the stationary distribution
also.
00:08:41.610 --> 00:08:52.129
The stationary distribution the way I have
discuss the DTMC the CTMC also same.
00:08:52.129 --> 00:08:57.050
So I have a vector if the vector satisfies
these three conditions; probabilities therefore
00:08:57.050 --> 00:09:02.290
greater than or equal to zero, summation is
equal to 1 and you should be able to solve
00:09:02.290 --> 00:09:04.529
the solution and get the pi.
00:09:04.529 --> 00:09:06.839
It is a homogenous situation.
00:09:06.839 --> 00:09:12.470
So you need a second condition to have the
nonnzero probabilities.
00:09:12.470 --> 00:09:23.939
So if you solve pi Q equal to 0 along with
the summation of pi j is equal to 1 and if
00:09:23.939 --> 00:09:26.030
this pi j exist then the CTMC has the stationary
distribution.
00:09:26.030 --> 00:09:33.379
The similar way I have discussed the stationary
distribution for the DTMC model also instead
00:09:33.379 --> 00:09:38.889
of pi Q is equal to 0 we had a pi P is equal
to pi.
00:09:38.889 --> 00:09:44.980
So if any vector satisfies that pi P is equal
to pi and summation of pi i is equal to 1
00:09:44.980 --> 00:09:47.529
and all the pi i are greater than or equal
to 0.
00:09:47.529 --> 00:09:50.899
Then that is going to be a stationary distribution
for DTMC.
00:09:50.899 --> 00:09:57.899
The same way if pi Q is equal to 0 and summation
of pi j is equal to 1, pi j are greater than
00:09:57.899 --> 00:09:59.179
or equal to 0.
00:09:59.179 --> 00:10:04.569
If this is satisfied by any vector, then that
is going to be the stationary distribution
00:10:04.569 --> 00:10:06.970
for a Time Homogenous CTMC.
00:10:06.970 --> 00:10:17.459
Every time we are discussing the default CTMC
that is the time homogenous CTMC.
00:10:17.459 --> 00:10:23.300
The main result for the stationary distribution
whenever you have an irreducible positive
00:10:23.300 --> 00:10:28.929
recurrent CTMC the stationary distribution
exists and that is going to be unique.
00:10:28.929 --> 00:10:36.189
Whenever the CTMC is a positive recurrent
as well as irreducible there is no need of
00:10:36.189 --> 00:10:45.820
periodicity in the CTMC whereas the same stationary
distribution for the DTMC we have included
00:10:45.820 --> 00:10:50.639
one more condition that is aperiodic, but
for the CTMC there is no periodicity for the
00:10:50.639 --> 00:10:51.649
state.
00:10:51.649 --> 00:11:00.779
Therefore, as long as the system is irreducible
and the positive recurrent then the stationary
00:11:00.779 --> 00:11:08.249
distribution exist and it is unique and by
solving these equations you can get the unique
00:11:08.249 --> 00:11:09.459
stationary distribution.