Mod-01 Lec-10 Markov Chain

In general, what is a Markov chain? So, we said a Markov process is a stochastic process So, what is a Markov chain? It is basically a Markov process with the discrete set of states. So, when you have a discrete set of states, so number of customer that is a discrete set countably in in finite, but countably infinite. So, that is what is called as a Markov chain technically. So, this is on the state space right; state space has to be discrete for something to be called a Markov chain, but your time can be continuous or discrete So, we have two options, discrete time Markov chain or you can have continuous time. By time, again I generally mean the parameter, discrete parameter or continuous speed parameter, I flip my definition CTMC So far, we looked at these two classes, and see how we can given a system that can be expressed as a DTMC or a CTMC, what kind of properties, what kind of performance evaluation properties can be derived from the system; that is where, we are trying to evolve towards So, as a simple example of the discrete time Markov chain system right, so if I am measuring let say q right of a system at every time instance a, t is some 1 micro second So, every micro second that is micro second, we measure the number of customer’s right in the system So, therefore, at time 0 right how do we do this, wait a minute. So, now here we look this is going to represent the states of system as such then, we start talking about probabilities of the system right. So, this is the state space right And then given that, I am in state 0 at whatever time right, this is now time is setoff now what is the probability that will go to state 1? What the probability I will have one customer at the next time instance? I am only looking at every time instant I am sorry Number of customer is a parameter. Now, I am trying to represent the system using this Markov chain, where I start talking about probabilities now. What is the probability of going from 0 to 1 right? Given that, I was in state 0 at whatever point in time, what is the probability I will go to state 1, I could also directly go to state 2 right If I started off with no customers and in 1 micro seconds, 2 customers arrived then I have probably have right I will be going to systems with state 2 customers in the system right. So, like this you will start representing a Markov chain in terms of these transition probabilities So, from 1 I could go to 0 right, from 1 I could go to 2, from 1 I could go to 3 and so on, and so forth. And you can also have self-loops in system itself with some you know non-zero probability will continue to stay in the system and so on You might have no customers arriving No no from I am currently in the system let us say your sometime instant t naught you have 0 customer; then your next instant is 1 micro second later you are looking at the state of the system at that time Yeah yeah So, every time instant I am looking at the

probability of shifting from one state to different state. So, here I am so the system state is measured at every time at every micro second. So, it is possible that no packets arrived in 1 micro second; therefore, stay back in arrival. So, in each of the state, if no packet arrives I would stay in the same state or if there is a packet completion then, I will go from this 1 state to 0 states. If there was 1 customer in the system and then the customer has been serviced in is departed then we got back you go to state 0 and likewise in each of these cases you will have those right reverse ok So, now we start talking about the so called rate state transition probabilities. So, we now need to define from right what is a probability of going from state i to state j right in certain number of steps will get to that This is essentially your state So, let us first prepare this discrete time, DTMC for some definitions of derivations So, the parameter space we are denoting as discrete parameter . Again whole series of definition they are going to start cropping up. So, let p j of n be the probability that at time instant n, I was in state j So, the system starts in time 0 and some states we do not know what that is right. As the system evolves, there is a definition of that time n that should be in this particular state in some given probability. And then let p j k we are interested in starting in one state and then looking at how many like n steps later, what state I will be in right? What is the probability of being in some particular state? The previous diagram that I showed, I am talking of what is called single step right 1 step transition. What is the probability that I am in state n, I will go to n plus 1 and n plus 2 and so on But now I am looking at series of steps right I can go through several steps before I go from one state to some other state right; so that we will just define here. So, what is the probability that, given that I started state in j at time m, then at time n where this relation should goes right, so for some value m lager than n. So, at stay time m I was in state j, then for n greater than equal to m, what is the probability that I am in state k? This is the conditional theorem Yes, they can be intermediate transmission That is why your they can be other transition also, there can be yeah yeah. So, it is not n equal to n plus 1 right sorry n n is greater than or equal to m; so, m m plus 1, m plus 2 and so on Yes. So, here dimension is step so how many Discrete can be state j for move then one time Yes it can it can yeah. That is why m can equal or yeah k can equal j right. It can stay in the same state for several time instances before it goes some other instances states So, as an example, if we look at the number of customers at time 4 right let us say there is 1 customer in the system and that customer

