WEBVTT
Kind: captions
Language: en
00:00:00.210 --> 00:00:07.609
I am to give one simple example for this type
of reducible Markov chain with the transient
00:00:07.609 --> 00:00:12.360
state and one or more absorption state.
00:00:12.360 --> 00:00:17.579
I am making the assumption that is a positive
recurrent, so instead of positive recurrent
00:00:17.579 --> 00:00:22.130
I have a finite Markov chain so the finite
Markov chain at least one state is a positive
00:00:22.130 --> 00:00:29.369
recurrent therefore both are going to be an
absorbing state therefore you do not want
00:00:29.369 --> 00:00:31.059
those conditions.
00:00:31.059 --> 00:00:42.359
So here in this model the states 0, 1, 2 are
the transient states 3 and 4 are absorbing
00:00:42.359 --> 00:00:43.620
states.
00:00:43.620 --> 00:00:49.980
This is a easy example in which you can visualize
someone who is doing the undergraduate with
00:00:49.980 --> 00:00:56.980
the probability of, he is not able to complete
undergraduate in the next step with the probability
00:00:56.980 --> 00:01:01.329
of he is moving into the post-graduate in
the next step.
00:01:01.329 --> 00:01:07.060
So I am making a DTMC with the assumption
the memory less property is satisfied and
00:01:07.060 --> 00:01:08.540
so on.
00:01:08.540 --> 00:01:13.310
From the post-graduate either someone gets
the job1 with the probability one third or
00:01:13.310 --> 00:01:19.650
not able to complete the post-graduate that
probability is one third or he completes and
00:01:19.650 --> 00:01:22.299
go to the PhD program one third.
00:01:22.299 --> 00:01:29.700
From the PhD one fourth is not able to complete
the PhD in the next step or with the probability
00:01:29.700 --> 00:01:32.369
three fourth he is getting the job2.
00:01:32.369 --> 00:01:39.510
Now you can visualize the questions, what
is the probability that I observed into the
00:01:39.510 --> 00:01:45.390
state job1 or job2 that is the probability
of assumptions.
00:01:45.390 --> 00:01:51.729
The next question, how much time on average
I will be spending in the transient states
00:01:51.729 --> 00:01:56.070
in the study before I get the job.
00:01:56.070 --> 00:02:02.610
So this is the way you can visualize reducible
Markov chain with this type.
00:02:02.610 --> 00:02:08.220
So these two questions are going to be answered
by finding the probability of absorption and
00:02:08.220 --> 00:02:12.660
meantime up to absorption.
00:02:12.660 --> 00:02:18.750
First let write the P matrix in the canonical
form when all the sub matrix I made it in
00:02:18.750 --> 00:02:26.420
the different colors so three and four are
going to form a each one is going to be absorbing
00:02:26.420 --> 00:02:34.250
states, so therefore A to A that is identity
matrix; A to capital T that is a 0 matrix—sub
00:02:34.250 --> 00:02:42.860
matrix then T to A that is again a matrix
that is R; then T to T that is a Q matrix.
00:02:42.860 --> 00:02:49.770
So what we need the Q matrix and the R matrix
both are sub matrix capital P that is the
00:02:49.770 --> 00:02:52.110
one step transition probability matrix.
00:02:52.110 --> 00:02:59.660
So you find out what is I-Q, I is identify
matrix of the same order I3 here -Q matrix
00:02:59.660 --> 00:03:07.080
so you know the Q matrix is this so I-Q matrix
find out the inverse that inverse is this
00:03:07.080 --> 00:03:14.770
much so from this if you multiplied the vector
e that is 1,1,1 we will get the meantime to
00:03:14.770 --> 00:03:19.290
absorption.
00:03:19.290 --> 00:03:26.430
And also you can find out the probability
of absorption after finding the I- Q inverse
00:03:26.430 --> 00:03:32.180
that is the fundamental matrix multiplied
by the R in this matrix you will get the probability
00:03:32.180 --> 00:03:34.390
of the absorption.
00:03:34.390 --> 00:03:39.560
I am not giving here, the numerical calculation.
00:03:39.560 --> 00:03:48.470
See the result, so this is the mean time upto
the absorption and this is the probability
00:03:48.470 --> 00:03:49.470
of absorption.
00:03:49.470 --> 00:03:52.040
First, let us discuss the probability of absorption.
00:03:52.040 --> 00:04:00.920
If the system starts from the state 0 state
three is nothing but the job1 so with the
00:04:00.920 --> 00:04:07.130
probability half you would have been observed
into the job one with the probability half,
00:04:07.130 --> 00:04:12.060
if the system starts from the state 0 from
the undergraduate.
00:04:12.060 --> 00:04:18.239
Similarly, with the job2 that probability
is half, it is a probability mass function
00:04:18.239 --> 00:04:24.280
either you will be in the job1 or job2 there
is the probability of absorption.
00:04:24.280 --> 00:04:29.110
If you would have started-- starting with
the post-graduate then with the probability
00:04:29.110 --> 00:04:34.310
half and half you may be in the job1 and 2.
00:04:34.310 --> 00:04:39.189
Whereas, if you beginning with the PhD program
not this two programs that is not possible
00:04:39.189 --> 00:04:41.819
but still this is just example.
00:04:41.819 --> 00:04:48.949
So if you start with the PhD program then
definitely you will land up with the job2
00:04:48.949 --> 00:04:55.430
with the probability one because there is
no arc from two to one and land up the job
00:04:55.430 --> 00:05:00.850
one therefore the probability of absorption
into the job1 that probability is 0.
00:05:00.850 --> 00:05:07.150
Just for illustration, therefore you can make
out how the calculation goes.
00:05:07.150 --> 00:05:11.729
So here the probability of absorption starting
from the state two that probability is zero
00:05:11.729 --> 00:05:15.430
to the job1 whereas job2 that probability
is one.
00:05:15.430 --> 00:05:21.370
So this is the probability distribution of
probability of absorption starting from this
00:05:21.370 --> 00:05:22.930
transient states.
00:05:22.930 --> 00:05:31.599
Similarly, you can visualize the meantime
up to the absorption.
00:05:31.599 --> 00:05:33.469
These zeros can be discussed first.
00:05:33.469 --> 00:05:41.960
So if the system starts from the state two
what is the average number of steps the system
00:05:41.960 --> 00:05:50.710
goes from the state two to zero then it goes
to the absorption state.
00:05:50.710 --> 00:05:55.689
That is not possible the system is going from
two to zero, therefore the meantime is going
00:05:55.689 --> 00:05:57.530
to be zero.
00:05:57.530 --> 00:06:03.310
Because the minimum time is one or minimum
number of steps system spending in the transient
00:06:03.310 --> 00:06:09.960
states are one and so on therefore mean is
zero here.
00:06:09.960 --> 00:06:17.669
Similarly, the system is starting from the
state two and land up one and from there it
00:06:17.669 --> 00:06:22.949
goes to the absorption state that is also
not possible therefore that mean is also zero
00:06:22.949 --> 00:06:31.539
whereas all other values the greater than
0 that gives what is the average number of
00:06:31.539 --> 00:06:39.050
steps the system is starting from these transient
states and reaching these a transient before
00:06:39.050 --> 00:06:48.330
absorbed into any one of the absorption states
accordingly we have these values.
00:06:48.330 --> 00:06:57.360
With this example I go to the next example
that is a Reducible Markov Chain.
00:06:57.360 --> 00:07:02.240
And this is a special case of random walk
also.
00:07:02.240 --> 00:07:06.879
Let me discuss, what is the example.
00:07:06.879 --> 00:07:09.139
This is called the Gambler’s Ruin problem.
00:07:09.139 --> 00:07:12.680
Let me define what is the Gambler’s Ruin
problem.
00:07:12.680 --> 00:07:20.509
Consider a gambler who starts with an initial
fortune of Rs. i, i amount he has at the time
00:07:20.509 --> 00:07:21.509
0.
00:07:21.509 --> 00:07:31.289
And then on each gamble either wins Rs.1 or
loses Rs.1 independent of the past with the
00:07:31.289 --> 00:07:40.100
probabilities p and 1-p respectively so in
this game there is no draw there is no type.
00:07:40.100 --> 00:07:42.240
Either he wins or he loses.
00:07:42.240 --> 00:07:52.069
Wins with one rupee loses one rupee and corresponding
probabilities are p and 1-p.
00:07:52.069 --> 00:07:57.199
And he started with the initial amount i.
00:07:57.199 --> 00:08:02.020
And Sn denote the total fortune after the
nth gamble.
00:08:02.020 --> 00:08:13.469
That means S0 is small i and S1 becomes if
he wins he is a total fortune after the nth
00:08:13.469 --> 00:08:16.949
first gamble that will be i +1.
00:08:16.949 --> 00:08:24.089
If he loses then his money would have been
i-1 that is the way S1, S2, S3 sample parts
00:08:24.089 --> 00:08:25.349
goes.
00:08:25.349 --> 00:08:33.980
The Gambler’s objective is to reach the
total fortune of rupees N, N is some number,
00:08:33.980 --> 00:08:42.540
some positive integer without first getting
ruined.
00:08:42.540 --> 00:08:52.000
That means you can make a state transition
diagram for this Markov chain the Sn is going
00:08:52.000 --> 00:08:55.820
to form a time homogenous discrete-time Markov
chain.
00:08:55.820 --> 00:09:01.231
Because of each games are independent and
with the probability p and with the probability
00:09:01.231 --> 00:09:10.960
1-p he wins or he loses therefore the Markov
property is going to be satisfied therefore
00:09:10.960 --> 00:09:16.220
this Stochastic process will form discrete-time
Markov chain.
00:09:16.220 --> 00:09:26.380
If you notice if he is land up 0 amount at
the nth game, then he is ruined.
00:09:26.380 --> 00:09:34.030
If he is getting a first time N rupees then
the game is over.
00:09:34.030 --> 00:09:35.390
That is objective.
00:09:35.390 --> 00:09:43.140
Therefore, this is a special case of random
walk one dimensional random walk in which
00:09:43.140 --> 00:09:51.460
the states 0 and N are going to form absorbing
barrier.
00:09:51.460 --> 00:09:56.320
Once the system goes to the state zero the
system is absorbed in the state zero.
00:09:56.320 --> 00:10:02.940
Once the system reaches the state N then the
system is absorbed in the state N. Therefore,
00:10:02.940 --> 00:10:11.310
the states 0 and N are absorbing states and
all other states – states are from 1 to
00:10:11.310 --> 00:10:14.650
N-1 are going to be the transient states.
00:10:14.650 --> 00:10:28.680
Therefore, this DTMC is a reducible DTMC with
transient states and two absorbing states.
00:10:28.680 --> 00:10:35.820
So this will fall under second type the one
we had discussed.
00:10:35.820 --> 00:10:40.510
Our interest with this model is, what is the
probability of absorption?
00:10:40.510 --> 00:10:46.430
What is the probability that he loses all
the money at the end of some game.
00:10:46.430 --> 00:10:55.400
Or what is the probability he reaches N that
is objective that is the probability of absorption.
00:10:55.400 --> 00:11:02.820
The other one is how much time he is in the
transient states on average.
00:11:02.820 --> 00:11:14.490
What is the meantime of absorption till he
reaches the observing states either 0 or N.
00:11:14.490 --> 00:11:22.660
So for that I am making the notation first
P suffix i that denotes the probability that
00:11:22.660 --> 00:11:32.430
the gambler wins when S0 is equal to i that
is i, i means initially i amount he has that
00:11:32.430 --> 00:11:33.870
is S0.
00:11:33.870 --> 00:11:36.650
So what is the probability that the gambler
wins?
00:11:36.650 --> 00:11:48.770
Clearly P0 is equal to 0 similarly Pn is equal
to 1 because no way if he is having initially
00:11:48.770 --> 00:11:52.680
0 amount he cannot win therefore that probability
is 0.
00:11:52.680 --> 00:12:00.770
If he is having initially the gambler has
the amount N amount at the time 0 itself.
00:12:00.770 --> 00:12:06.330
Then, he need not play at all therefore that
probability is going to be 1.
00:12:06.330 --> 00:12:11.250
Therefore, the probability the gambler wins
that probability is going to be 1 if he is
00:12:11.250 --> 00:12:15.480
having N amount initialy.
00:12:15.480 --> 00:12:23.280
For all i in between 1 to N-1 one you can
make recursive using the Chapman Kolmogorov
00:12:23.280 --> 00:12:30.430
equation that means the probability that the
gambler win with the i amount initially that
00:12:30.430 --> 00:12:46.100
is same as either he has initially i +1 amount
initially and with the probability p events.
00:12:46.100 --> 00:12:57.070
Or with the probability i -1 the gambler wins
multiplied by the probability q, q is the
00:12:57.070 --> 00:12:58.310
he loses.
00:12:58.310 --> 00:13:05.190
So these two combinations will give the probability
of Gambler’s win.
00:13:05.190 --> 00:13:11.340
You can do the simple calculation the way
we have Pi in terms of P(i+1) and P(i-1) you
00:13:11.340 --> 00:13:16.880
can write that P(i-1) also then you find out
the difference then you will get the recursive
00:13:16.880 --> 00:13:23.560
way and you will get in terms of P1 and everything
you will get it.
00:13:23.560 --> 00:13:30.410
So you can use the PN is equal to one using
that you will get all the Pi’s, you can
00:13:30.410 --> 00:13:39.260
use this relation P0 is equal to zero and
the capital PN is equal to one using this
00:13:39.260 --> 00:13:44.560
two values you find out the difference and
you make a recursive relation you will get
00:13:44.560 --> 00:13:46.530
a Pi.
00:13:46.530 --> 00:13:54.680
So whenever the p is less than q and p is
greater than q you will get and the Pi is
00:13:54.680 --> 00:13:57.740
1- q/p power i divided by 1- q/p power N.
00:13:57.740 --> 00:14:02.300
For p and q is equal to same.
00:14:02.300 --> 00:14:09.070
That means, it is of because q is 1-p, therefore
you will get the probability of gamblers win
00:14:09.070 --> 00:14:15.060
that will be i divided by N, that you can
get.
00:14:15.060 --> 00:14:19.140
And here the interest is what is the probability
that he is going to ruined.
00:14:19.140 --> 00:14:24.040
This is the probability that he is going to
win and the one minus of that of that is going
00:14:24.040 --> 00:14:30.380
to be the probability that he is going to
win in this game.
00:14:30.380 --> 00:14:34.830
The next one is our interest is Mean Number
of Games.
00:14:34.830 --> 00:14:39.920
Because the objective is that he has to reach
the N amount so the game is going to be over
00:14:39.920 --> 00:14:45.920
either he completely ruins or he is going
to get the N amount.
00:14:45.920 --> 00:14:51.520
Therefore, I am making here the random variable
M suffix i.
00:14:51.520 --> 00:15:00.100
So M suffix i is denote the number of-- sorry
mean number of games I am directly making
00:15:00.100 --> 00:15:05.510
random variable for the mean suffix i and
I know the relation for this.
00:15:05.510 --> 00:15:11.440
And here also I am making the similar relation
by solving that I get the Mi.
00:15:11.440 --> 00:15:18.450
So this is the mean number of games in the--
mean number of games played by the gambler
00:15:18.450 --> 00:15:25.130
until he goes to broke or wins completely
fortune N.
00:15:25.130 --> 00:15:29.990
So in this lecture I have discussed the Reducible
Markov Chain and types of Reducible Markov
00:15:29.990 --> 00:15:32.610
and some examples also.
00:15:32.610 --> 00:15:37.720
And finally I have given Gambler’s Ruin
problem.
00:15:37.720 --> 00:15:47.380
References are this.
00:15:47.380 --> 00:15:56.320
Thanks.