This episode introduces the idea of a Markov Chain. A Markov Chain has a set of states describing a particular system, and a probability of moving from one state to another along every valid connected state. Markov Chains are memoryless, meaning they don't rely on a long history of previous observations. The current state of a system depends only on the previous state and the results of a random outcome.
Markov Chains are a useful way method for describing non-deterministic systems. They are useful for destribing the state and transition model of a stochastic system.
As examples of Markov Chains, we discuss stop light signals, bowling, and text prediction systems in light of whether or not they can be described with Markov Chains.
(upbeat music) - The Data Skeptic Podcast is a weekly show featuring conversations about skepticism, critical thinking and data science. (upbeat music) - Welcome to another mini episode of the Data Skeptic Podcast. I'm here as always with my wife and co-host Linda. - Hello. - Thanks again for joining me, Linda. - Thank you. - So Linda, do you remember several episodes ago when we talked about partially observable state spaces? - Hmm, I don't know, did we? - That is the case where you can't necessarily know the true situation you're in, but you can observe secondary versions. And you should go back and listen to that episode if you haven't yet. But we're gonna talk about something today called Markov Chains. And these things kind of relate. So we talked about state spaces then. And we talked about how our bird Yoshi, who's here on your hand, has different moods and you know, she goes from happy to hungry to sad to quiet or whatever. Let's talk a little more generally about state spaces. You know the game tic-tac-toe, don't you? - Yes. - Can you describe it for me? - There's a grid and one player's X's and one is O's. You take turns marking them until someone gets three in a row or you start a new game. - Now let's say you were walking through the park one day and you came across a piece of paper that had a tic-tac-toe game on it. But it wasn't complete. It just had like two X's and one O. Whose turn is next? - Well it's O. - Yeah, right, how'd you know? - 'Cause there were two X's and one O and you're supposed to take turns. - So you know something about the state of that game of tic-tac-toe. You see how two moves that X made. You don't know the order that X made those moves in, do you? - No, but I could guess. - You could guess, but it also doesn't matter and that's the key and that's what Markov chains and what we're gonna talk about in a second is the Markov assumption is all about. It's the case when you can describe the situation you're interested in in a set of states and that the current state relies exclusively on the previous state and whatever went on in between. So let's talk more generally, step away from tic-tac-toe. Let's talk about monopoly. Have you ever played monopoly? - Yes, well it took me a while to play by the rules or even know what the rules were but you try and buy a property and then build on the property like hotel or houses and then as people land on your property try and make money. - Right, so let's say a similar situation. You walk by an in-progress game of monopoly. Can you tell the current state like who's winning or who has the most property, who has the most money? - Maybe, yeah. - Pretty much, right? 'Cause you can see like who has hotels on the board and who has houses on the board and how much money they have in front of them. The first point I wanna make is that and games are a great analogy for this. There are states of the game. The state is the collection of variables that describes everything you need to know about it. So we could even talk about the state of our house like do you think our house is currently clean or not clean? - It's okay. - It's okay. So how discretized might you describe our house in terms of clean to unclean? It's neither clean or unclean. It's okay, are there only three states or are there multiple states of being? - There's multiple states. - How many? - I don't know, I mean probably infinite if you cared to define it. - I'm so glad you said infinite because yes, it should be in general a continuous state space that like I could add one more gram of dust to the house and little by little that would like slowly add more dust. So there are an infinite states of cleanliness of our house but in general and in practical terms you're often forced to discretize that which means you separated into different states. Like it's a little bit cleaner, a lot cleaner. Maybe you have like 10 divisions or something like that and Markov chains they can work at continuous spaces but I only want for today for the sake of this podcast to talk about discrete time events where the current state is a isolated period of time and it depends only on the previous state and what's happened in between. - I think I get it. - So let's go back to Monopoly. I can hold certain properties that I've purchased and we know whose turn it is and we know how much money everybody has and we know where the pieces are on the board. So in fact you could have a game of Monopoly that people have been playing for like an hour, have them all stand up and walk away and have like four new people come and sit at the table and they should be able to pick that game up and play it to completion because as soon as they sit down they see the whole state of the board everything's perfectly observable on that case and they can just play it. The current state depends only on what happened previously and what action took place in between. Now that's not true of every process but in the case where you can discreetly describe your state space and you can talk about how it moves from one state to another even if that's probabilistic or especially when it's probabilistic we call that a stochastic process. So how does one decide how many spaces they get to move in Monopoly? - Your old die. - Do you know in advance what the die will say? - No. - That's right so that makes it probabilistic and therefore stochastic that the next state depends on a random variable an event you can't predict at the onset. So the Markov assumption is the key to Markov chains that we're about to talk about. And the Markov assumption says that the current state depends only on the previous state not necessarily like eight states ago. Think of just like a board game and the current like whose turn is it depends on whose turn it was last time and where all the pieces are on the board. So it's a much simpler situation than a relationship. And those are cases where you can make a Markov assumption that the current state depends only on the previous state and what's happened in between. Whatever probabilities govern the transition from the last state to the current state. So I wanna ask, are you aware that Markov chains affect your everyday life? This is probably the one data science thing that you encounter every single day. - So Markov chains are situations which you only need to know one step up previous. - Correct. Can you think of times when you encounter these? - What about a stoplight? - A stoplight, that is kind of a good example because it's, let's say it's green. It's either gonna stay green or it's gonna go yellow. It's definitely not gonna go from green to red, but once it goes from green to yellow it will go to red after some period of time. So you don't know when it's gonna go from green to yellow. Well, you're gonna follow the signal, right? - Yeah. - Like you're not gonna go straight away through a red light. - Well, we generally want to. - Yeah. - I mean, you want to follow the signal and not go through a red light. - But you probably, when it goes from green to yellow, depending on your strategy for driving, you either wanna slow down or speed up real fast. That's kind of the two driving strategies I have to-- - To be clear, Kyle speeds up and I flow down. - Fair enough. - All right, so let's go back to I said, if anything of the whole podcast, Markov chains are the things that you have most interacted with in your day to day life. Do you know why? - No. - Can you think of one situation? - Well, I can think of one now 'cause you pointed to one. (laughs) - Well, it's an audio podcast. They didn't have to know I cheated. What's the one you're thinking? - Kyle pointed to his smartphones. He's saying that, I'm guessing he's saying that our phone or apps on our phone predict where we're going based on our calendar, information, or whatever, past. - Oh, you took it fancier than I meant. I meant like when you're sending a text. - Ow, whoa. - Markov chains are built directly into our phones and they helped you predictive text because they can look at what did you type last and what might you type next. And that can be a useful tool for enabling you to just like click a button and say like, oh yeah, that is the phrase I want or that's the word I want. So whether it's based on single characters or engrams, which is the term we used to say like a couple of words together, like a bi-gram is two words together, a trigram is three and an engram is any number of words together, these are predictive tools that are based on Markov chains that exist kind of prolifically through all technology right now and you benefit from them every day. - So are Markov chains statistics or AI? - Well, that is almost philosophical. They are definitely statistics and AI benefits from them strongly. So does operations research and a variety of other fields. All right, I got one last example. Do you think bowling follows the Markov assumption? - You mean like winning a game or just keeping score or one at a time? - Keeping score. - I guess? Well no, 'cause I think isn't there some point rule where you get an extra turn and you need to know what happened to turns before? - That's right, you found the trick question. So bowling is sort of a Markov process up until the 10th frame because otherwise the score and the current frame is based on what happened in the last frame and what happened in this frame. But in the 10th frame, if you hit a bunch of strikes, then it's like you get a couple, you get an extra throw. So it kind of partially slightly violates the Markov assumption. But other than that actually it is kind of scored in a very Markov fashion. I only know that 'cause I'm really bad. So it's never happened to me. (both laughing) - One day. - So next week we're gonna talk about an extension to this. So you wanna probably remember what we talked about here. We're gonna talk about Markov chain Monte Carlo, which is, well, we'll get into it then, but it's an extension of this that's actually very powerful. - All right. - All right, well thanks again for joining me, Linda. - Thank you. - Oh, and yeah. So I've been doing these shout outs to all my favorite data science podcasts at the end of these episodes. Eventually I'll switch over and start doing shout outs to skeptical podcasts. But for now, this week I wanna give a shout out to the Friday Lunchtime Lectures podcast, which is produced by the Open Data Institute in the UK. The audio quality isn't always the greatest, but there are some great topics and I love Open Data. In fact, if you live in Los Angeles, I'm talking, oh, when this airs, I will have talked three days ago. So if you live in Los Angeles and are also a time traveler, you can go see that. But other than that, you know, as always follow me on Twitter. It's @DataSceptic. Join the Facebook page, and please, please leave us reviews on iTunes. Those are how other people find the show. So we really appreciate when people leave reviews. We appreciate everyone listening, and we will see you soon. - Thank you. (upbeat music) (upbeat music) (upbeat music)