being serviced by the server. Then for the next five instances, if no other customer comes, then my state is always going to be in the same right is always in the state with with number of customer equals 1; therefore, there is no change of state. So, again this is just a definition this is the conditional probability that given a time in state j So, this p m p j k somehow is defined to be this one right This p j k on the (m, n) is the called the transition probability function Yes you can that is that will come up later on with this c k equation it will come up So, we will , so 0 eth step transition probability So, what is the probability of going from state j to state k in 0 steps that is again just for base line definition right. So, if j equals k then it is 1 right 0 otherwise probability enough self-evident, but we will just do that for notational convenient we will need this later on right So, basically I can go from one state to another state in 0 steps, only if you are in the same states only if both j and k are the same states, otherwise it is 0 probabilities. Then normally we can determine the 1 step transition probability So, given a system my 1 step transition probability is defined as follows So, this 1 step is whatever instant of time I am looking at there is probability that I am given at time instant n minus 1 and I was in state j, and the next time instant I will be some other state k; and what is the probability of that? This is the given right this somehow has to be determined. So, we will see how we can use this. Now, let us look at one example, so for just equation have been coming yeah So, in the condition probability function that you are given same discusses suppose the multiple paths from one states to another that is possible each having there their individual probabilities. So, will this be a cumulative of the other possibilities? Yes it will be yeah. If you are going to transition to multiple path, it will be yeah That if you want so from i to j we can go through several intermediate nodes right with m steps and n steps. So, then this is this the way we will define that right. You look at the summation of all those probabilities right that will be a total So, the total probability going from i to j (m plus n) steps will depend up on how whichever way you break that. So, m and n can be whatever combination, if it is 3 it can be 1 plus 2 or 2 plus 1 and so on right But in that case if we consider special case, where say g equals to k we return to the same state it means in same state Yes It is possible that it might take the path and return to the same state in that? Yes you can yes So, it might also take that path multiple

times over? Yes. So, you are talking of starting in a state and then going to several sequences and coming back to same state, yes that is also possible that is that will be Is it possible that path repeated multiple times, we cannot capture that information? Yes yes that their is possible But that is possible to go from one state to come back to the same state after several other transitions. So, what do you mean that, the state that is not capture? So, I am saying is, suppose it is moving from i to j to the state k we take two different time instances, it goes form i to k and k to j and this transition i k and j happens multiple times over. So, will that not affect the probability? It needs certain time duration, suppose m and n has multiple like such transition present in the Number of steps will vary Number of steps varies For a given, so the probability you are saying does not depend upon, no the probability will not depend upon the number of steps; you are only trying to see, if I am starting in state i, what I will come back to state i in whatever k steps right. That is what this is trying to tell you Number of steps will vary in case that he is finding out number of steps will vary Right see one thing I am trying to list is the actual sequence of possibilities and other thing I trying to look at the probabilities right. So, the two the probability is trying to capture what is overall probability that I have; you are looking at specific instance if you have, run the simulation then yes you will find that there are several ways in which this can happen right. This is simply looking at the probability of going from one state to another not the number of ways in which you can go from one to the other or number of instances that such sequences occurring Because at each, if you are running this as the simulation right; you will randomly toss the coin and then it will probably go to one of those case states and yes you might come back in different points in time. But quite looking at is a long term steady state probability that I will come back to same state right that is what I want to find out So, if I write to have say 1000 seconds of monitoring the system and that you find that in five instances, I started from i and actually came back to state i right. So, I started in state i and I ran through several sequence of this right time instance then you keep on monitoring. Each of them you will be giving you different flow of states right; you will have different state transition each of this simulations And the probability tells you that, what is the rate with some finite probability I will come back to the same state or not right that is what right. Others did not follow that even around right, but anyway increase steps So, it is the one probability or even calculate in first step went to 0 to 1 then 1 to 2 then 2 to 2 then 3 to 4 cumulative probability ending all those No, I did not get What happens is, probability i to j and steps Yeah or m plus 1 step ok in this case I took steps So, i to j is going to take some path, directly also we can take some paths also Yes. So, this i p k will be against split into, it would finally expressed as sequence of 1 step transition cumulative Yeah it will be cumulative, because all this singles fives only you know the 1 step transition; from this we have to start building that second which is word I am trying to get to, but have not got to that it. So, I am so with this 1 step transition, I can actually figure out the probability of the 2 step, 3 step and so on; from which I can essentially compute from any state to any state, if you want to do that x number x plus y steps I can compute So, if now what I am trying to get is let me give this examples. Say, I have a two state system right this is a state of channel it see there good or bad ; and if is in state 0 right it will stay in that same state probability 0.5 and then leave it with probability 0.5 and like wise. So, this is this is an example of such a system ok So, if I measure the system, I found this right. Now, the question is so what? So, you are representing this system behavior with this Markov chain. Now, he would like to derive some properties of the system using this representation right. So, the first question is, in the long term right this is one time instant, at one time instant I go from this to the other In the long term, what is the probability that system will stay in state 0 or the probability system will stay in state 1? That is something that you want to calculate right big for what

