WEBVTT
Kind: captions
Language: en
00:00:00.560 --> 00:00:09.310
Now I am going to move the Stationary Distribution,
the stationary distribution also a very important
00:00:09.310 --> 00:00:17.730
concept in the Markov chain and as such first
I am going to give the definition of a stationary
00:00:17.730 --> 00:00:18.730
distribution.
00:00:18.730 --> 00:00:24.770
The vector pi is called a stationary distribution
of a time homogeneous discrete time Markov
00:00:24.770 --> 00:00:33.830
chain, if that vector satisfies the first
condition, all these values pi j's are greater
00:00:33.830 --> 00:00:41.800
than or equal to 0 for all j and the summation
over pi j's that is going to be 1, and the
00:00:41.800 --> 00:00:48.540
third condition pi is going to be same as
the pi times P, where P is the one step transition
00:00:48.540 --> 00:01:00.060
probability matrix. So any vector pi satisfies
these three conditions.
00:01:00.060 --> 00:01:06.259
Then, that vector is going to be call it as
a stationary distribution, this is a nothing
00:01:06.259 --> 00:01:16.000
to do with the limiting distribution the one
I have discussed earlier, but for an irreducible
00:01:16.000 --> 00:01:23.259
aperiodic Markov chain the limiting distribution
is same as the stationary distribution that
00:01:23.259 --> 00:01:28.920
is also going to be same as the equilibrium
or a steady state distribution. All these
00:01:28.920 --> 00:01:34.460
three distributions are going to be same for
a irreducible aperiodic Markov chain.
00:01:34.460 --> 00:01:41.710
But, for in general, all these three things
are going to be different, so here I am giving
00:01:41.710 --> 00:01:56.289
the definition of a stationary distribution
by satisfying these three properties.
00:01:56.289 --> 00:02:04.590
Now I am going to give some important results
for that, the first result is for an irreducible
00:02:04.590 --> 00:02:09.670
aperiodic, positive recurrent Markov chain
the stationary distribution exists and it
00:02:09.670 --> 00:02:19.440
is unique, the one definition I have given
earlier, I have discussed aperiodic irreducible
00:02:19.440 --> 00:02:24.790
I have to include the positive recurrent also.
Because these three things are important for
00:02:24.790 --> 00:02:29.799
an irreducible aperiodic positive recurrent
Markov chain all these three distributions
00:02:29.799 --> 00:02:35.120
limiting distribution, stationary distribution,
steady state or equilibrium distribution,
00:02:35.120 --> 00:02:37.280
all three are same.
00:02:37.280 --> 00:02:44.590
I have to include the positive recurrent also,
so what I am giving in this result then pi
00:02:44.590 --> 00:02:54.129
is uniquely determined by solving this equation
pi equal to pi P with the summation of a pi's
00:02:54.129 --> 00:03:01.290
are going to be 1. So if I solve pi is equal
to pi P along with the summation of pi is
00:03:01.290 --> 00:03:08.939
equal to 1 that will give a unique pi and
that pi is going to be a stationary distribution
00:03:08.939 --> 00:03:15.150
for a irreducible, aperiodic, positive recurrent
Markov chain, irreducible means all the states
00:03:15.150 --> 00:03:18.590
are communicating with all other states.
00:03:18.590 --> 00:03:24.860
Aperiodic means the periodicity for a state
is 1, the greatest common divisor of a system
00:03:24.860 --> 00:03:32.620
coming back to the same state all the possible
steps that greatest common divisor is 1. The
00:03:32.620 --> 00:03:37.269
positive recurrent means it’s a recurrent
state that means with the probability 1, the
00:03:37.269 --> 00:03:43.019
system start from one state and coming back
to the same state that probability is 1, the
00:03:43.019 --> 00:03:49.959
positive recurrent means, the mean recurrence
time that is going to be a finite value.
00:03:49.959 --> 00:03:55.480
If these three conditions are going to be
satisfied by any time homogeneous discrete
00:03:55.480 --> 00:04:04.409
time Markov chain. Then the stationary distribution
can be computed using pi is equal to pi P
00:04:04.409 --> 00:04:11.489
and the summation is equal to 1 that is going
to be a unique value.
00:04:11.489 --> 00:04:19.250
I am giving the same example - I am giving
the same example that is the two state model
00:04:19.250 --> 00:04:28.400
with states 0 and 1 with probability is a
self-loop 1 - a and self-loop 1 - b and the
00:04:28.400 --> 00:04:34.139
system going from the state is 0 to 1 in one
step that is a and the system is going from
00:04:34.139 --> 00:04:43.350
the state 1 to 0 that probability is b, so
I am giving a very simple two state model
00:04:43.350 --> 00:04:52.070
and you can solve pi is equal to pi P and
summation is equal to 1 and you will get the
00:04:52.070 --> 00:04:59.310
probabilities.
00:04:59.310 --> 00:05:07.039
And these probabilities are same as the probability
you got it in the limiting state probability,
00:05:07.039 --> 00:05:14.810
if you solve.
00:05:14.810 --> 00:05:19.780
If you solve the two state model with the
pi is equal to pi P, you will get the probability
00:05:19.780 --> 00:05:26.520
is that pi 0 is going to be b divided by a
+ b and pi 1 is going to be a divided by a
00:05:26.520 --> 00:05:32.970
+ b, and it satisfies the summation of pi
is equal to 1 and it also satisfied pi is
00:05:32.970 --> 00:05:40.680
equal to pi P, that means in this model it
is irreducible aperiodic positive recurrent
00:05:40.680 --> 00:05:53.190
model, therefore the limiting distribution
is same as the stationary distributions also.
00:05:53.190 --> 00:06:04.840
The second example, that is with the infinite
state
00:06:04.840 --> 00:06:16.860
so here the number of states are going to
be a countably infinite, I
00:06:16.860 --> 00:06:23.660
can start with the to find out the stationary
distributions before that I have to cross
00:06:23.660 --> 00:06:29.759
check whether it is going to be irreducible
aperiodic positive recurrent Markov chain,
00:06:29.759 --> 00:06:35.830
it is irreducible because the way I have given
the probabilities. I make the assumption the
00:06:35.830 --> 00:06:38.539
probabilities are lies between 0 to 1.
00:06:38.539 --> 00:06:44.210
And the probability of lies - the q is also
lies between 0 to1, therefore each state is
00:06:44.210 --> 00:06:54.319
communicating with each other state, therefore
it is going to be a irreducible, the second
00:06:54.319 --> 00:07:02.450
one it is it has to be aperiodic, aperiodic
means the periodicity for each states, because
00:07:02.450 --> 00:07:06.759
the greatest common divisor is going to be
1, because the coming back to the state is
00:07:06.759 --> 00:07:12.920
via self-loop are going to the some other
state and coming back and their also has a
00:07:12.920 --> 00:07:13.920
self-loop.
00:07:13.920 --> 00:07:18.319
Therefore, it is going to be all the states
are going to be aperiodic, therefore the Markov
00:07:18.319 --> 00:07:30.960
chain is aperiodic. The third one positive
recurrent, since it is a infinite state model
00:07:30.960 --> 00:07:39.310
you cannot get the you cannot come to the
conclusion whether these Mu 00 is going to
00:07:39.310 --> 00:07:44.960
be a finite quantity unless otherwise substituting
the value of p and q.
00:07:44.960 --> 00:07:59.509
So what I will do I will make the assumption
assume that all states are positive recurrent
00:07:59.509 --> 00:08:09.610
then later I will find out what is the condition
to be a positive recurrent, so I make the
00:08:09.610 --> 00:08:14.270
assumption even I do not want to make the
- I do not want to make the assumption for
00:08:14.270 --> 00:08:18.669
all the states are going to be positive recurrent
I can make the assumption for only 1 state
00:08:18.669 --> 00:08:24.930
is going to be positive recurrent and since
it is a irreducible Markov Chain and all the
00:08:24.930 --> 00:08:26.889
states are going to be of the same type.
00:08:26.889 --> 00:08:31.349
Therefore, it will come to the conclusion
all the states are going to be a positive
00:08:31.349 --> 00:08:35.310
recurrent so I make the assumption one state
is going to be positive recurrent therefore
00:08:35.310 --> 00:08:42.830
it lands up all the states are going to be
a positive recurrent, now once I made a assumption
00:08:42.830 --> 00:08:50.930
of all the states are positive recurrent therefore
it satisfies all the results of a the first
00:08:50.930 --> 00:08:58.060
result that is a irreducible aperiodic positive
recurrent Markov chain with the infinite state
00:08:58.060 --> 00:08:59.060
space.
00:08:59.060 --> 00:09:04.370
Therefore, I can find out the I can come to
the conclusion the limiting distribution sorry,
00:09:04.370 --> 00:09:09.370
the stationary distribution exists and it
is going to be unique and that can be computed
00:09:09.370 --> 00:09:19.100
by solving the equation pi is equal to pi
P with the summation of pi, over i is equal
00:09:19.100 --> 00:09:34.430
to 1, where pi is the vector and P is the
one step transition probability matrix, that
00:09:34.430 --> 00:09:39.490
one step transition probability matrix can
be created using the state transition diagram
00:09:39.490 --> 00:09:41.700
which I have given.
00:09:41.700 --> 00:09:47.940
So if I take the - if I find out what is the
first equation from this vector pi is equal
00:09:47.940 --> 00:09:52.220
to pi 0, pi 1, pi 2 and so on, here also this
and P is the matrix.
00:09:52.220 --> 00:10:08.880
Therefore, I will get the first equation as
pi 0 is equal to pi 0 times (1 – p) + pi
00:10:08.880 --> 00:10:17.580
1 times q, so this is the first equation of
a, from the matrix pi is equal to in the matrix
00:10:17.580 --> 00:10:22.300
form pi is equal to pi P, so the first equation
is pi 0 is equal to pi naught times 1 minus
00:10:22.300 --> 00:10:32.290
p + pi 1 times q, so from this equation I
can get pi 1, because I can take this pi 0
00:10:32.290 --> 00:10:40.100
this side and I can cancel, so I will get
a pi 1 is equal to p divided by q times pi
00:10:40.100 --> 00:10:41.290
0.
00:10:41.290 --> 00:10:47.800
From the first equation we get the relation
pi 1 in terms of pi 0, now I will take a second
00:10:47.800 --> 00:10:58.139
equation from pi is equal to pi P, so that
will give pi 1 is equal to pi 0 times p +
00:10:58.139 --> 00:11:14.910
pi 1 times 1 minus p minus q + pi 2 times
q, so this equation have pi 0, pi 1 and pi
00:11:14.910 --> 00:11:25.610
2, so what I can do I can write pi 1 in terms
of pi 0 and I can simplify this equation if
00:11:25.610 --> 00:11:39.660
I simplify, I will get pi 2 is same as p square
by q square times pi 0.
00:11:39.660 --> 00:11:44.570
Because I am substituting pi 1 in terms of
pi 0, in this equation therefore I get pi
00:11:44.570 --> 00:11:52.149
2, in terms of pi 0, that is pi 2 is equal
to p square by q square times pi 0. Similarly,
00:11:52.149 --> 00:12:03.990
if I take the third equation and do the same
thing finally, I get pi 3 is equal to p cube
00:12:03.990 --> 00:12:18.040
by q cube pi 0, the same way I can go further
therefore I am get pi n in terms of pi 0,
00:12:18.040 --> 00:12:24.110
for n is equal to 1 2 3 and so on.
00:12:24.110 --> 00:12:30.920
So this is the way I can solve this equation
pi is equal to pi P that is a homogeneous
00:12:30.920 --> 00:12:35.890
equation we have to be very careful with the
homogeneous equation, so that trivial solutions
00:12:35.890 --> 00:12:40.240
are going to be 0, but we are try to find
out the non-trivial solutions therefore we
00:12:40.240 --> 00:12:48.079
are using the normalization that is the summation
of pi is equal to 1, till now I have not used,
00:12:48.079 --> 00:12:55.910
so I have just simplified that pi is equal
to pi P and getting pi n in terms of pi 0.
00:12:55.910 --> 00:13:07.670
Now I have to use summation of a pi i is equal
to 1 starting from i is equal to 0 to infinity
00:13:07.670 --> 00:13:18.120
therefore the pi 0 will be out 1 + p by q
+ p square by q square and so on, that is
00:13:18.120 --> 00:13:30.130
equal to 1, therefore the pi 0 is going to
be 1 divided by 1 + p by q +p square by q
00:13:30.130 --> 00:13:38.940
square and so on, that is pi 0, since it is
a infinite terms in the denominator as long
00:13:38.940 --> 00:13:43.880
as this is converges you will get a non-zero
value for a pi0.
00:13:43.880 --> 00:13:54.839
In turn you will get a pi n is equal to p
by q power n times pi 0 provided this denominator
00:13:54.839 --> 00:14:05.470
is going to be converges, when the denominator
is going to be converges in this situation
00:14:05.470 --> 00:14:15.660
as long as the p by q is going to be less
than 1, if p by q is less than 1 earlier condition
00:14:15.660 --> 00:14:21.839
is p is lies between 0 to 1 and q is lies
between 0 to 1, now I am making the additional
00:14:21.839 --> 00:14:28.170
condition p by q is less than 1 that will
ensure the denominator converges therefore
00:14:28.170 --> 00:14:31.490
the pi 0 is going to be a non-zero value.
00:14:31.490 --> 00:14:44.610
Therefore, the pi n's are going to be p divided
by q power n times pi 0, where pi 0 is written
00:14:44.610 --> 00:14:56.640
1 divided by 1 + p by q + p by q whole square
and so on, so provided p by q is less than
00:14:56.640 --> 00:15:05.310
1, if you recall we made the assumption the
states are going to be a positive recurrent,
00:15:05.310 --> 00:15:12.899
if this p by q is less than 1, then you can
conclude the mean recurrence time is going
00:15:12.899 --> 00:15:15.370
to be a finite value.
00:15:15.370 --> 00:15:20.009
If you make the assumption p by q is less
than 1 that will ensure the mean recurrence
00:15:20.009 --> 00:15:24.360
time for any state is going to be a finite
value therefore all the states are going to
00:15:24.360 --> 00:15:29.180
be positive recurrent and then the stationary
distribution exists therefore this is the
00:15:29.180 --> 00:15:39.000
condition for a positive recurrent state for
this model and the stationary distributions
00:15:39.000 --> 00:15:44.209
that is going to be pi n is equal to p by
q power n times pi 0.
00:15:44.209 --> 00:15:49.130
This is nothing but in a longer run what is
the probability that the system will be in
00:15:49.130 --> 00:15:58.449
the state n that probability is a p by q power
n times this pi 0 and pi 0 is given in this
00:15:58.449 --> 00:16:14.069
form, and in this example we have taken each
state for the p by q is same for all the states
00:16:14.069 --> 00:16:22.110
we can go for a in general situation the system
going from 0 to 1 could be p 0, system going
00:16:22.110 --> 00:16:26.040
from the state 1 to 2 maybe p 1 and so on.
00:16:26.040 --> 00:16:32.100
Therefore, it need not all the p i p's need
not be same and the q is also not be same
00:16:32.100 --> 00:16:37.660
so you can generalized this model and this
model is nothing but a one dimensional random
00:16:37.660 --> 00:16:48.350
walk and here the 0 is, it's a barrier the
system is not going away from the 0 in the
00:16:48.350 --> 00:16:54.089
left side therefore 0 is the barrier and this
is a one dimensional random walk in which
00:16:54.089 --> 00:17:00.420
the system is a keep moving into the different
states in subsequent steps.
00:17:00.420 --> 00:17:05.430
And there is a possibility the system may
be in the same state with the positive probability
00:17:05.430 --> 00:17:14.970
of 1 minus (p + q) in this model, in general
you can go for the p, p 0, p 1, p 2 and so
00:17:14.970 --> 00:17:18.940
on, and similarly, q 1, q 2, q 3 and so on
also.