Transcript for:
Understanding Discrete Time Markov Chains

all right hello everyone my name is dylan wong i am a math uh senior year math major up at the university of nevada reno and i decided i'd upload some videos to this channel again to just kind of go over some cool and more complex math processes i studied in the last couple years at the university some of which when i got to the higher levels i felt as though the number of online resources like uh you know condensed digestible videos just they weren't very readily available there weren't very many you know there so i guess i thought i'd kind of go over some topics i feel like i had a pretty good grasp on um one of which is stoichastic processes so i will be beginning a video series uh first on stochastic processes which um just kind of cover some of the main ones you could uh use in a practical setting and some of the theory behind how they work um and yeah so to get right into it the first one that i wanted to talk about was okay discrete discrete time markov chains all right and uh okay so what is i just well let's break this down what is a markov chain and i think the easiest way to talk about what a markov chain is is to draw a picture so there's a kind of graphical representation of markov chains so one in which we have several nodes something like this so a b c d right and um these can represent anything really uh they're as long as they represent different states in a system so these can be what restaurant i choose to go to lunch at today [Music] now if say i had a yesterday well then i could go to b and maybe there's an 80 chance i i like going to b after a i also could stay at a however the same restaurant two days in a row you know who knows probably a little bit lower percent chance that i do that something like an 80 20 in this example and then let's just say from b i can either decide to go back to a and maybe i do that half the time and otherwise if i had b yesterday i like to go to d about half the time and i never get b twice in the row lastly uh or not lastly but then let's just say i had d yesterday uh maybe after d i always want a so i have a 100 chance of going to um a after getting d if i got d last time and then c i'm gonna leave this as a little singleton you know c is like your favorite restaurant if you go there once you're hooked you can never you know you can't bring yourself to go back to any other restaurant it's just kind of a weird case for convenience of talking about it later so there's some pretty reasonable questions that may arise from having a system like this we may want to ask some questions so first we make define uh let x sub t equal state time t or after you know t days of eating out um so i may want to ask questions like what is the probability of x sub t equaling some value given that on the first day we had uh restaurant a right that's a pretty quick a reasonable question we may want to ask another reasonable question we may want to talk about is that as t approaches infinity uh what is p of x of t you know or in this case p of x of t given some initial probability given that we started at a and you may ask okay well why would we want to know that but let's think about what this means uh after after i spend an infinite amount of time or go to an infant number of restaurants what was my what's the probability of being at any given one of the you know four available restaurants that essentially also describes uh the percentage of time i spent at each restaurant leading up to the infinite number of you know visits so you know you could think of this like in your lifetime how long will you spend at any given restaurant but let's not get too far ahead of ourselves okay so here are some possible questions basically that we made that may be kind of reasonable to ask but for now i'm going to take those and just set them aside and i figured it didn't grab that that's okay so let's just set these aside for a second oops still getting used to this little tool down here okay so with those out of the way now um just kind of forget about those and we'll come back to them let us define if we wanted to answer those questions right uh there's two things we need to do we should really define some vocab right some general sort of information about those the markov chain and we should try to communicate this data these one-to-one relationships in a more kind of mathematically applicable way because right now i mean how would we refer to you know this probability 0.8 here um i mean sure we could call it the probability from a to b or something you know involving treating it like a line segment but that's really a little bit convoluted and i don't doesn't feel very natural so where i would like to suggest we go is make something called a transition transition matrix and i'm just going to label this big t so big t uh equals a matrix except let's write it as a table first i feel like that a matrix is just a table but this will be a little bit more helpful maybe so let's just say uh we have all our starting points right we can start at state a b c and d no problem and from any of these four states we want to write down the probabilities of going to any other state a b c and d all right so the chance of staying at a given that you are at a is 0.2 right the chance of getting that food twice in a row the chance of you know having a the previous day and then going to b is 0.8 and then if you look a has no other connections to c and d so we're just going to put zeros there next uh if the chance of going from b to a is 0.5 the chance of going from 0 to or sorry from b to d is 0.5 and then it's 0 everywhere else right we never stay at b and we never go to c from b if we're at c you'll notice it's zero everywhere except it can stay at itself and in fact it only ever stays at itself and then d is guaranteed to transfer to a so from d you can only go to a everything else is zero okay so now one way to check that you did this right is that all the rows should sum to one the columns don't need to they can be anything but the rows should sum to one so yep that checks out one-half plus one-half's one one one very good and that kind of makes logical sense right we couldn't have one of these nodes that had a 50 chance of going to d a 50 chance of going to a and a 50 chance of going to c that doesn't quite make sense so this is what we call the transition matrix and we tend to write it well in matrix notation so we could say that the matrix t equals 0.2 0.5 0 1 0.8 0 0 zero zero zero one and so this is just a quick transcription of what's in that table to a matrix uh because we probably will need to use that so here we go we have this transition matrix and now before we continue going down the mathy route to try to answer these questions that i alluded to earlier let's let's first get a little bit of vocab out of the way now that we kind of have an understanding of what a markov chain is so i already said these are called states um and now we have a way to classify states so there's two categories of state we have transient so a transient state is one that you visit a finite number of times now in this case that's a little bit that's a little bit of a relative thing this is a special case so if we start it anywhere in state a b or d then c is a transient state because we're only going to visit it uh zero times a finite number of times and then we also have the class of recurrent so i'm guessing uh you can all figure out what would fall into our current it's one that we visit an infinite number of times so long as we iterate this markov chain an infinite number of times and that would mean that a b and d are all transient states assuming we start in this chain now if we were to start in the chain c it would be a recurrent state and these would all be transient because we'd visit them zero times but for now i'm just gonna say these are what we care about because we're assuming that we're starting on you know one of these three now the fact that it does matter case by case means well you may question okay how am i gonna know if you know there's different kind of cases in which the transient recurrent states depend on and that can be simplified down to whether or not the markov chain entirely is um irreducible okay so an irreducible markov chain uh would mean like a b and d itself if we just had this this would be an irreducible markov chain every link needs to be there we can't simplify it at all however the one we have here including c is a reducible a reducible markov chain and so uh that's actually because what we have here is two separate markov chains anytime you have a node completely disconnected from another one that would be um really best declassified as its own markov chain however i wanted to demonstrate the fact that markov chains are interesting in that you can actually represent multiple markov chains within one transition matrix since the zeros in the diagonal in horizontals will uh basically be the separating line between the two um so if it's reducible this kind of is subjective if it's an irreducible matrix these are fixed and that's that's about i think all the depth we need to go in uh to for that basically uh you're welcome to do a little more research but honestly it's notation that we don't use too often so that's why i'm just going to kind of throw that off screen right now and then one more thing in terms of notation that i do want to talk about is uh grab my white pen again periodically so this one not super important uh i'm not going to cover it in great detail just i would look up do a little research kind of look into it on your own if you want it's you can just do a google and you'll find out periodically of markov chains but it just describes the number of or rather the frequency with which you can expect to visit a certain node um so in this case you know this one would have a period of one because every single time it's returning to its the state c so um yeah like i said i honestly haven't found it too applicable i rarely used it in all my time going through you know upper division math courses at my university so i don't think i'm going to cover that one very much now let us go back to what we originally proposed right let's try to do an example of this so we want to solve for the probability of x sub 1 um given that or here let's rather let's see the probability of x sub 1 is equal to a given that x sub zero is equal to a right so let's let's calculate this um we can look at uh here and we can say all right if we're starting at a what's the probability that we will be at a next time well that's just 0.2 very simple let's do one more kind of simple case right so the probability of x equal 1 equal to c given that x sub 0 is equal to a well if we're at a there's no chance we're going to c so that one would be zero so that's two very simple cases of applying this right now another reasonable question we may want to ask though is just what is the distribution of probabilities on after one iteration of the markov chain given that x sub zero equals a so if we start a what are the probabilities of ending up at any of the states is kind of more how this one reads um and for that one well essentially we know that we can just take the first column here out of our table and that's going to be the distributions um right wait does d yeah d does go to a okay um sorry i just wanted to check my math real quick so here we are and uh what this actually is is sorry it's not the first column it'd be the first row that's where i got thrown off so this one here would be transition matrix row one and that would equal so if we're going to fill out this vector we know that uh if we're starting at a then the probability of us ending at a is 0.2 the probability of a starting a and ending at b is 0.8 and then its zeros thereafter so we've answered this first question we have found a distribution for a equal for x after one iteration of the markov chain when we started at a now let's try to take this uh one more like one further so let's look at x sub two given that x sub zero equals a and well now a we had two options right so this one gets a little more complicated um because after this first iteration after x1 we don't know where we are anymore there's no explicit you know set value so what we're going to have to do is actually do some matrix multiplication now there's kind of two different approaches here you could go with and so if you allow me to be a little hand-wavy here what we're gonna do is we're going to um actually take t the matrix we're going to square this whole thing and then take the first column okay and to do this matrix operation i'm not going to square out this 4x4 matrix here in front of you guys i have it pulled up in symbolab which is a good tool if you just want a free tool online to do some simple like linear algebra type matrix operations and we can see that this is the matrix when we square it again i'm doing some hand waving by saying we should square it and we're going to verify using brute force that this was correct now because we know our initial condition was a i was saying we take the first row of this matrix so i have to remember 44 16 and 40. and oops sorry that's the wrong way so come over here we have 0.44 0.16 and 0.4 one important thing a way you can fact check these is that this should still sum to one you should always sum to one you should always have a total of 100 probability 100 probability of being at one of the states that would mean if not you found your way outside of it somehow which is impossible and you probably did an operation wrong um now let us verify this with brute force so how would we get to this with brute force so we know we have a 0.2 percent chance of staying at a meaning if we uh want to consider the chance that we after one iteration stay at a and then a second iteration stay at a in order to fall into this category well that's 0.2 times 0.2 all right and then or if we stay at a we have the 0.2 percent chance we stay a but then we transition to b well there's a 0.2 times 0.8 percent chance of that happening now consider the alternate case there's a 0.8 percent chance that we go straight to b so we're at b now and we have two options from there so wallet b we have a 50 chance to go back to a meaning there's a 0.8 times a 0.05 chance of going back to a and finishing the end of the two stages there and there's also the chance that we go to d from a which is a zero point eight percent chance to get us to b times the zero point five percent chance that we will then move to d this is simple uh this is like something you should know from stats like intro to stats anytime we want to consider the probability of two events happening we just multiply their probabilities [Music] and sure enough if we check this uh 0.2 times 0.8 is indeed 16 0.4 times 0.45 is 0.44 you know so on so forth basically um you can go through and verify these but indeed this strategy did work so while it is a little hand wavy we can essentially generalize that p at x sub t uh is equal to sorry given x sub zero equals some initial condition uh let's call it n is equal to uh t to the t at row n so that's kind of uh the generalized way i'm going to say this so if you want to know the distribution at any you know teeth time or step in time then you just have to take the nth row of the matrix transition matrix raised to the t power that is one of the mathematical beauties of writing the markov chains in this matrix form uh that just happens to be a consequence of kind of the nature of changing from one state to another it acts a lot these operations here and summing these things acts like matrix multiplication um and that's really the kind of data we're encoding when we do that so now there's one more thing i want to consider and that is as i said what happens as t goes to infinity right what do we what happens here um and so we can't exactly take the you know infinite power or multiply this matrix by itself an infinite number of times that's that's not very practical um so we kind of can take a linear algebra approach out of it and that is so to find the stationary distribution um that's actually what we the name we give this so the stationary distribution which is the [Music] sort of the distribution distribution approached after an infinite number of iterations right uh also keep in mind that is given uh some initial condition right some x sub zero so in this case let's try to find the stationary bit distribution for the particular matrix we have here well uh the way we go about that actually is we solve oops solve for eigen vectors and the values so we want to solve for the eigenvectors and values that is step one and again this is something i'm going to do in symbol lab because i already have the matrix typed up here i'm not going to work through those by hand but in vector so it'll take a second it'll calculate it or it'll take quite a while apparently um maybe i'll just cut to when it feels like finishing okay there we go uh it finally finished doing its thing um i forgot we can't so and to do this one um let us use an entirely different markov chain okay so we're going to have a new transition matrix right um and it's not going to correspond to the above transition matrix so we have a new t and we're going to give it something like 0.5 0.5 0 uh and we'll just make it even a three by three we'll be fine then we have a zero we have a one and a zero and then maybe we have a zero point two we have a zero point three and a zero point five something like this right that's a that's a valid uh transition matrix and let us go plug this into an online calculator once again so we're going to plug this into symbol lab just uh for ease of uh not having to do the eigenvalues and stuff on camera i'm hoping that you have a basic knowledge of linear algebra slash differential equations if you're watching uh this and kind of getting into stoichiostic processes but or stochastic excuse me if that was something maybe people wanted to see a video on in the future i could probably cover enough of these topics for you to follow along but leave a comment if that's the case let me know so let's solve for the eigenvectors now there's gonna be a number of them in this case two there's usually uh one minus the number of columns worth or actually has a multiplicity there's one for each column right and um in this case right oops sorry what we're looking for is the maximal eigenvector usually it's one normally you get ones with a fraction and stuff pretty much always choosing one just works but we're looking for the the maximal one um and if there's negatives and even if it's a big negative number you forget it we're looking for the just not absolute value just the straight maximum one and in this case pretty simple right it worked out that uh x sub 1 is equal to 1 1 1 as our vector so what this actually means is that if we come here and [Music] we were to take this one and um write that vector down right so at lambda equal to 1 we found that the eigenvector is one one actually i can i can write this sideways that's fine one one one that's our eigenvector and now all we need to do to get the stationary distribution right step two is i'll make a note we choose want to choose the maximal lambda so choose the maximum lambda and the corresponding vector then step two is normalize this vector uh those again you should hopefully know what normalizing is slash means but uh i'll run you through it real quick basically we need this to sum to 100 while keeping the same proportions that it is there's a particular formula but in this case it's so simple i'm just gonna do it and say that the stationary distribution equals one-third one-third one-third pretty much the formula is you simply add together everything inside of here and then divide each component by the sum of everything inside so one plus one plus one is three divide everything by 3. that's how you get the stationary distribution this so what does this tell us just as a reminder this means that in this particular markov chain given an infinite number of time passing we expect to see it spend an equal amount of time basically at all three of these which kind of neat um and so or sorry after that's not what it means after an infinite number of time we are equally likely to expect it to be at any one of these um which again it does kind of mean the same thing but it's better if we word it that way i suppose and with that um i think that's basically going to wrap up today's episode on discrete markov chains um there is one more important thing i wanted to say which is we never quite broke down the whole discrete thing what does discrete really mean um in discrete as just as a note right so i'll just note as a note discrete uh refers to refers to steps uh include or just the number of steps rather than then periods of time in which steps are distributed oops so uh discrete refers to the fact that uh these jumps we're just assuming one jump to the other so any time we increment this number t here that i was using to represent time that is we've assumed it increments the second we jump from one state to another um and that you know we kind of have to run through this whole process now in real life these kind of systems uh they're not like that usually there's not kind of these decision point moments in which you can know with certainty you're transferring from one point to another in general when it comes to real life uh practical applications with markov chains we tend to talk more about like over a given amount of time something will you know if if we go back to the restaurant analogy sure it could be that i'm in this case it's best model by the fact i make it the decision every day to go to uh one of those restaurants and it's always at 12 o'clock that i just feel hungry for lunch right um but that's not it's not always so convenient right that on some particular time on the clock i'm just gonna go in real life it may work out that i may get busy i mean you know stuff may happen let's just say every day i have um or between certain hours i have a given probability uh within this window maybe of going to lunch and you know so i have certain frequencies within there which you know it's likely that i'll go to lunch and you know i'll get more on that next time but as a little preview we can imagine over a one month period the number of times that i decide to go out and eat is exponentially distributed so we could graph the number of times i feel like going out to eat and it has some distribution that we know and then now when we combine this kind of varying randomness with um the fact that i randomly am going between the states each time with some given probability we create this kind of composite more complex thing and what's really cool though is that despite adding kind of this extra layer of obscene complexity here it really does uh not change the core math of how we apply these principles hardly at all um and so i'll exhibit that through some examples and maybe through some code down the line but that wraps up today's um sort of little mini not too short briefing on markov chains um please leave a like let me know what you think and thank you all for watching