whatever reason; I will leaves this later on for computing the average number of customers in the system or for computing some other matrix or I could be having some sort of revert function for each state right r of 5 for state 0, r of r 0 for state 0 1 and so on. And you want to compute compute them expected reward of this system as its progressing through this right So, this is procedure from this. Now, I need to find out in the steady state in the long run right what is the probability that system will be in state 0, it will be state 1, and how do we compute that? Now, just assume that everything is known with that the index is simply 1 2 3 4 and so on right. So, in the 1 step transition I know; that is what this problem. This is the 1 step transition right You are say probability that x n equal to i equal to probability of x n minus 1 equal to j I mean sigma over j probability x n minus 1 equal to j into probability of x n like giving that x n minus 1 equal to j Minus 1 equal to j we can will be equal to x n equal to j, because n is large. Then we get the So, to get to that what we will do is. So, now we will represent this state 1 step probability matrix. So, we will call this as p, again p is appearing in several different, this is 1 step transition matrix. So, instead of trying to do that, we can use this matrix itself right to do some of our computation So, for I am, so what is the probability going from state 0 to state 0 or basically staying there and so on right I can represent this as my matrix. Remember that, the state is can be infinity t0o just that it is right it is discrete So, therefore, it essentially extent all the way here, if it is finite set if it is finite set of states then you can do some easier computation. It is infinite set, we cannot do this computation So, it is fine actually. But, if you look at a queuing system that will be an infinite system; because, number of customers could be infinite in the case of M M 1 queue, only if M M 1 B it will be finite. So, then I will use this term. So, p i j (n) is the probability of going from where step by mean time interval or n time right. This system is moving on a every time interval from one state to another state depending on the probability that the 1 step probability distribution the transition that we have seen And if I denote p of (n) to be basically this matrix; so, p of (n) is the probability this as transition probability matrix of going from state i to state j in n steps. This is probability of right this is this, so this is going in 1 step right, this represents going in n steps . As n approaches infinity, then we finally approach so called if you have you can derive, if the system that have a steady state distribution then you will find out that the probability of going from right state i to state j in n step is this much. And that will help us finally derive out so called final probability that will come to just a second So, this p of (n) is nothing but, your p raise to the n times. This is your right matrix p multiplied or raise to the power right . So, will see how do we use this in just a second

