Hi. In this set of lectures, we're talking about Lyapunov functions. And Lyapunov functions give us a way to explain or understand why some processes go to equilibrium. What I wanna do in this very short lecture is just clean up two details, two questions that might be out there lingering in the minds of people. The first question is this: Can we say how long it's gonna take the process to go to an equilibrium? So we know it's going to an equilibrium. Can we say exactly how fast? We'll talk about that. And then second: Does the process always stop at the max or the min? So, remember when we talked about Lyapunov processes, they can either always be going up or always be going down, until they reach an equilibrium. The question is, if they're going down, do they automatically hit the floor? Do they necessarily hit the floor? Could they stop above it? And if they're going up, do they necessarily hit the top or could they stop below it? That's the second question. Both pretty straightforward. Both fairly easy to answer, but it's worth cleaning up those details. Let's look again at the formal definition of the Lyapunov function, just so we can answer these questions precisely. So some function F, it has a maximum value. If the process stops, then it's in equilibrium. If it doesn't stop, then its value according to [inaudible] increases by some amount that has a value, by some amount at least k. So it goes up at least k. So that means that either the process is stopped or it's going up k. And since there's a maximum, that means that at some point the process has to stop. So now I also get this question: How long until the process reaches equilibrium? That's really a fairly easy question to answer. Suppose that we start out with F of x1 equals 100, and k equals 2. So that means that the original value of the function is 100, k equals 2, then I suppose the maximum equals 200. So that means starting out at 100, the highest you can go is 200, and it's got to go up at least 2 each period. Well, what we can say is, is that the number of periods has to be less than 50, because it's gotta go up at least two, and the most it can go up is 100, and so 100 divided by 2 equals 50. So what we get is, the maximum number of periods is 50. So when we write down Lyapunov function, if we could make k as big as we can possibly make it and make the maximum as small as we can possibly make it, then we can put a bound on the number of periods. We can't say for sure. The process could stop in one period. It could stop in two periods. It could stop in 47 periods. But we can say for sure, is that the number of periods is going to be less than 50. Now could be, if I think really hard about the model, I realize that, you know what, k is not 2, but actually k is 4. That I can show, it's got to go by at least 4 each period. Well, if that's the case, then instead of the number of periods being less than 50, you could show it's less than 25. So if you want to put as tight a bound as you possibly can on the time it's going to take the Lyapunov process to converge, what you want to do is: make k as big as you can make it, and make that maximum value as low as you can make it, and that will help you make a tighter bound on how many periods it's going to take to get to equilibrium. But putting that bound on once you know k and the maximum value and [inaudible] minimum value as well. The starting value is really straightforward, it's just some really simple algebra. The other question is a little bit harder. That is, does the process necessarily reach a max or minimum. And the answer here is going to be no. Now that first reading where people were choosing routes, in terms of where to go in the city. That one it did go to a minimum, it did go to an efficient case always. We didn't prove it but you can show that that's true. But generally that's not going to be the case, generally it can be the case that a process can get stuck someplace less than the max. So I'm going to explain this in two ways. Let's go back and talk about a rugged landscape model. Remember, in a rugged landscape model there were peaks, so here's a peak, here's a peak, here's a peak. You can think of a Lyapunov function as saying, I'm going to step up at least some distance each period. It doesn't necessarily mean that you're gonna get to the highest peak. You could just go up a particular hill, and it could be a suboptimal peak. It doesn't seem necessary that these processes would take you to the maximal point, take you to the optimal point. Again, there's a difference between metaphor, and actually having a mathematical example. So let's see if we can come up with an example to show where we get stuck at less than the optimal point. To do that we're gonna go back to our preference model. So you might be noticing at this point, "uh-oh, I better have paid attention to the earlier lectures", cause you've done Langton's model, now we're gonna do the preference model. So remember in the preference model, individuals had preference over different things. So person one here. Here's person one. Person one. They like apples more than bananas, more than coconuts. And here's person two. And they like bananas, coconuts, and then apples. And then, here's person three. They like coconuts, apples, and then bananas. Let's suppose the following is true: Person one has a banana. Person two has a coconut. And person three has an apple. And now we're going to have an exchange market. We're going to ask, do they want to trade? Can they trade to make themselves happier? Well, it's clear they could trade and make themselves happier, but let's see if they can do it. So person one is saying, "but I would like to have the apple". Person one goes over to person three and says, "hey, how about if I give you this banana for your apple". And person three says, "a banana? No way, 'cause I like apples more than bananas." So they reject the trade. So person one can't make any trade that makes him better off. Person two has the coconut, but they'd rather have the banana. So they go to person one whose got the banana and says, "hey person one, would you like to have my coconut? How about my coconut for your banana?" And person one says, "the coconut? No way. I like my banana more than the coconut. So forget it." So no one's, person one is not going to trade with person two. Now person three has got the apple, and they'd like person two's coconut. So they go to person two and say, "hey person two, how about if I give you my apple for your coconut?" And person two looks and says, "the apple? Forget it, I like my coconut more than the apple, I'm not gonna trade with you." So what we've got here is a situation where person one has the banana, person two has the coconut, person three has the apple, none of them can make a pairwise trade and be better off. One way to understand that metaphorically, right, is to think, here's the landscape where they've got these certain things. They got, they're stuck at this point. There's some place they could get, they could be better. It could be that if person one had the apple, person two had the banana, person three had the coconut, they'd be better off. But they can't get there by pairwise trades. They could do it if they had a more sophisticated trade, where they put all three things on the table and each person grabbed the thing they wanted. But through pairwise trades, they don't get there. So what have we learned? What we learn is that it's at least possible to put a Lyapunov function on a process and have it stop at somewhere less than the optimal point. Doesn't have to stop at the optimal point, it could stop below. That's what we're seeing here. So we've answered two important questions. The first one is: Okay, we know it goes to equilibrium, can we say how fast? And the answer is yes. And the better bound we get on k, and the better bound we get on the max, the more accurately we can put a restriction on how fast, how long it's going take. So, we can put a tighter bound on how long it's going to take, if we can estimate k accurately, and if we can estimate the maximum value accurately. We also learned that it can stop a lot faster than that, because of the fact that the process may not get to that optimum value. Some processes get stuck in suboptimal points, and at least metaphorically, you can understand it's being stuck in a landscape, at a suboptimal peak, instead of climbing the mountain, you're getting stuck somewhere below the optimal point. Okay, where we're going to go next, is we're going to talk about another lingering question. And that is, are there processes where we don't know whether they go to equilibrium or not? And the answer to that, surprisingly, is going to be, yes. There's some where it's just sort of hard to figure out. [laugh] All right? Thanks.
