[MUSIC] In the previous lecture, you've seen how to use the rate matrix to specify the transition behavior of a CTMC. This lecture will introduce the so-called Generator Matrix which we need just for convenience. It makes things easier to compute. First, let's take a look at the behavior of the CTMC. The probability to leave a non-absorbing state in the time interval from 0 to t, is given by the probability distribution, the exponential probability distribution, which you've seen in the last lecture. It is 1 minus e to he power of minus E(s) times t. And recall capital E(s) is the exit rate. It gives you the sum of all the rates that bring you out of state s. So this is the probability to leave a state which is non-absorbing. Now, if the time interval is very small, we can make things a little easier, and we can instead write E(s) times t, but that only works for really small t. Now, on the other hand, what is the probability to move from a non-absorbing state s, to another state s prime, in the time interval 0, t? You see the difference, right? First, in the upper line, I want to have the probability to just leave the state. I don't care where I go. And now I want to have the probability to go to a state s prime, specifically. So I have to take into account the rates that bring me to that state s prime. And this is what is written here. So, this part is the same as above. It is the probability to just leave the state in the time interval and then I multiply with this expression, R(s,s') gives me the rate to go from s to s', divided by the exit rate. So that is basically the probability to go from s to s prime. Now, this discusses the Generator Matrix. It is also called infinitesimal generator matrix. You don't need to remember that. Q is capital R minus on the diagonal the exit rates. Let me show you an example. This is a very simple CTMC, two states. Let's see whether I can write down the Q matrix for this. So from 0 to 1, I go with lambda and from 1 to 0, I go with mu. Leaves two entries, and this is where I have to subtract the exit rate on the diagonal. In this case it's very easy. Even I can do that on the fly. So minus lambda and minus mu. Let's see whether this is, correct. Yeah, I did it. So this is how we build the generator matrix. This is the formalization, the generator matrix Qij, contains in every entry either lambda i times Pij, that is for all i that does not equal j and for all i that equal j, that is those entries on the diagonal. We have minus lambda i. So now you might think that you always have to reconstruct this lambda i or you don't because you can do it a bit easier and just write on the diagonal the negative row sum of all the entries for which i is not equal to j. Coming back to the behavior over time, so for small time h and i does not equal j, I can write down the probability to b interstate j at time t plus h. I recall x is a random variable that we're looking at. Given that, the random variable was instead i at time t. And this is the same as qij, times h, h is the time I give my CTMC to move. And now here comes the problem or the challenge with real time. You don't have this time steps that makes computations and DTMCs so easy. So here you have to add o(h) and o(h) is the probability to move from i to j, in more than one step. Yeah, that's the problem in real time, you don't know how many steps you'll do in a certain time, but the good news is, If I take this h very small, then, o(h), will go to 0. So if I take the limits of h to 0, o(h) divided by h will go to 0. Let's take a look at a slightly more difficult example, now we have three states. We have a system that can be idle, busy or asleep. And this is now modeled as a DTMCs as you can see on the probabilities on the transitions. Now, I want to make a CTMC out of this and I have to specify a random variable for every state. So I have to add an exponential variable to each state and this is the rates I'm going to use, so first state 0, I add a random variable with rate 5, state 1 gets a 10, and state 2 gets a 4. Just for future reference, larger here means faster. So if you get a larger rate, it means you will leave the state more quickly. So let's make a CTMC out of this. That's kind of easy. You multiply the probabilities on the transitions with the rate that goes with the exponential random variable per state. So for state 0 it is 5. And this is what I did, I multiplied 0.8 with 5, gives me a 4. And I multiply 0.2 with 5 and that gives me a 1. And then similarly I do the same thing for the two other states. Now for this CTMC, I can again write down the generator matrix, so I move to state 1 with rate 4. I move to state 2 with rate 1. And now the diagonal entry is the negative row sum, so minus 5. Next row means next state from 1 to 0 with 10 and from 1 to 2 with 4 and the negative row sum here is minus 14. Last state, 2 2 1 is 4, and that is the only transition so this is a 0 and this is minus 4. Let me clean this up for you. Yes. Now, I can also go the other way around. I can start with the CTMC and compute the so called embedded DTMC and let me show you how this is done. So this is the formula you have to use, P, s, s prime is the entry in the probability matrix of the embedded DTMC is given by, well, the, Right matrix, so the right from s to s prime divided by the exit rate of state s. And this you do if the exit rate is greater than 0. Means if the state is not absorbing. And otherwise, it's just a 0. So lest's do this. On a DTMC with 6 states, of course the sorry, on a CTMC with 6 states. Of course the embedded DTMC that we want to derive also has 6 states, the exact same structure, now we only have to derive the probabilities. So, let me start with this state 0, I have to come up with the exit rate, 21 plus 21 is 42. So 21 divided by 42 is one-half. Same here, one-half. Moving to state 1, the exit rate is 16, so that gives me one-half here and one-fourth here and one-fourth here. Next state, let me call this 2. Exit rate is 2, so this is a 1. And for state 3, we get a 1 here as well. And now I only have to derive the probability for this self-loop and that is 1 as well. So now you've seen how to move from a DTMC to a CTMC by adding a random variable that is exponentially distributed, and you've seen how to move from a CTMC to the embedded DTMC. And even though you might think this is a lot of background information, you will use this later when we need to compute the transient probability distribution of a CTMC. [SOUND]