right. So, your for that example that we saw p was this right 0.5, 0.5, 0.3 and then 0.7 This is the 1 state transition 1 step transition probability right So, what is p squared then? I am sorry now going from 1 to 0 is 0.3 in that example right read it. I read it the other way around you know, now yeah. So, there is that 0.4 0.6 I think you are using my incorrect matrix; correct matrix is 0.4, 0.6 is correct or not correct 0.6, 0.4 This is the value I have, but because matrix is wrong 0.6, 0.4 Now, I just derive it then correct it yeah, so then you are calculating I changed Now, let us repeat the values again. So, it is p squared. So, this is this so called right the probability of going from one state to another too. So, this is basically to go from state 0 to state 0 into 2 steps is 0.6 right and then so on This is the meaning of this one. So, if I let this p 0 are the initial state or initial probability vector. So, the initial probability vector let say that you are going to start the system with right being in state 0 probability of either 1 right. So, for example, let say that I am always starting the system in a good state as you are state 0 right I will never start in state 1 I always start in state 0. That is my initial probability vector p of 0 or it could be something more generic that I never know right it is like when you wake up in the morning if you are good mood or bad mood we never know right. So, 50 50 it is not always you wake up in a good mood So, this is your initial state in the system right So, this could be some other distribution also. This is again based on right measuring the system, estimating the system behavior function measurements. So, want to you some initial vector is known that is starting point

for your system; then as system progresses after while then what is my after n steps, what is the probability that will be in in state 0? And what is probability will state 1? That is your p of n right. So, that is nothing but, p 0 times p n. So, that is where this it slowly coming towards this much of steady state right. I am just trying to establish, why we need to compute this, this is one way of doing it right So, I start to the original as 1 step transition then, I can keep on computing this p of (n) until I am board and or until you converge So, there are some systems for which we can where some non-properties are there, where this finally this p of n will simply converge to the value it is the independent of you are n, the starting value right. Independent of the number of steps as well as you are independent of initial vector, you will finally converge to a steady state, which will tell you that after thousand iterations you are always be in state 0 with probability x and state 1 with the probability y. That is what we want to find out. What is the steady state probability of the system right you start of in this case at towards the end, what is that you will end up I am sorry This is the square matrix you have n states this is the finite matrix, your transition probabilities from every state how do you go to every other state You have a system like this, in that case you will not you have system like this right If you start in state 0 or stuck in state 0 yeah. In this case there is no communication at these two, these almost like two independent systems; in this case, yes you cannot. Say, you will if depending on various start you struck in this state. So, depends upon you are, so the I am saying it is not true for all kind of system right, where there are some properties defined you will you can derive this transition probabilities In this case, we can state that these transition probabilities are 0, so that will give us square matrix 0 to 1 and 1 to 0 Yeah you will you will get a state like this right. But, you will always being you are how many whatever you multiplied always been 1 0 right this will be your identity matrix So, if you keep multiply this entire you always have I; finally, whatever state you start with you are struck with that state. If you are state is initially 1 and 0 then going to be in that state forever. So, that is also technical, but this is right this not like this a not an irreducible matrix or Markov chain ok So, you just started again scratch the surface of this Markov chain business that is continuing with over DTMC discussion. So, this is as we talk before set up this state space discreet could be infinite, but still discreet and time is also discreet. So, move along in terms of time steps then whatever the time step is whatever unique we want to, but its processes moves along from one state another in sequence of different time steps ok So, have to completely specify discreet time Markov chain, one is we need the 1 step probabilities right 1 step. So, this is 1 step probability transition probability matrix which is your p. So, if we recollect this also our matrix that we had last time; and to know the current state of a system after some sequent of some n steps right we need to also specify the initial matrix or the initial probability So, this is p 0. So, this is a vector that specifies the initial state of the system So, if there are n states right, they use n differently. If there are total of say k states then, you specify what is probably system will starts with in state 0 with some probability right; and state this is the initial set of probability that you have So, for example, right we said that the system some funny business going on here I could set my p (0). This simply states that, in

