Intro to Markov Chains & Transition Diagrams

in this video we're going to talk about markov chains which is a type of statistical process it's used widely in probability and statistics and heads enormous number of applications and to illustrate the idea of a markov chain let me begin with a concrete example i want to imagine some collection of cities i've got four cities here and they each have a rail connection so not every city has a direct connection for example city a is only directly connected to city b but then b is connected to multiple other ones now unfortunately there's a lot of crime in these cities but we have a superhero who's here for the rescue unfortunately this superhero has some limitations first limitation the superhero can only travel down the connections they have to take the train they can't fly and then secondly this superhero is a little bit of a forgetful one they don't know where they've been in the past if they're at any given city and they want to go to the next one what they do is they just look at the different trains they can take the different connections and they randomly choose between them they don't remember where they've previously been they just know where they are right now and randomly choose where to go in the future so for example if our markovian superhero starts at city a there's only one possibility for where they could go they could go down to city b there's only that one connection but now that they're at city b there's three possible ways they can go back to city a they could go to city c or in this case they randomly choose between a three and how about they end up as city d now that they're at city d again they can randomly choose between the two possibilities go back to city b or onwards to city c perhaps they're randomly chosen to go back to city b and then on to city c who knows what happens so this markovian superhero is always deciding the next step is just a random choice based on where they currently are so that is the idea of a markov chain and let's put up our formal definition a markov chain is a sequence of events in this case the sequence of events was they were going between different cities such that the probability of where they go in the future the probability of what the next step is going to be only depends on the present it only depends on where that superhero was at that particular time not where they've been in the past and there's all kinds of statistical processes like this a sequence of events that happens over and over and over again for example every day you can look outside it's either cloudy or rainy or sunny and that fact happens over and over and over again and every time you have a sequence of events if you're trying to predict the future you may sometimes only wish to use the knowledge that you have at the present and sometimes you might wish to also use information from the past and that's the difference between a markov process and a non-markov process for example let me now show you a non-mark of superheroes this is a new superhero still has to go along the rail connections but this one has a memory this one is going to go between the cities in a way to sort of optimize and see all the cities as often as possible so they started city a again the only option to go to city b and then the superhero is not going to bother going back to a because it's a non-markovian superhero it knows where it's been in the past the past information previously being a is available and so it doesn't choose going back to a it chooses going on to c or d perhaps going to c and now that it's at c it knows that it's being at a and b previously so it's not going to go back that direction and so it goes on to d and so the fact that the probabilities for this superhero depend on more than just where it's currently located on more than just the present means that this superhero is a non-markovian superhero now i'm actually going to improve the diagram that i have a little bit i'm going to separate out each of these connections to make it more clear that there's an arrow leaving an arrow coming back and one of the things i want to do is try to figure out the probability for each of these different arrows so for example imagine i was at city a there's only one option for me to go the only option from leaving city a is going to city b so with probability 1 or 100 probability anyone that started at city a has to end up at city b however now you're at city b there's three different possible connections back up to a or c or d and so if those are all equally likely if you're randomly choosing between them each of those have probability one third okay so we're getting a lot of the arrows now let's imagine you happen to be at city c there's two possible outputs if you randomly choose between them it's a half for each and similarly for d there's two outputs again and a half for each of those what i've done here is created something called a transition diagram a transition diagram lists all the possible states in this made up example there's a b c and d and then it lists the probability for every connection every arrow that goes between two states and so this transition diagram sort of encodes all of the information about the movements of our markovian superhero okay let's do a little bit more serious of an example i'm going to try and model the stock market now in any given week the stock market either goes up or down if it goes up we're going to call it a bull market just some fancy lingual if it goes down we call it a bear market and this market that we're studying if you look at the historical data it's one that has been going up more than it's been going down it's one that's been a bull market more than being a bear market and so the historical data says 75 percent of the time that it's a bull market it's followed up by another bull market and likewise 60 percent of the time it's a bear market so going down the next week it's also going down again it's another bear market this data is just totally made up for the purpose of illustrating this example doesn't represent anything realistic nevertheless we can try and model this with a markov chain and the first thing i'm going to do is take my two possible states my bowl and my bear and to finish my transition diagram the diagram that shows all the connections i put in what are all the possible connections i could start as a bear and become another bear i can start as a bull and become another bull i can start as a bear market week and then the next one be a bull market week or vice versa so there's these four different arrows and our job to fill out the transition diagram is to label each of these arrows with the appropriate probability let's first imagine that it starts with a bull market this week is a bull market it's going up then the question is well what's going to happen in the next week well our data said that 75 percent of the time it's a bull market the next week is going to be a bull market again so that arrow going from bull market to itself is supposed to have a 75 chance or a 0.75 and if 75 chance is that it becomes a bull market again then the remaining 25 goes to the other arrow the chance where it goes from a bull market in one week to a bear market in the following week likewise if we now focus on when it's a bear market in the first week there's a 60 chance that it becomes a bear market again so i can fill in that arrow and if it's a 60 chance that it goes from bear market to bear market the remaining 40 percent chance goes from bear market to bull market so now i've labeled all of the arrows in my transition diagram with a number and so i'm complete with that let's actually use this let's use this example to make some predictions about the future for example i could go and ask what happens two weeks from now if i know it's for example a bull market this week i can make the predictions that's the 75 and the 25 for the following week but what about the week after that to do this it's actually useful to use a different type of diagram we've been talking about transition diagrams so far but next i'm going to look at something called a tree diagram so i'm saying i know it is a bull market in this particular week so i'm going to just put bull market down there then i know that that splits to the next week in two possibilities 75 chance bull market 25 chance bear market that is there's two possibilities for the outcome after one week and if that outcome was that it was a bull market that then again is going to split into 75 chance of a bull market two weeks in the future and 25 for it being a bear market alternatively if one week in the future it was a bear market that would split according to the diagram as 40 chance of bull market and 60 chance of bear market and so what i've got in here is this nice little tree diagram that allows me to start with the certainty of being a bull market and then project one and two weeks into the future as you can imagine you could keep on doing this for three four five a hundred weeks into the future if you wished it would just be a much more complicated diagram so now let's actually answer that question what is the probability two weeks in the future of it being a bull market well two weeks in the future being a bull market there's actually two different pathways it could be bobo ball or could be bull bear ball those are two different approaches to ending up with it being a bull market two weeks into the future so to compute the probability of being a bull market two weeks into the future i have to add both branches of the tree diagram that end up with it being a bull market so first the yellow is the 75 percent chance times another 75 chance that's going to be one way it ends up as a bull market and the other approach is the 25 that it turned to a bear in the first week and then followed by that 40 chance it turns back into a bull that's the blue add those together and i get about a 66 chance of it being a bull market in two weeks okay so let's recap a little bit about what we've learned and what we need to investigate in the future we've seen how a markov process is one in which the probability for the future only depends on where we are at the present it ignores what happened to the past we've seen how we could draw a transition diagram and we've seen how for multiple predictions in the future a tree diagram is useful but where i'm getting a little bit stuck is that if i had to predict long into the future like for example 100 steps into the future this tree diagram would get very very cumbersome and so i want a more efficient way to encode and to manipulate the data that's represented in one of these transition diagrams and indeed in the next video on markov chains we're going to see exactly that we're going to see how we can use matrices and a little bit of linear algebra don't worry i'll introduce the entire idea to you in order to make these types of manipulations significantly easier all right if you have any questions about this video leave them down in the comments below give the video a like for the youtube algorithm and we'll do some more math in the next video

Channel: Dr. Trefor Bazett

Views: 16,337

Rating: 4.984293 out of 5

Keywords: Math, Solution, Example, Markov Chain, Markov Process, Probability, Statistics, Transition Diagram, Initial State, Tree Diagram, Future Probability

Id: rHdX3ANxofs

Length: 11min 24sec (684 seconds)

Published: Mon Sep 07 2020