Hi! So we're talking about Lyapunov processes. Lyapunov processes gives us one technique, one tool for possibly determining whether or not the system goes to equilibrium, so it can tell us for sure the system's gonna go to equilibrium. But sort of lingering out there is this question of well, can we always tell? Maybe not using Lyapunov functions, But if we have a system, can we say for sure, hey, does this go to equilibrium or does it not go to equilibrium? Well, that's the question that we're going to take up in this lecture. Does the system go to equilibrium or does it not, or can we even tell? Well, and that's, that's a good question. So what we're going to do is we're going to do this in two ways. We're going to do this in sort of a fun way with some examples and then we'll do something a little bit deeper. We'll see, in fact, that why some processes are very hard to figure out. So here's the fun example and this is called "chairs and offices", and this actually comes from an experience that one of my former students had. So the student had learned about Lyapunov functions in class, and she's working for some firm. And this firm's moving to new offices. And they've also got a whole bunch of new office furniture, and they're trying to decide, how do we allocate the furniture and how do we allocate the offices? So I'm gonna just put furniture in this one category "chairs", and all the offices in a separate category which I call "offices". So allocate the chairs: My students said, well, here's a really great idea. Let's just give each person a chair, just randomly assign each person a chair. We can all hold our chairs, cause these chairs are different. And then, people can just trade. Each person can trade their chair with someone else if they want to. And this will be great, and then the process will stop and we'll be done. And her boss said, you know that seems [laugh] kind of crazy, because we could be trading chairs all day. And she said no, no, we're not going to trade chairs all day because there's a Lyapunov function. Let the Lyapunov function be how happy people are with their chairs. And this is just a simple exchange market. I'm going to only trade with someone else if I'm happier and if they're happier. And so that means happiness is going to go up. Now there's a maximum happiness which would be if everybody had their preferred chair. Now of course, not everybody would get their preferred chair, but there's still definitely a maximum. So if you assume even some small cost of trading, you know, if it takes time and everything else, you've got to push the chairs around, that means happiness is going to go up with each trade. There's a maximum happiness. Process stops. So the boss says, that's a brilliant idea. So we can do that, we can allocate the chairs that way. Well then the boss says, hey, that's such a great idea. We can also do it. You can also do it for offices. We can just randomly assign people offices, and then let people trade. And my student said, that's a terrible idea. [laugh] The boss said, wait a minute. Why is that a terrible idea? It was your idea for the chairs, but now it's a bad idea for the offices. What's going on there? The student says, look, office is different because there's externalities. It's like the North Korea/ Iraq example. So, suppose you mix your boxes, and here's, you know, me right here, and now there's someone, let's suppose there's someone who wears a hat and this person likes to play really loud music. Well when this person and maybe that person wants to be next to this person over here, who's really happy and always whistling. So there's the whistler over here and the loud music person, well the loud music person moves into this center office because the center office, the center cubicle because they want to be near the whistler. So there sitting near the whistler. And they're happy, but now I'm sitting next to this person who plays loud music. So I then, decide to, I would want to move. So I'm gonna move over here, let's say. But maybe when I move over here, maybe I'm someone that, frequently gets out of my cubicle and wanders around, 'cause I like to walk around when I think, 'cause I do do that. Well, this person who's sitting here, she may not like that at all. She may not like people who get up and wander around, 'cause that disturbs her. So when I move here, she may wanna move someplace else. So when you think about allocating offices, I may move someplace to be happier, but that may make other people less happy. In fact, we saw that a little bit in the Schelling model. Right? One person moving can cause other people to move. In the Schelling model, the process eventually stopped. In the office case, depending on the nature of the externalities, maybe it'll stop, maybe it won't stop. So my student could say, here's, well we don't know for the office. This may be undecidable. In order to know whether or not the office relocation thing will stop, we're gonna need to know a lot about how people feel about other people and how much they care about who their office is next to. So that leads to the deep question: When can you decide? And can you always decide? And that's a hard question. The answer is it depends on the problem. So in some cases you can figure out some other way to show or prove that the process goes to equilibrium. Or in some cases you can come up with a really sophisticated Lyapunov function to show the system goes to equilibrium. But other problems, even what seems like incredibly simple problems, it turns out they're very hard to solve. So let me take just a simple instance of this. Can we know that a process stops? This is the question. Let me take just an incredible simple instance of this to show you just how complicated even simple processes can be. This is something called the Collatz problem. The Collatz problem works as follows. I call it "HOTPO", half or three plus one. So the idea is that you pick a number: if it's an even number, divide it in half. If it's an odd number, multiply it by three and add one, and you stop, the process stops if you ever reach one. So pick a number. It's even: divide by two. If it's odd: multiply by three and add one. So it's going to be going down every time you divide. It's going to be going up every time you multiply it by three. And you stop if the process ever reaches the number one. I could ask: Does this process ever stop? Let's do some examples to see how this works. So let's suppose we start with five. Five's odd, so I'm gonna take three times five plus one, so that's sixteen. Then I divide--that's even--so I divide by two, that's eight. That's even: I divide by two, that's four. That's even: I divide by two, that's two. That's even: I divide by two, that's one, process stops. Let's take seven; that's odd, so I multiply by three, three times seven plus one, so it's 21, that's 22. That's even, so divide by two, that's eleven. That's odd, so we multiply by three and add one, that's 34. And I divide by two, that's seventeen, that's even. And it's odd, so I multiply by three. And add one, that's 52. Even, so I divide by two. Even, divide by two, that's thirteen. Odd, I multiply by three and add one, that's 40. That's even, twenty. Even, ten. Even, five. And once I get to five, I know, look, sixteen, eight, four, two, one. Process stops. So I start with five, I get to one pretty quickly. When I start at seven, I get to one but it takes a long time. Why don't I start with 27, start with a bigger number. Well, you see, whoa, this process seems to take an incredibly long time, it's no longer a really simple process. Turns out that this is a very hard problem. In fact, the mathematician Paul Erdős, he's one of the great number theorists ever, said, "mathematics is not yet ripe for such problems". In other words, mathematics as a subject hasn't matured enough to be able to solve this. We can put a man on the moon, but we can't solve the Collatz problem, sort of amazing. Just to give you a sense of how complicated this is, here's a graph of from Carnegie Mellon of all the numbers up to 2000 on this axis. And this is how many periods it takes them to stop in the Collatz problem. So, what you see is, you see, wow, there's a lot of structure in here. There seems to be one set of numbers that sort of goes like this, and then another set of numbers that sort of has this pattern, but it seems really interesting and hard to figure out. Well, that's why we don't know. Because it's so interesting and hard to figure out, we can't tell whether the Collatz problem stops, and we probably can't tell where the office problem stops. But we can tell whether the chair problem stops. That's what's so interesting. So when you think about a model, when you think about a process like the Lyapunov process, right? Lyapunov functions. What you've got is, you can say, hey, there some cases like the case of chairs, a pure exchange market, this thing works great. And we can just can say, boom, it's gonna stop, we're fine. There's other things like the office process, that unless you know a lot about the nature of the externalities, you can't tell. It could be, oh yeah this thing's gonna go right to equilibrium. Or it could be that, whoa it's gonna churn a long time. Like the number 27 did, alright where it just goes and goes and goes and goes and goes when we put in the Collatz process or HOTPO process. Okay thanks.