the two state Markov that Markov process that we saw last class rights. So, the p below states here this is your transition matrix of going from one state to other and then initial state could be anything that is dependent on the system, it could be simply always starting in state 1 or state 0 and so on So, these two essentially start the, or specify the initial state of the system. Then as your system progress with time then the state of the system also changes right. So, there are some cases for which we can actually end up with steady state probabilities, where regard after some 8, 10 iterations or 10 steps or 100 steps and so on. The system ends up in some steady state that tells you the probability of being in state 0 is x, state 1 is y and so on right. So, there are some cases where we can actually derive that and it exists So, will try to talk little bit about that So, this is the expression that we saw last class right. The probability distribution of the states at time step n is simply raising that matrix p to the power n right. So, p squared was we did this last time and other was 0.56, 0.44 ok. So, one way to find out the steady state probability, steady state is as in a process infinity right all this probabilities will converge to some common value right it was single value. So, you just use that yeah So, let us define this it is actually called the visiting probability V j is the limit in probability of p j (n) as n approaches infinity. So, this what we want to figure out right; for a given Markov chain thus such you know such a set of limited limiting state probability exists and if so, what is it? For some particular type of Markov chains this exists we will define that way So, one way to find this V j, so will let V right will use this. So, V is the vectors that are present these limiting state probabilities So, to calculate this V, one way is to simply keep on multiplying this matrix p by itself until you find that some point it converges right. So, that is we look at the example we did last time right. So, if you you can just write a small program to do the matrix multiplication or use MATLAB whatever it is, after 5 or 6 iterations or 5 or 6 steps this will simply converge right So, for the above example, the steady state probability right does exist and V becomes,

the probability being in state 0 is 7 by 12 steady state and state 1 is 5 by 12. And the tutorial I ask and we guess we thought a little simply end up in state 0, because the high probability of going back to stage 0, but this not the case. This we can actually generalize this also for a given setup systems So, this we can write, so after 5 or 6 steps right regardless of the initial state of the system; this is what will end up with, we can also verify right. So, you have p of it or you say infinity . So, ultimately this is what we want, we want to know the probability of the system being in a given state right as steady as in the in the steady state situation, quick questions ok In this V row will be the same sir? Yeah. So, that means whatever state we start with, you will ending there is a row the probability of going the one of those other state right along row is the same. So, we start in state 0, the probability of going to state 0 1 2 3 will be the same. So, what are the initial states is starting with, will end up with the same, that is that is what it is So, all the rows will be similar Similar yes that again. So, now we look at there is lot of definitions with I think as simply I have to skip slightly behind. There is notion of transient state, the recurrence state and irreducible and so on. So, I just want to specify the main thing all right So, this under some conditions I kept saying right, this will we can have the steady state vector. So, for an irreducible, a periodic Markov chain with all the states Recurrent non null sorry non null I am I am not define what recurrent is, what non null is, but I just leave it that for now I need to move ahead. So, for the special set of Markov chains, this limiting probability vector right V which is nothing but, the steady state probability of being in state V 0 or state 0 and so on right is unique So, this vector will satisfy the following condition right. So, your V is equal to V p. So, one way of arriving at the steady state probably repeatedly multiplying the power raising p to the power to large numbers; and other way of looking at this, if I start in some state this steady state V; and I have one more transition right which is what is represent V into p right this right side simply represents the current side is the system is already in the steady state. The probability of that is denoted by this V of being in each of those states I have one more transition p will end up being back in the same state right that the same probability of the states will be the same The probably distribution of being the different state just not change even after one additional transition. That is what this steady state means right. I start with the, I go through one more transition and the distribution of

the probably different states, they still unchanged; that is what V equals V p s So, this is in other way of actually determining our where vector V. So, given p I can find out the steady state probability we are simply having this V equals V p. So, we saw one case where simply right rising to powers of n; this is in other way of getting out steady state probabilities right. And there are some other conditions also, this is V equals V p as well as, all V j should be greater than equal to 0 with all this this sigma V j should equal to 1 Because, otherwise V equals V p can be satisfied by all V is equal to 0 right as a trivial solution with does which do not care about So, this V j should sum up to 1, otherwise 0 will also satisfy all 0’s will satisfy V equals V p right, 0 equal 0; so their is no regardless of p we will end up with right Which one? No, that is equals to 1, if V j equals 0, then the this condition would not be satisfied like Yeah otherwise that this should be equal to that theirs non-zero probability of being in each of those states. That is solution that we want to we simply solve V equals V p; as one solution will be simply V j equals 0. But, to get to unique solution and this we have to satisfy this condition too ok So, now let us go back to our previous example that we saw right. So, if I were to solve, so so my p was and V equal V 0 V 1 right. So, from our equation we simply have to solve for this. So, you will have a set of linear equations to solve So, technically V equals V p, but I preferred write as V p equals V, because the equations will come out looking better then we start So, that is the, so to find out the steady state, this is what we would have to solve So, what does this equation work out to? It some of you already worked out on the board last time. So, you just see if I can squeeze this here. So, 0.5 anywhere make a mistake right. So, that is your set of equations And this we can now solve which I do not have to go to we can pick any of those equations to solve. So, this will end up giving you So, for given any as long as your matrix is finite right you can end up with these make sense. Now, there are some cases where this would not hold we would not able to right

