What are Markov Chains | Mathematician Thane Plambeck

I want to talk about Markov chains. Does anyone know what a Markov chain is? One person? Okay, good. So this is your introduction to Markov chains. Markov's looking pretty good in this photo. I don't think this is a photo. This may have been a drawing of the guy. He was a Russian mathematician. Have you ever played this game? Do you know this game? No. Okay, Chutes and Ladders, or Adders, or what is it? Chutes and Ladders, Adders, and what is it in the UK? Anyone from the UK here? Adders and Ladders. Adders and Ladders is what they call it. Adder, you know, like the snake. Adders and Ladders. Okay, so in this game, what do you do? You start with your guy at 1, you roll the dice, and then you move from one state to another state. And then it hap— So I'm going to call the boards states. And here are the squares on the board states. And then there's this drama here where if you land on 4, for example, you know, you go up to 14. But we could just think of that as a shortcut, you know, that if you're at 3 and you roll a 1, you end up at 14, okay? So it's a bunch of states with arrows between them, each with a certain probability of going there. And the probability is what you roll on the dice. Okay. OK. OK, so this is a very simple model. So you just have a bunch— you just think of a bunch of circles with arrows between them. And when your little guy is sitting on some specific circle, you roll some dice to determine which new state you're going to go to. That's all it is. That's all a Markov chain is. Why is this a great thing to know about? Number one, it's a very, very simple concept. There's— at the core, there's nothing more than what I just said, states with arrows between them and probabilities. It's also industrial strength in that it's literally underneath almost everything. The algorithms are really well understood, and you can get books no matter what you— whatever you're working on, you can find a book specifically about applications of Markov chains to that. There's a lot of stuff to read. And then finally, the greatest thing about it is magic. They oftentimes will just give you answers to problems just almost by magic. I mean, it seems like magic to me sometimes. So here, just to make it specific— and when did I start this? I don't want to go over time. Does anyone know? We started at 2:00, or did we start late? We started about 10 minutes ago. OK. Here's a Markov chain, very simple. It has 2 states, A and E. And you see I've got some arrows that— let's say if I start in A, then I imagine rolling a 10-sided die. So with probability 40%, I would go to E. Otherwise, I would just stay at A. And then I do it again. And maybe this time I go to E. And now I have a probability of 30% of staying and 70% of going. And then we usually think of it as having some sort of output. So when you're at the state, you output that letter. OK. Okay, well that very simple thing is used in all this stuff. And I don't need to talk about all of it. I'll just take one of them. Okay, so take speech recognition. I don't know if you've noticed that, like, have you ever really tried using Siri? Yeah, it rocks. It rocks. Okay, and when it doesn't rock is when you start it before you know exactly what you want to say. Right? If you're sending someone a text message, you just have to pause for a second and say, what do I really want to say? The whole sentence. And then you start it, and then you say it. And it can be very complicated, and it will get it exactly right. I mean, I've never seen it, when I followed the rules I just mentioned, get it wrong. How does this thing actually work? What is it actually doing? Well, what it's doing is it's taking the little sounds that you make, and it's trying to decide what sound it is. And it's got a huge Markov chain. You can think of it as this. I don't know that this is exactly how it works, but it certainly works something like this. There's a huge Markov chain where it computes what is the most likely thing that you said. What's the most likely path you followed? For all of those weird noises you just made, the one that is most likely is this weird thing, you know, that happens to mention the Eisenhower administration, ping pong balls, and— it doesn't care what the substance of what you're saying, but it— and it probably brings in grammatical things also. But the algorithm itself is very, very simple. And it's just the— what's changed is not the algorithm. What's changed is that the cell phone is so powerful that you actually can do this now. I mean, it's long been known how to do it. It's just like, you know, can you carry it in your pocket? Is the computer fast enough to do it? And now it is, so it's just like— that's why I say it's like magic. Once the stuff gets powerful enough, you can do stuff using algorithms that have been known for like 70 or even 100 years, okay? And these are just more examples. I'll talk a little— I'm going to talk a little about I mean, yeah. Okay, so the Google PageRank algorithm, this is— maybe I'll say something about that. You can think of— and this is a simplification. If I type in Draper University, you can think of— and I'm at Google, and how does it know to bring up the page of Draper University? Well, we sort of know it's because there are lots of links that point to that. But really, You can think of it— if you imagine all of the websites in the world that mention Draper University, and imagine yourself following links from those pages and just following at random. The page that the Google PageRank returns to you is the one that you're most likely to be sitting at if you just move around at random in that Markov chain, roughly speaking. OK. Okay, so here's a little— this is a toy example. It gives an idea of how it works. So let's say I've got a casino that's occasionally dishonest. So just a simple dice game, I throw 1 through 6, and they're switching the dice on me. So every once in a while, they change it so that I roll a 6 with probability 1/2 rather than 1/6, and then they bump down these probabilities, okay? And so— I'm interested— if I see a sequence of rolls, I don't— I know that this is what they're doing, but I don't know what state I'm in, okay? All I'm allowed to do is look at the rolls that come up. And then I have to decide, are they cheating or not? Are they using the fake die or not? This is a typical problem. So you're allowed to look at this, you know you have a model, and you're trying to figure out what states you were in. And so I actually coded— I actually did this one. And this thing's called the Viterbi algorithm. It will figure out— It will figure out for a specific set of observations what's the most likely path you followed. And that's what goes on in the cell phone too. So here's what I rolled, and this is whether it was loaded or fair, and this is what the Viterbi algorithm predicted underneath. And it almost got it exactly right. The only thing it missed was the very first one. So speech recognition, this is used in all kinds of stuff. Bioinformatics. OK, this is even— let's say you don't know what the model is. You don't know what the states are. You don't know what the transitions are. There are even algorithms for that. If you just have some notion of how many states you want, you don't even know how they fit together, there's an algorithm. If you have enough observations, you can build the Markov chain. OK. Automatically. Okay, so this is kind of a joke example. Okay, so I took this list of company names. This was probably at least 8 years ago. I took this list of real company names and I made a Markov chain on it. So what it did is I took all the sequences of 3 letters. So here's Linear Technology, TEC. So I would take that, TEC. D-A-T, and I say take all those sequences, throw them in a bag, and then based on 2 letters— so if I see like T-E followed by C, I might see T-E followed by something else. Like here's T-E-R in international. So if I start with T-E, I choose R or C as the next letter with the observed probability. And then I call this thing the company name generator. Okay. And so you could go to this thing and it'll just spit out fake company names that sort of look like real company names. And I explain it more here, but there's no need. So this is sort of what the states of the model look like. You've got states where there are sort of 2 letters and transitions out that have single letters. And I put this up on the web, and this is example output. I put this thing up on the web and I think it was the first company name generator ever on the web. And at the same time, I was trying to understand how the Google advertising thing worked. I had never used it, and I just wanted to know how a person went about placing ads on a website. So I put a Google ad on this page, and then I forgot about it. In order to get the account, I had to give my checking account number or something. And then it was like 4 months later, I had $10,000 in my checking account. People had clicked— people were clicking on this thing at the rate of like 4,000 a day. And each one of those I was getting $0.10. So after that— then after this happened, somebody— in the next year, a lot more people started doing this. And now if you type in company name generator, I think you'd have to type in my name to actually find this thing. It's been buried by much superior versions of the same thing.