Finite Math: Markov Transition Diagram to Matrix Practice

hello and welcome to the next video in my series on finite mathematics now if you're watching this video because you're having problems in a course I want you to stay positive and keep your chin up if you're watching this video it means you've come pretty far in your education up to this point and I know that with a little bit of hard work patience and practice you can get through it I have faith in you and so should you I just reminder that these videos are geared towards individuals who are relatively new to finite mathematics so I will just be going over the very basics in this video I'm going to use three examples we're going to go through them step by step very deliberately and I will explain each and every step we take so all that being said let's go ahead and dive right in now in this video we're going to continue our discussion on Markov chains now if you're not quite sure what a Markov chain is I advise you to go back and watch my previous video where I explain Markov chains at their most basic level how they are related to probability trees how those trees are then turned into transition diagrams and then how those transition diagrams are then turned into transition matrices this video will focus on practicing doing transition diagrams and then turning them into transition matrices so we will be doing three different types of diagram two matrices so you get a feel for each type so let's go ahead and get started now just a quick review of Markov chains this will not be as comprehensive as my entire previous video but I'll just go over the basics now remember that there are combination of probabilities and matrix operations so you kind of take the probability portion of finite math you combine it with the matrix portion of finite math and then you come up with Markov chains so it's taking those two different topics and combining them what they do is they model a process the proceeds and steps and those steps could be time or some sequence or trials or whatever but it's a step process like a series of probability trees so I could have a probability tree that works like a coin cost I could flip the coin and then I can write down heads or tails I can flip it again write down heads or tails flip it again write down heads or tails so that's kind of what a Markov chain is now the model can be in one state at each step so in my coin flip example the coin can either be in the state of heads or the state of tails so we talked about States and Markov chains when the next step occurs the process can be in the same state or move to another state so in our coin toss example if I flip a heads and then I flip it again well I can be in the state of heads again or I can go into the state of tails and the movements between states are defined by probabilities so in my previous example again with the coin flip the probability of heads is 0.5 and the probability of tails is 0.5 so each step or each sequence or each trial in two different states are all defined by probabilities now all probabilities exiting a state must add up to one so in my coin flip example if I start in heads and I flip the coin I can either come back to heads which is 0.5 or I can go to tails which is also 0.5 and of course those add up to 1 we can then find the probability of being in any given state many steps into the process and this is where the power of Markov chains lies so instead of doing a probability tree that would take you 20 steps and if you wrote it out it would be the size of a wall you can use Markov chains and transition matrices to find out what's the probability of being in any given state many steps into the future and that's where their power lies so let's go ahead and do some examples so here is our first example we're going to start with the transition diagram and then we're going to generate the transition matrix based off the diagram so in this diagram we have three states 1 2 & 3 and we know that if we begin in state 1 the probability of coming back to state 1 in the next step is point 2 now the probability of going from state 1 to state 2 is point 4 and finally the probability of going from state 1 to state 3 is also 0.4 so notice a few things here we're going to state to state 3 or back to state 1 those are our arrows and the probabilities add up to 1 so 0.4 plus 0.4 plus 0.2 is 1 let's move on to transitions originating in state 2 well we can go from state 2 to state 1 with a probability of 0.1 we can go from state 2 to state 3 with a probability of 0.9 so notice that those already add up to 1 so there is no way to go from state 2 back to state 2 so there's no you know no self loop there at state 2 so you know that once you get to state 2 in the next step you're going out of it you're not going to stay in it now for state 3 the probability of going back to state 3 in the next step is 0.3 the probability of going to state one is 0.7 and again if you notice those add up to one so you're never going to go from state three just over to state two that does not exist it's zero so the first thing we're going to do in the whole point of this video is to practice generating transition matrices based on this diagram now unfortunately because of the size of the diagram I cannot put the diagram and the matrix on the same slide so if you want to pause the video sketch this out and then when we go into the next slide you'll have that so we can go ahead and do the transition matrix okay so let's go ahead and generate our transition matrix now what I did here is give you a general transition matrix and all this says is that the arrow indicates what state were starting in and what state were going to so from and to so in the top left of our matrix we're going from state one to state one in the top center we're going from state one to state two etc so in our transition diagram there are really nine possible paths and that should make sense we have three states for each state we can either come back to itself or go to the other two states so we have a total of nine possibilities now the first thing I recommend doing is when you're going ahead and filling out your transition matrix is to do the returning States first so you look at your transition diagram and look for any states that come back to themselves in the next step and those will be represented by small curly arrows where the arrow just comes right back to the state you're looking at so in our transition diagram the probability of going from state one and then coming back to stay one was point two now the probability of starting in state two and coming back to state two was zero remember so in that one you're never going to come back to two if you're into in the next step and then finally if you're in state three coming back to state three in the next step had a probability of 0.3 so those are the easy ones you just look at your transition diagram look at each state and then look for the probabilities of coming back to each state in the next step and then from there you can just go ahead and fill in the rest so if we continue filling in our transition matrix using our diagram we can see that we have probability of 0.2 0.4 and 0.4 and that's from state 1 to the other three states and itself and so on and so forth now notice that each row has to add up to 1 and that just stresses the point that every path leading out of a state must their probabilities must add up to 1 so if you look at each row 0.2 0.4 0.4 oh that's 1 the second row 0.1 and point 9 that's 1 and in the bottom row 0.7 and point 3 that's also 1 so that's kind of a check if your transition matrix is correct every row has to add up to 1 if something happens and it does not it means you made a simple mistake somewhere so always go back and double check to make sure your rows add up to 1 okay let's go ahead and do our second example this one's a bit more complex in this one we have five states so we have a lot of possibilities going on here now think about it how many possibilities could there be is far as paths to of any given state or itself well theoretically if friend state 1 we could go back to state 1 or to any other of the four states so that will be five potential paths and that's the same way for each state so there are 25 total paths possible let's go ahead and see what we got in terms of probabilities well the probability of being in state 1 and then coming back to state 1 in the next step is 1 that's actually a special kind of state we'll talk about here at the end but if it comes back to itself with a probability of 1 can it go to any other state well no it cannot go to any other state once you get into state 1 you're kind of trapped in it because you can never go anywhere else so that's a special type so there will be no other arrows to any other states coming out of state 1 let's move on to state 2 well the probability of going from state 2 to state 1 and the next step is 2/3 and the probability of going from state 2 to state 3 is 1/3 so if you notice those two add up to 1 2/3 plus 1/3 is 1 so there are no other possible exits from state 2 so for state 3 the probability of coming back to itself in the next step is 1/3 the probability of going from state 3 to state 2 in the next step is 2/3 so again notice that those add up to 1 so there are no other possible arrows or paths leading out of state 3 because they add up the one already let's look at state 4 so the probability of being in state four and then coming back to state four is one that's very similar to state one for both of those states once you're in that state you're always going to come back to it you're trapped in it you can never go anywhere else so there are no other arrows leading out of state for for state five the probability of going to state 3 is 1/2 and probability of going to state 4 from state 5 is also 1/2 now notice that adds up to 1 so there are no other paths or arrows that can come out of state 5 so we can double check to make sure that the exit of every state adds up to 1 so in state 1 it is 1 so we know that's good state 2 we have 2/3 and 1/3 that's good from state 3 we have 1/3 and 2/3 that's good state 4 we have one that's fine and then state 5 we have 1/2 and 1/2 that's good so we know that all of our probabilities add up to 1 leading from each state let's go ahead and do our transition matrix now before I do that I forgot to mention state one and state for our special kind of states they are called absorbing States if any state has a probability of 1 that comes back to itself that's called an absorbing state once you get into that state you're trapped you can never leave so if I'm in state 2 now and then I go over to state 1 in the next step once I get into state 1 that's it I'm trapped I will always come back to state 1 no matter how many times I do the next step the next step is always back to one itself the same thing is true for state for state for so those are called absorbing states okay let's go ahead and do our transition matrix should say matrix are at the top I apologize so again I recommend that you do the returning states first and if we go tour if we go back to our transition diagram we would see that state 1 to state 1 is 1 state 2 to state 2 is 0 there's nothing leading back to itself there state 3 to state 3 is 1 third state 4 to state 4 is 1 that's our other absorbing state and state 5 to state 5 is 0 there is no coming back to itself in state 5 so here our return States again then a couple of things we need to keep in mind here if we are in a row with a probability of 1 we know that everything else in that row has to be 0 because the row cannot add up to anything more than 1 so just to keep everything nice and neat I always tell the students I work with to go ahead and fill in zeros for the rest of that row that way they don't make the mistake of accidentally putting something in it that might cause the problem to become incorrect so I always tell the students I work with do the return states first down the diagonal that's pretty easy then if you have any ones go ahead and fill out the rest of that row with zeros because you know there can be nothing there and then after you've done that then go back and fill in the rest of the transition matrix so again you have to go back and look at your transition diagram look what's going from state to state so if we look at the 2/3 there in the top left of our final matrix we know we're going from state 2 because it's 2 rows down to state 1 because we're in column 1 and we do the same thing for the rest of that matrix now of course you can double check your work by making sure each row adds up to one so the top row adds up to one the second row adds up to one it's two thirds plus one third that's good the third row adds up to one again two thirds plus one third the fourth row is one and then the bottom row is one half plus one half so that equals one so everything looks good and again you just go back and check your transition diagram to make sure everything checks out okay and here's our final example that you might see in your work very similar to the first one but I've changed a couple things so we have three states but for state 1 the probability of coming back to state 1 is 5x what does that mean but we don't know yet okay but again this is one your company you're going to commonly see in finite math it's the probability of being in state 1 and coming back to state 1 is 5 X the probability of being in state 1 and going to state 2 is 2x and the probability of being in state 1 and going to state 3 is X so in the problem you might see it written this way the probability of going from state 1 back to state 1 is 5 times that of going from state 1 to state 3 okay so X + 5 X 5 times the probability or you might see it say something like the probability of going from state 1 to state 2 is 2 times the probability of going from state 1 to state 3 so X + 2 X that's a very common type problem in finite math so these probabilities as of right now our relative probabilities we have to figure out the actual numbers in the next step let's go ahead and continue for state 2 the probability of going from state 2 to state one is X the probability of going from state two to state 3 is 9x okay for state 3 the probability of being in state 3 and coming back to state 3 in the next step is 3 X and the probability of going from state 3 now to state 1 next is 7x and that's all we have to go on so you'll see problems like this all the time so we have to do an additional step to actually get our probabilities let's go ahead and do that now again this is reminding you that the basic matrix form works the same way you should end up by now and we went ahead and wrote in the relative probabilities in our matrix form so remember that the top row is going from state 1 to any of the three states that's the to the second row is going from state 2 to all three states and the bottom row is going from state 3 to all three states and again that just corresponds with our transition diagram but of course that I'm going to work we've got to put numbers in there so how do we do that well we know that each row must sum to one so we know that 5x plus 2x plus X has to equal one and we know that X plus 0 plus 9 X has to equal 1 and the bottom row 7x plus 0 + 3 X has to equal 1 so each row has to equal one so if we do simple algebraic addition there we come up with 8 x equals 1 on the top row 10 X has to equal 1 in the middle row and 10 X has to equal 1 and the bottom row then we just do simple division so in the top row at is 1/8 or 1 over 8 we'll just divide both sides by 8 in the middle row we divide both sides by 10 so there X is 1/10 and the bottom we again divide both sides by 10 and X there is also 1/10 so what we have to do is substitute X into our original matrix so in the top row X is 1/8 so 5x is 5 times 1/8 which is 5/8 two times 1/8 is two eighths or 1/4 same thing and then x times 1/8 is 1/8 so all we do is substitute 1/8 in for X and do simple multiplication now in the middle row X is 1/10 so the X by itself is 1/10 zero is zero in the middle and then nine times 1/10 is nine tenths in the bottom row we have 7 X 7 times 1/10 is 7 tenths we have 0 in the middle and then 3 times 1/10 is 3/10 and that is our transition matrix for a problem our transition diagram that originally started with relative probabilities and again it's a very common type of problem okay that about wraps it up so this reminder I wanted to do three very common examples that you're going to see in finite math in one form or another when you're having to convert a probability tree into a transition diagram and a transition diagram into a matrix so again all three of those as I mentioned in my first video about this those all represent the same information it's just done in a different way and of course as you do many steps in the future the transition matrices become the most efficient by far so this reminder that Markov chains or combinational probabilities and matrix operations they model a process that proceeds in steps maybe that's time some sequence or trials etc the model can be in one state at each step so in our previous examples for in over previous example as we progress we can either be in state 1 state 2 or state 3 and we transition to each state based on the probabilities we are given when the next step occurs the process can be in the same state so remember that some of the states had curved arrows that come back to themselves so that's going to be in the same state the probability of being in the same state or it could move to another state it does not have to move to every state because remember absorbing states come back to themselves all the time they have a probability of one so once you're in that state you can never leave it now we could go from state two to one but we don't have to go from state two to three there's no requirement for that but it can go to itself or to any other state as long as the probabilities add up to 1 so movements between states are defined by probabilities all probabilities exiting a state must add up to 1 and again the power of Markov chains is that we can find the probability of being in any given state many steps into the process so here's what that would sound like so if you remember in our first example we had a three state a transition diagram that we then converted into a transition matrix using the transition matrix we can figure out the probability of say being in state 3 10 or 20 steps into the future now think about that that's pretty remarkable actually if you're going to if you were to do this using probability trees you would need 20 steps of 3 branched probability trees and that would again take up a small wall to write but using the matrices it's very easy to figure out just with a graphing regular graphing calculator it's so simple this takes a minute to do we're going to do that in future videos so again that's the power of Markov chains okay so that wraps up our practice converting transition diagrams into transition matrices because if you can't do that then we cannot do the next step or the next type of problems involving Markov chains so we have to be able to convert basically between probability trees transition diagrams and transition matrices because really they're all representing the same type of information but we have to have it in matrix form to do more advanced work and Markov chains so again if you're having problems in a course I want you to keep your head up and stay positive you've come this far so keep practicing keep working hard and I know you can make it I believe in you and so should you so if you like this video give it a thumbs up if you think it can be better leave me constructive comment below and we'll try to make them better so thank you very much for watching good luck and look forward to seeing you again next time you

Channel: Brandon Foltz

Views: 97,214

Rating: 4.8905358 out of 5

Keywords: transition probability matrix, transition probability matrices, finite math matrices, markov chains transition matrices, markov chain matrix, markov analysis, transition matrix, transition matrices, transition diagram, finite mathematics, finite math, statistics, markov chain, brandon c foltz, anova, linear regression, logistic regression, brandon foltz, transition, statistics 101, markov, markov chains, math, math matrix

Id: hUBc2Nb8yyI

Length: 28min 36sec (1716 seconds)

Published: Wed Nov 07 2012