get to the steady state probabilities So, the couple of right, for example look at this system here right. So, in other words if you start in state 0, you stay in state 0 forever; if you start in state 1, you will stay in the same state forever right there is no transition between the states. So, this is an example of that is not reducible. Irreducible simply means that you have a set of states from which one side you can reach any other state in a finite number of steps right. In periodic again skip the definition for now So, in this case, you once depending on here p of 0 right whatever that is; so, if you going to be if you starting in that state, that is the state always be right, if you start at 0 or 1 you are struck with that state You can also have another example, where we start with state 0, but it is right and if you ever from the probability 1 will go from state 1 to state 0 right this is also an example of system ok So, this is here 0 is an observe, observing state right. So, in the long run the probability of being in state 0 is simply 1, you will never go to state 1. And these are also valid system’s right. These could be for example, life time right some decay is there, decreasing life time some point have to come back to this state 0 after for whatever reason right I am sorry they both of them steady state yeah the second one as steady state yes yeah yeah only think it is from 0 we are not able to so yeah So, this does not satisfy the irreducible thing, because it should be able to go from one state to all other sate. In this case, once you go to 0 each an observing state So, I am not saying that you will not have steady state; for these cases you carry or guarantied a steady state right, but do not saying anything about the other thing. Then in this case steady state is 1 0 So, if you look at the matrix itself identify your steady state matrix right , additional steady state where the rows are the same right, whereas here is the identity matrix; so, simply 1 0 1 0. So, whatever you start with you struck with that right So, you rise these n times you will end up with simply identity matrix. So, whatever your p 0 is will be your p of n. And in this case, whatever be your p of 0 you will end up with 1 0; this is simply multiplying each row by the first column which is all 1. So, you will end up with 1 always. So, these are two special cases which do not fit with this definition that we saw earlier . We will look at one more examples for DTMC’s, then we go on towards CTMC’s yeah; we look at two examples, we have to go to this one So, now we are looking at, so we just saw the toy example right with two states. And now, let us look at some more realistic couple of realistic examples right. So, one is where you have program that is only execution. So, this is typically an operating system. So, we know that in OS, you have CPU burst and IO burst right. So, let us say that there is process right So, thus 0 represent the state of the system when it is running on the CPU. So, process runs in the CPU for say 1 unit of time right; and then at the end of it that is the probability q 1 that it goes to devise 1 this these are

