[MUSIC] So after two lectures of introductory material, we're finally going to compute something in this lecture. What are we going to compute, well, the steady-state probabilities of CTMC. How do we formalize the steady-state probabilities? Well, just as in the DTMC, in steady-state nothing changes any more, the mark of chain has reached its equilibrium. So one way to express the steady-state probabilities is to say that pi, the steady-state probability for state i, is equal to pi(t) where t is the time and we have a limit of time go to infinity. On the other hand, in steady-state, this vector p doesn't change any more. So we can also say that if we take again the limit of time to infinity, the derivative of the steady-state probabilities is 0. Now this leads to a system of linear equations. Namely we have to multiply this vector p with the Q matrix, equal it to 0, and, just as for DTMCs, you have a normalization equation. You need to sum all the entries of the p vector and they have to be 1, so that this is indeed a probability distribution. Now, let's do this, on an example, here you have the q matrix, and I'm going to do the computation for you. So I'm going to multiply the row vector p with each column of this generator matrix to obtain the system of linear equations. So this is -5p0 + 10p1 = 0, next column, 4p0- 10p1 + 4p2 = 0 and the last column is p0- 4p2 = 0, and of course you need the normalization equation. So p0 + p1 + p2 = 1. Yes, and now you have to solve the system of linear equations, and here I'm still giving you the same advice as I did for DTMCs. Pick one of the variables, express all others in terms of this one, this is what I do here for you, and then you can just add all of the expressions equal them to 1, from that you derive the value for p0. And once you have p0, you can insert that in these expressions for the other variables, and you get the complete steady-state distribution. Now, if you don't believe my computation skills, you can just check my result and you do that by summing up all the steady-state probability first step and you will see, well 4 divided by 7 plus 2 divided by 7 plus 1 divided by 7 is indeed 1. So, the question is, does this limit always exist? And yes, for finite CTMC, this limit always exists, so this is much easier in a sense than for DTMCs. However, you still have to look at the underlying graph structure. And what you have to do is you have to check the reachability between pairs of states, and you have to identify so-called bottom strongly connected components, BSCCs. What is a bottom strongly connected component? Well, let's first take a look at a strongly connected component, and in a strongly connected component, each state is reachable from each other's state. Now if this strongly connected component is also bottom strongly connected, it means you can never leave this component, once you enter it you are stuck in there. So in that sense, an absorbing state is a very simple bottom strongly connected component with just one state. So if you want to identify the bottom strongly connected components, you do not need to do that on the CTMC, you can also use the DTMC. It doesn't matter, you do not need the transition rates or the transition probabilities. Now the only notion you need is the one of irreducibility, and a CTMC is said to be irreducible if all states belong to a single bottom strongly connected component, right. So the whole CTMC is one strongly connected component, otherwise the CTMC is said to be reducible. And that is the only thing you need to check before you compute steady-state probabilities. So why's that, you might ask, because, don't we have to consider periodicity? Well, let me show you an example for that. So, unlike in DTMCs, for CTMCs we do not need to consider periodicity. Here we have a very simple Markov chain, two states, two transitions. Now, is this a CTMC or is it a DTMC? Well it is both, actually, because you can interpret the ones on the transitions as both probabilities or rates. So let's take a look at the transient behavior of this very simple Markov chain. Here you see, in blue, the transient behavior of this Markov chain interpreted over discrete time. And you see these spikes going up and down, and that is because this DTMC's periodic, so the limit does not exist. However if we interpret it as a CTMC and compute the transient behavior which you cannot do at the moment, but I did this for you. You see that the CTMC moves into equilibrium after say, time 1 or 2 approximately. So, for the CTMC, periodicity doesn't matter. The only thing is irreducibility, if you have an irreducible CTMC, it is very easy. You just compute the steady-state probabilities and they are independent of the starting state. So you can compute the unique solution of the linear system of equations. P times Q equals 0 and the normalization equation which states that the sum of all the probabilities is 1, and Q is the generator matrix of the CTMC as you've seen before. How do you do that, either you do it by hand, but of course for large Markov chains, this is not feasible. So there is many numerical methods which allow you to do that, iterative methods, such as Jacobi or Gauss-Seidel, which we are not going to discuss. Now, if the CTMC is reducible, then it is slightly more complicated to compute the steady-state distribution, because now it depends on the starting state s prime here. So, first thing you have to find all the bottom strongly connected components of the CTMC, and then we compute the steady-state probabilities of each bottom strongly connected component T. So I call them PT so that vector that has as many entries as the bottom strongly connected component has states. It's called T, so this is the steady state probability for a strongly connected component T. Then you need to compute something else, namely, the probability to reach this bottom strongly connected component, T from the starting state s prime. And then, you can combine the two, and that gives you the steady-state distribution, depending on starting state s. And that is for each entry, it is the probability to reach the bottom strongly connected component T from state s prime times the steady-state probability to be in state s, in that bottom strongly connected component T. And that is the case if s is indeed part of the bottom strongly connected component T. If you want to compute the steady-state probability for a state s, that is not in any bottom strongly connected component, the probability is simply 0. Why is that? Well, in the long run you will be stuck in one of the bottom strongly connected components. So the steady-state probability for such a transient state if you recall from the lecture on DTMCs, is just zero. [MUSIC]