Hi. Welcome back. And I want to conclude our discussion and analysis of Lyapunov

functions, and I want to do so in a particular way. I want to contrast

Lyapunov functions with Markov processes, which we previously studied. 'Cause Markov

processes also went to equilibria. But there's some fundamental differences

between the equilibria we described with Lyapunov functions and equilibria we

described with Markov processes. Now remember the broader context here is, when

we look out there in the world, look at a system, there's lots of things that can

happen: the system can go to equilibria, the system can be ordered, it can be

random, or it can be complex. Those are the four things that we can get, and both

Markov processes and Lyapunov functions gave us, sort of, conditions

under which we can say for sure, this system is going to go to equilibrium. For

a Lyapunov function it was really simple, right? We just had that, there's a

function F, it has a maximum value, in this case it's a minimum value. If there's

a maximum value, if the process isn't in equilibrium it goes up by some fixed

amount k. That means since it's always going up by some fixed amount k, it has to

stop. Really simple idea. So it's a way, if we can construct the function, to say

that the system's going to equilibrium. Now Markov process was a very different

thing. The system went in some finite number of states. They could be high

values, low values, whatever, and it moved between those states. And our assumptions

were that the probability of moving between those states stayed fixed over time, and it

was possible to get from any one state to any other. That was assumption three. And

then the third [sic] assumption was, there was no simple cycle. So then you just go like

ABC, ABC, ABC. Given those assumptions, we had the Markov Convergence Theorem that

said, the system goes to an equilibrium. Remember, it goes to a stochastic

equilibrium. So it goes to some equilibrium, if the states are A, B, and C,

it may go to some equilibrium like 1/2, 1/4, 1/4. So half the time

it's in A, a quarter of the time it's in B, a quarter of the time it's in C. So,

it's a stochastic equilibrium. The system's churning, there's equilibrium a

percentage of the time it stays in those three states. And moreover, that

equilibrium is unique. So if I have a Markov process, history doesn't matter.

Initial point doesn't matter. None of those things matter. It's gonna go to this

stochastic distribution over these three states, regardless of where you start.

Very different from a Lyapunov function, Lyapunov function could be highly path

dependent. It could depend a lot, also, on the initial conditions. So it could depend

on where you start and where you go. So there could be many, many equilibria. So

there's no reason to assume that it's gonna be unique if you put a Lyapunov

function on a process. It could, there's lots of equilibria. There could be

lots, [inaudible], it isn't necessary, but there could be. Second thing is, it's not

a stochastic equilibrium. It's not, half the time you're in A, quarter of the time

you're in B, quarter of the time you're in C. It's a fixed point. It's a fixed, you

know, allocation of places where people go shop, you know, time periods that people

go shop, it's a fixed set of trades among people. So the system stops. Whereas in a

Markov process, the system keeps churning. So this, this structure we had

for Lyapunov functions, right, maximum value keeps going up, is

fundamentally different than the structure we had for Markov processes. Both go to

equilibrium, but they go to types of equilibrium. Let's remind ourselves just some

of the things we've learned though, about these processes on which we can place

Lyapunov functions. First is, if you can construct the Lyapunov function, then it

goes to equilibrium. Now if you can't, that doesn't mean it doesn't, but if you

can, then it does. That's the first, so when you look at a process, one thing you

might do is just sit there and think, huh, can I place a Lyapunov function on this?

So in the case of my student with the chairs, yes she could. In the case of the

offices, no she couldn't. So she could say with great conviction, "hey, let's do this

trading thing with the chairs", but she could be skeptical of whether the same

procedure would work with the offices, because she couldn't think of a Lyapunov

function. Second: If you can compute, if you can write down a Lyapunov function,

you can figure out how long it's going to take. So you can say: this is going to go

to equilibrium and it's going to go pretty fast. Or you can say, it's going to go to

equilibrium, it could take a long time. So you can bound how long it's going to take

to go to equilibrium. That's also good. Third thing, right, just talked about this,

that equilibrium need not be unique or efficient. So it could be many equilibria,

it could be bad equilibria, all you know is it's going to go to equilibrium. To

prove it's a good equilibrium requires other techniques. It's gonna require a

deeper analysis. All the Lyapunov function will tell you is, is it gonna go to an

equilibrium, and how fast? And then, last: The reason a system won't go equilibrium

is because there's externalities. And even more than that, I can even be more specific

here: there are sort of externalities pointing in the other direction. So

pointing opposite. So if you are trying to increase happiness, if the externalities

cause people to become less happy, that's gonna keep the system churning. If you're

trying to minimize waiting time and the externalities increase waiting time, that's

gonna keep this system churning. So it's not just externalities, it's externalities that

point in the opposite direction. That's what cause, that's what causes a system

not to have a Lyapunov function, and that's what makes it possibly undecidable.

So let's think back to the HOTPO case, the Collatz problem. Remember, that was "half

or three plus one". So some of the time it was going down by half, and other times it

was going up by three plus one. So we had a system that is going up and down. Systems that

go up and down, you can't necessarily say their gonna go to equilibrium. It's those

externalities that point in the opposite direction that cause a system that's

trying to go down, to go up, or a system that's trying to go up, to go down. And

it's externalities that prevent equilibrium. That's the same lesson we

learned, remember, from the Langton lambda in that very simple cellular

automata model. When we have externalities, when one person's action

or one cell's action depends on the actions of others, so if my happiness

depends on other people's actions, the system's likely to churn. When what I do

is unaffected by other people, so my happiness is unaffected by the actions of

others, then I'm likely to get a system that equilibrates. That's it. You know

[laugh] we're done now with Lyapunov functions. There's a lotta really cool

stuff. And it's a really nice framework for just thinking about systems. So you

just think about, let's just set something loose. You think, oh boy, have I just set

something loose that's gonna go crazy? Or have I set something loose, that's just

gonna very smoothly, lead to a nice equilibrium? One way to get some insight

into that is through Lyapunov functions. Now, what's nice though about this as well, is,

by looking at Lyapunov functions and comparing it to some of our other models,

like Markov processes and the Langton model, we begin to see how having multiple

models in our heads enables us to understand some of the richness we see out

there in the world, and actually have deeper understandings of the processes we

see. To understand, like, this process is going into equilibrium because it's a

Markov process, and it's a stochastic equilibrium. And this process, an exchange

market, is going to equilibrium because of the fact that it's a Lyapunov

function and happiness is going up. So what you get is different processes in

that equilibrium for very different reasons. And having different tools for

understanding why equilibrium exists is [a] very useful thing for making sense of the

world. Which is one reason why we model. Okay, thanks.