all I O queue’s right. So, we remember we saw this queuing right So, this is your, you go to on join end up with input output. It is assumes that, there is no queue as such simply devices alone, you simply gets serviced on the CPU for time unit are and then after that with some probability q i will go to one of the various. So, let us say we have total of m devices and then at the end of the getting serviced you will simply come back to state 0. So, that is that is only transition Then there is a non-zero probability that it is the CPU will the the process of program will finish execution in a current burst in which case always assume that, there is one more process always waiting to be run on the system. So, there is not exactly multiprogramming, this still unique programming right. There is only one job at a time in the system, it gets the CPU then it goes to the one of the device queue’s gets serviced to the device then comes back to the CPU again In the mean time, when this devices getting when the process being serviced to the device queue there is no other process that is occupying the CPU. That is multiprogramming will come to the later, this is simply unique programming So, in case thus process finishes execution with the current CPU burst, then this indication that goes back to the state 0 simply mean there is some other process that is occupying CPU right. So, there is always a job queue there is ready that is waiting with some jobs that are allocated So, this will be generalized, because I am assuming that all service times are only 1 right; we will have to modify this to later on to have a system, where the service time is not unit is not simply 1 unit of time, it can be multiple units of time. And there is also no self queue as such right self queue is an I would have self-loops around each devices it means I spend several right amount of time that I staying in each state I can capture by self-loops; so, all that is taken out of the picture This is very simple process that we are looking right; get serviced for 1 unit at a device and go back to the CPU. So, now for this system one can try to find out right, what is the steady state probabilities and based on that you can find out they utilize section of the system right and so on So, if I look at my p matrix right. So, this is an m plus 1 by m plus 1 matrix right. So, the rows the entries for row 0 are simply q i’s right q naught to q m; and for the rest of the rows from every devices simply come back to the queue state 0, so it simply 1 0 0 0 So, with this representation if I ask you the question, what is the average number of times some particular device right i is used in the the system? Given the inputs are this q I’s that is pretty much it right. So, given q i, what is the probability system will be the CPU is going to be used in the system right. So, what is the probably being in state 0 will tell you the CPU utilization right, and the probability that you will be number of visits to a particular device will be dependant upon the visiting probability for a particular state So, that V i for the state is what you tell us, the probability that you will be in state 3 means you have been serviced device number 3 right. So, that is why we need to we need to define those V i’s to determine the probability the utilization of the system as well as the the probability of being serviced at a given device right. So, now we can simply solve this cycle goes back to Yeah there is no loop here I will could have know this queue, if the time spent is some other it is not unit it is not unit or some unit time then yes will have a more realistic system. So, this will little bit simplified system right, because we not moral the service time at the queue’s right at the device queue’s; that we will come to, when we go to closed queuing networks then will model queues then will model the waiting time of the queues and so on (Refer Slide Time: 1:00:00) So, now let us say that for example, right So, if m equals to we can solve this for the

general case to, but let us you look at a m equals 2 fairly straight forward this all this particular system it is not at all. So, your equation to solve is (No audio from 1:00:17 to 1:00:59) right (No audio from 1:01:01 to 1:01:29). Some one if you are used a program or software package for solving system of linear equations. Any of you used, any one who, what did you use? Package called java matrix Java matrix that actually LIM package LIM package that is LIM package is free right IBM, but even our MATLAB and mathematical should solve right. So, either you can do this by hand or you should you can look at some of those tools also right for doing that for you. And those are symbolic too right, so you can symbolically also you can get not just numerical value for also symbolic value also some some of these cases we can actually derive ok. So, to solve this it is fairly straight forward rights. Solve the the V 1’s are expressed in terms of V naught; all you are do this solve for V naught (Refer Slide Time: 01:02:37) So, that simply V naught q naught plus (1 minus V naught) equals V naught right. V 1 plus V 2 is equal to 1 minus V naught that is our last. So, many times we will find that third last equation convenient. So, anyway so we can now let write that, 1 over q naught and V j is simply (No audio from 1:03:05 to 1:03:20). So, therefore, now I express the probabilities of being in the different states simply in terms of this q naught So, if it asks you the question right, if q naught is say 0.4 then, q 1 this 0.5, q 2 equals 0.1 right; what is the CPU utilization? What is fraction of time the CPU is being utilized? (No audio from 1:03:45 to 1:04:02) So, what is the CPU utilization in this particular case? 1 over 1.6; so, that is 0.667 or 0.625 So, that is where your chain comes in handy So, you can now determine the CPU utilization with this very simple system, where the time spent in each of the states is just 1 And if I ask you the question what is the number of visits right number of times that device 1 was used in 100 seconds. So, what is that right? So, the number of times (No audio from 1:04:53 to 1:05:09), so that is

simply the visiting probability V 1 into t right. So, that is simply V 1 into 100; and what is that? (No audio from 1:05:23 to 1:05:35) V 1 is 6.25 there is another half there, it is 0.5 right its 0.5 or 6.25 V 1 is q j divided by q minus so q j is half; so, it will be half of this. So, it is 31.25, because V 1 is q naught into V naught or divided by sorry q naught into V naught yeah, if you remember the previous expression right. So, V 1 is q 1 into V naught right remember the previous. So, once you know, V naught simply plug in right and keep going, so 31 times So, this is what once one basic example of how these Markov chains come in handy in terms of performance evaluation right. That is why these steady state probabilities are computed