[MUSIC] So, before we are computing the steady state probabilities in this last last lecture of that module, we first have to take a look at two more concepts, mainly Irreducibility and periodicity. What does irreducibility mean? Well, a is irreducible if from each state we can reach each other state in a finite number of steps. That one is easy. Now what is the period d(s) of state s. If we want to compute the period for a state, we first need to find the greatest common divisor for all values step numbers n for which we have a positive probability to coming back to that state. Then if this greatest common divisor is greater than one, the state s is called periodic. And if this greatest common divisor equals one, the state is called aperiodic. Now if you want to formalize this, we have this equation, and it states, then it states S is periodic if exist such as greatest common division d. Which is greater than one, such that fo all N and mod d Is not equal to zero, it follows that PSSN is zero. So there's a zero probability to returning to that state as in N time steps. In a DTMC, that is good to know that all states in the same component have the same period. So what does a component? A component is a part of the DTMC that is irreducible basically. All states in that component are reachable from each other. And that also means if the complete DTMC is irreducible, all states in that DTMC are either periodic with the same period or they are all aperiodic. Now, let's take a look at a simple example. We have DTMC with four states and we want to check whether it is irreducible or not. Well, this DTMC clearly is irreducible, because you can reach each state from each other state. Now, what about the periodicity? For that We have to pick one state, I picked state 0. And we have to check with how many steps you can come back to that state, so you can come back in. In one, two, three steps or in one, two, three, four, five, six steps. So three, six, nine, and you immediately see that the greatest common divisor of all these step numbers is three. So we can state that this DTMC is periodic with DS3 we have stated that it is irreducible and now I want to take the opportunity and also. See whether you can remember the concepts from last lecture, so are these states transient or recurrent? What do you think? Well they're recurrent because they are all in the same component, and there is a zero probability to leave this component. What you see is also that in a finite DTMC the concept of irreducability and recurrence, actually talks about similar things. Only in infinite DTMCs you really have to distinguish the two. Now, what about the long run behavior of this DTMC? We need a starting state which is state 0, in this case. Now let me write down the first transient distributions for, time point zero, this is one, zero, zero, zero. For the next time point, one, this is zero, one third, two third, zero. One more, we have zero, zero 0, 1, and then in the next one, we have 1, 0, 0, 0, which you've seen before. So what you see is that the limiting behavior here doesn't exist, but What you do see if you take a look at the first six distributions is a pattern. Namely, for all step numbers that are multiples of i, you have the same vector, 1,0,0,0 for all step numbers that are multiples of 3 plus 1 you have 0, one-third, two-third zero. And for all step numbers that are multiples of 3 + 2 you have 0, 0, 0, 1. And this clearly is because the is periodic with period three. Now, let me play around with this DGMC a bit and I want to add a self-loop. And that is this transition which leaves state 3 and goes back to state 3 with probability one-half. Now, if you take a look at this, and you want to compute the period of that DTMC, you see that for the first two step numbers, one and two,. You have a probability zero of returning but for all step numbers that are at least three, you have a positive probability of returning. Why is that? Well that is because you can idle in that self loop as long as you want. So for example we do one, two, three, four or we do one, two, three, four, five and the same for all larger step numbers. Clearly, the greatest common divisor of these step numbers, is one, which turns this DTMC into an aperiodic DTMC, for which we can derive the limiting distribution. I've already hinted at this concept of components and that mutually reachable states that are in one component have the same type. This not only holds for reachability, but it also holds for. Transient, recurrent, positive and nonrecurrent as well as periodicity. So, if you have identified a component of mutually reachable state, it is enough to only consider the characteristics of one of these states. Now finally, we can move towards a Stationary distribution. We define the P vector, as the stationary distribution of DTMC with matrix P, such that Pi equals pi times p. That is a matrix vector notation. You can also write this down per state. And then we have pi s is the stationary probability for state s. Equals the sum of the complete state space of pi s prime times the probability to move from s prime to s. We can also say this in yet another way, and that is that the probability flow Out of a certain state has to equal the probability flow into that state. So, this is for ps, ps times one minus pss. That's the probability to leave that state. Equals sum over All states from the state space, P(s prime) times P(s prime, s), the probability to move from s prime to s. So there are different ways to express the same thing. And now we come to the main theorem of this Lecture in and irreducible, aperiodic and positive recurrent DTMC, the limiting distribution v exist. Also, this limiting distribution has been independent of the initial probability distribution. So you do not need to consider this. And, v is equal to the unique stationary, or steady-state, probability distribution. Now you've seen in this lecture that we've talked about the limiting distribution, which only exists if the DTMC is a periodic and we have the stationary or steady-state distribution. Which may also exist if the DTMC is aperiodic but I'll tell you how this works on this slide. So if we have a DTMC that is irreducible and positive recurrent but not necessarily a periodic, we still have a unique stationary distribution and that is defined as Pi s equals 1 divided by ms. Now what is ms, you've seen that before. And it is the mean number of steps between two successive visits to that state s. So this is nice because it gives you a way to reason about the long run, the average behavior even though the DTMC might be Periodic and with that the limiting distribution does not exist. So this wraps up my lecture on the study site distributions and on DTMCs in general and I hope to see you back. For the next module where we start to do model checking for DTMCs. [SOUND]
