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.