I am to give one simple example for this type of reducible Markov chain with the transient
state and one or more absorption state.
I am making the assumption that is a positive recurrent, so instead of positive recurrent
I have a finite Markov chain so the finite Markov chain at least one state is a positive
recurrent therefore both are going to be an absorbing state therefore you do not want
those conditions.
So here in this model the states 0, 1, 2 are the transient states 3 and 4 are absorbing
states.
This is a easy example in which you can visualize someone who is doing the undergraduate with
the probability of, he is not able to complete undergraduate in the next step with the probability
of he is moving into the post-graduate in the next step.
So I am making a DTMC with the assumption the memory less property is satisfied and
so on.
From the post-graduate either someone gets the job1 with the probability one third or
not able to complete the post-graduate that probability is one third or he completes and
go to the PhD program one third.
From the PhD one fourth is not able to complete the PhD in the next step or with the probability
three fourth he is getting the job2.
Now you can visualize the questions, what is the probability that I observed into the
state job1 or job2 that is the probability of assumptions.
The next question, how much time on average I will be spending in the transient states
in the study before I get the job.
So this is the way you can visualize reducible Markov chain with this type.
So these two questions are going to be answered by finding the probability of absorption and
meantime up to absorption.
First let write the P matrix in the canonical form when all the sub matrix I made it in
the different colors so three and four are going to form a each one is going to be absorbing
states, so therefore A to A that is identity matrix; A to capital T that is a 0 matrix—sub
matrix then T to A that is again a matrix that is R; then T to T that is a Q matrix.
So what we need the Q matrix and the R matrix both are sub matrix capital P that is the
one step transition probability matrix.
So you find out what is I-Q, I is identify matrix of the same order I3 here -Q matrix
so you know the Q matrix is this so I-Q matrix find out the inverse that inverse is this
much so from this if you multiplied the vector e that is 1,1,1 we will get the meantime to
absorption.
And also you can find out the probability of absorption after finding the I- Q inverse
that is the fundamental matrix multiplied by the R in this matrix you will get the probability
of the absorption.
I am not giving here, the numerical calculation.
See the result, so this is the mean time upto the absorption and this is the probability
of absorption.
First, let us discuss the probability of absorption.
If the system starts from the state 0 state three is nothing but the job1 so with the
probability half you would have been observed into the job one with the probability half,
if the system starts from the state 0 from the undergraduate.
Similarly, with the job2 that probability is half, it is a probability mass function
either you will be in the job1 or job2 there is the probability of absorption.
If you would have started-- starting with the post-graduate then with the probability
half and half you may be in the job1 and 2.
Whereas, if you beginning with the PhD program not this two programs that is not possible
but still this is just example.
So if you start with the PhD program then definitely you will land up with the job2
with the probability one because there is no arc from two to one and land up the job
one therefore the probability of absorption into the job1 that probability is 0.
Just for illustration, therefore you can make out how the calculation goes.
So here the probability of absorption starting from the state two that probability is zero
to the job1 whereas job2 that probability is one.
So this is the probability distribution of probability of absorption starting from this
transient states.
Similarly, you can visualize the meantime up to the absorption.
These zeros can be discussed first.
So if the system starts from the state two what is the average number of steps the system
goes from the state two to zero then it goes to the absorption state.
That is not possible the system is going from two to zero, therefore the meantime is going
to be zero.
Because the minimum time is one or minimum number of steps system spending in the transient
states are one and so on therefore mean is zero here.
Similarly, the system is starting from the state two and land up one and from there it
goes to the absorption state that is also not possible therefore that mean is also zero
whereas all other values the greater than 0 that gives what is the average number of
steps the system is starting from these transient states and reaching these a transient before
absorbed into any one of the absorption states accordingly we have these values.
With this example I go to the next example that is a Reducible Markov Chain.
And this is a special case of random walk also.
Let me discuss, what is the example.
This is called the Gambler’s Ruin problem.
Let me define what is the Gambler’s Ruin problem.
Consider a gambler who starts with an initial fortune of Rs. i, i amount he has at the time
0.
And then on each gamble either wins Rs.1 or loses Rs.1 independent of the past with the
probabilities p and 1-p respectively so in this game there is no draw there is no type.
Either he wins or he loses.
Wins with one rupee loses one rupee and corresponding probabilities are p and 1-p.
And he started with the initial amount i.
And Sn denote the total fortune after the nth gamble.
That means S0 is small i and S1 becomes if he wins he is a total fortune after the nth
first gamble that will be i +1.
If he loses then his money would have been i-1 that is the way S1, S2, S3 sample parts
goes.
The Gambler’s objective is to reach the total fortune of rupees N, N is some number,
some positive integer without first getting ruined.
That means you can make a state transition diagram for this Markov chain the Sn is going
to form a time homogenous discrete-time Markov chain.
Because of each games are independent and with the probability p and with the probability
1-p he wins or he loses therefore the Markov property is going to be satisfied therefore
this Stochastic process will form discrete-time Markov chain.
If you notice if he is land up 0 amount at the nth game, then he is ruined.
If he is getting a first time N rupees then the game is over.
That is objective.
Therefore, this is a special case of random walk one dimensional random walk in which
the states 0 and N are going to form absorbing barrier.
Once the system goes to the state zero the system is absorbed in the state zero.
Once the system reaches the state N then the system is absorbed in the state N. Therefore,
the states 0 and N are absorbing states and all other states – states are from 1 to
N-1 are going to be the transient states.
Therefore, this DTMC is a reducible DTMC with transient states and two absorbing states.
So this will fall under second type the one we had discussed.
Our interest with this model is, what is the probability of absorption?
What is the probability that he loses all the money at the end of some game.
Or what is the probability he reaches N that is objective that is the probability of absorption.
The other one is how much time he is in the transient states on average.
What is the meantime of absorption till he reaches the observing states either 0 or N.
So for that I am making the notation first P suffix i that denotes the probability that
the gambler wins when S0 is equal to i that is i, i means initially i amount he has that
is S0.
So what is the probability that the gambler wins?
Clearly P0 is equal to 0 similarly Pn is equal to 1 because no way if he is having initially
0 amount he cannot win therefore that probability is 0.
If he is having initially the gambler has the amount N amount at the time 0 itself.
Then, he need not play at all therefore that probability is going to be 1.
Therefore, the probability the gambler wins that probability is going to be 1 if he is
having N amount initialy.
For all i in between 1 to N-1 one you can make recursive using the Chapman Kolmogorov
equation that means the probability that the gambler win with the i amount initially that
is same as either he has initially i +1 amount initially and with the probability p events.
Or with the probability i -1 the gambler wins multiplied by the probability q, q is the
he loses.
So these two combinations will give the probability of Gambler’s win.
You can do the simple calculation the way we have Pi in terms of P(i+1) and P(i-1) you
can write that P(i-1) also then you find out the difference then you will get the recursive
way and you will get in terms of P1 and everything you will get it.
So you can use the PN is equal to one using that you will get all the Pi’s, you can
use this relation P0 is equal to zero and the capital PN is equal to one using this
two values you find out the difference and you make a recursive relation you will get
a Pi.
So whenever the p is less than q and p is greater than q you will get and the Pi is
1- q/p power i divided by 1- q/p power N.
For p and q is equal to same.
That means, it is of because q is 1-p, therefore you will get the probability of gamblers win
that will be i divided by N, that you can get.
And here the interest is what is the probability that he is going to ruined.
This is the probability that he is going to win and the one minus of that of that is going
to be the probability that he is going to win in this game.
The next one is our interest is Mean Number of Games.
Because the objective is that he has to reach the N amount so the game is going to be over
either he completely ruins or he is going to get the N amount.
Therefore, I am making here the random variable M suffix i.
So M suffix i is denote the number of-- sorry mean number of games I am directly making
random variable for the mean suffix i and I know the relation for this.
And here also I am making the similar relation by solving that I get the Mi.
So this is the mean number of games in the-- mean number of games played by the gambler
until he goes to broke or wins completely fortune N.
So in this lecture I have discussed the Reducible Markov Chain and types of Reducible Markov
and some examples also.
And finally I have given Gambler’s Ruin problem.
References are this.
Thanks.