1
00:00:00,000 --> 00:00:04,052
Hi, in this set of lectures we're going to
talk about something called Lyapunov
2
00:00:04,052 --> 00:00:09,027
functions and what the Lyapunov functions
are, is they're functions that really can
3
00:00:09,027 --> 00:00:13,074
be thought of as mapping models into
outcomes in the following way. So what we
4
00:00:13,074 --> 00:00:18,020
can do, is we can take a model or take a
system and we can ask ourselves, can I
5
00:00:18,020 --> 00:00:22,061
come up with a Lyapunov function that
describes that model or describes that
6
00:00:22,061 --> 00:00:27,070
system. And if I can, then I know for sure
that system goes to equilibrium. So what a
7
00:00:27,070 --> 00:00:32,081
Lyapunov function is, is it's this tool,
it's this incredibly powerful tool to help
8
00:00:32,081 --> 00:00:37,086
us understand, at least for some systems,
whether they go to equilibrium or not. Let
9
00:00:37,086 --> 00:00:42,087
me explain what I mean a little bit more.
Remember how we talked about, there's four
10
00:00:42,087 --> 00:00:46,097
things a system can do. It can go
equilibrium, it can cycle, it can be
11
00:00:46,097 --> 00:00:51,025
random. Or it can be complex. Lyapunov
functions, if we can construct them,
12
00:00:51,025 --> 00:00:55,026
that's going to be one of the challenges.
If we can come up with one, then we'll
13
00:00:55,026 --> 00:00:59,038
know for sure that the system's going to
go to equilibrium. If we can't construct
14
00:00:59,038 --> 00:01:03,039
one, then maybe it goes to equilibrium,
maybe it's random, maybe it's chaos, maybe
15
00:01:03,039 --> 00:01:07,035
it's complex, we don't know. We can't
really say anything. So the challenge here,
16
00:01:07,035 --> 00:01:11,047
the really hard and fun part is coming up
with Lyapunov functions. If you come up
17
00:01:11,047 --> 00:01:15,038
with a Lyapunov function, then you know for
sure, hey, this system's going to a
18
00:01:15,038 --> 00:01:19,060
equilibrium. which is a nice thing to know.
Not only that, we'll see in a minute that
19
00:01:19,060 --> 00:01:23,059
you can see how fast it's going to
equilibrium. So, how does it work? Here's
20
00:01:23,059 --> 00:01:28,053
the ideal. Suppose you have a system and
I've got something I care about here which
21
00:01:28,053 --> 00:01:33,029
might be velocity on this axis. And suppose
there's a minimal velocity which is zero,
22
00:01:33,029 --> 00:01:38,010
which I'm representing by this big black
region down here. Now, suppose that I say
23
00:01:38,010 --> 00:01:43,016
the following property holds: I start with
some positive velocity, and every period, if
24
00:01:43,016 --> 00:01:48,015
the velocity changes it goes down. So it's
gonna down to there and then it goes down to
25
00:01:48,015 --> 00:01:52,045
there. Now it could be the velocity
doesn't change, if the velocity doesn't
26
00:01:52,045 --> 00:01:56,083
change then you're fixed, then you're in an
equilibrium, but if the velocity does
27
00:01:56,083 --> 00:02:01,064
change, it has to go down. Well if that's
the case, if it changes it has to go down,
28
00:02:01,064 --> 00:02:06,011
at some point it's going to hit this
barrier down at the bottom, this zero
29
00:02:06,011 --> 00:02:10,058
velocity point. And when it hits zero, it
has to stop, so that's the idea. If
30
00:02:10,058 --> 00:02:15,030
something, if it falls, if it moves, it
has to fall. That's property one, it's got
31
00:02:15,030 --> 00:02:19,076
to go down, if it moves it's got to fall,
and there's a minimum, well those two
32
00:02:19,076 --> 00:02:23,056
conditions are gonna mean that the system
has to stop. With one little, we got to
33
00:02:23,056 --> 00:02:27,040
pick up one little peculiar detail besides
that, but that's basically the idea. If
34
00:02:27,040 --> 00:02:31,025
the system is gonna move, it's got to fall
and there's a min. So therefore at some
35
00:02:31,025 --> 00:02:34,090
point, it's either gonna stop before the
min, like it might fall, fall, fall and
36
00:02:34,090 --> 00:02:38,076
then stop right here, or eventually it
will get the thing at the bottom. That's
37
00:02:38,076 --> 00:02:43,088
the idea. Now, how do economists do it?
Economists do the opposite. They have
38
00:02:43,088 --> 00:02:49,080
something where maybe this is happiness on
this axis. And maybe people are making
39
00:02:49,080 --> 00:02:53,082
trades. And you say, people trade,
happiness goes up. So, I've got happiness
40
00:02:53,082 --> 00:02:57,073
here. People trade, it goes up. People
trade, it goes up. So any time people
41
00:02:57,073 --> 00:03:01,096
trade, total happiness goes up, otherwise
they wouldn't trade. So that means any
42
00:03:01,096 --> 00:03:06,015
time the system moves, happiness is
increasing. But, you've got this caveat
43
00:03:06,015 --> 00:03:11,014
that there is a maximum happiness here, it
can't go above this black bar. So what
44
00:03:11,014 --> 00:03:15,077
does that mean, if anytime people trade it
goes up. And at, and at some point, you're
45
00:03:15,077 --> 00:03:19,017
gonna hit this bar, that means the
process has to stop. And if it has to
46
00:03:19,017 --> 00:03:22,062
stop, that means it's at an equilibrium,
where there's no more trade.
47
00:03:22,062 --> 00:03:26,054
Everybody's happy with what they've got.
So there's these two in substance identical
48
00:03:26,054 --> 00:03:31,033
ideas, right? One is from physics, that if
things fall every period and there's a
49
00:03:31,033 --> 00:03:36,019
min, the process has to stop. And then
from economics, you have where things go
50
00:03:36,019 --> 00:03:40,065
up every period, and there's a max. It has
to stop. That's it, that's the theorem. I
51
00:03:40,065 --> 00:03:44,022
know it sounds sort of frightening, right?
Lyapunov, it sounds really scary, and I'm
52
00:03:44,022 --> 00:03:47,069
sure when you looked at the syllabus, you
thought, oh my gosh, Lyapunov functions!
53
00:03:47,069 --> 00:03:51,013
This is gonna be hard. Maybe I'll skip
this lecture. I thought about calling it
54
00:03:51,013 --> 00:03:54,012
Dave functions, or Maria functions,
because then it wouldn't sound so
55
00:03:54,012 --> 00:03:57,056
frightening if I said, we're gonna study
Maria functions, you know, so, ha, that's
56
00:03:57,056 --> 00:04:00,081
probably gonna be pretty easy, or Dave
functions. It's just that with these
57
00:04:00,081 --> 00:04:04,020
Russian surnames, you sorta think, oh my
goodness, this is frightening. It's not,
58
00:04:04,020 --> 00:04:08,035
very, very easy. Here's the formal part.
What we do is we say there's a Lyapunov
59
00:04:08,035 --> 00:04:12,055
function if the following holds:
First, I just have some function F, and
60
00:04:12,055 --> 00:04:16,098
I'm gonna call this a Lyapunov function.
And there's just three conditions. The
61
00:04:16,098 --> 00:04:21,040
first one is, it has a maximum value. I'm
gonna do the economist's version. In the
62
00:04:21,040 --> 00:04:25,082
physics version, I'd say there's a minimum
value. So there's a maximum value. Second
63
00:04:25,082 --> 00:04:30,041
assumption, there is a k bigger than zero.
So there's some number k bigger than zero,
64
00:04:30,041 --> 00:04:34,062
such that, if xt+1 isn't equal to xt. So
what that means is if-- F is
65
00:04:34,062 --> 00:04:38,076
gonna basically map the state now to
xt into xt+1. If they're not equal,
66
00:04:38,076 --> 00:04:44,024
alright, so if the state in time t plus one is
not equal to the time the state at time t
67
00:04:44,024 --> 00:04:49,071
then F of xt+1 is bigger than F of
xt+k. What does that mean in words,
68
00:04:49,071 --> 00:04:54,046
not in math? What it means is, if it
increases, if it's not fixed, that the
69
00:04:54,046 --> 00:04:59,073
point is not fixed, then it increases by at
least k. Just by some fixed amount. It
70
00:04:59,073 --> 00:05:05,014
doesn't always have to increase by exactly
k, it can increase by more. But it's got
71
00:05:05,014 --> 00:05:09,081
to be increased by at least k. If those
things hold, so it's got a maximum, you're
72
00:05:09,081 --> 00:05:14,017
always going to be increasing by at least
some amount k, then at some point
73
00:05:14,017 --> 00:05:18,053
the process has to stop. Because if it
didn't stop, you would keep decreasing by k
74
00:05:18,053 --> 00:05:22,095
and would go above our maximum. That's the
theory. Now what does this assumption do?
75
00:05:22,095 --> 00:05:27,015
What is this thing about, it's gotta be--
Before I just said, it has to be bigger; now I've got,
76
00:05:27,015 --> 00:05:31,056
it's gotta be bigger by plus k. What's
going on? Well this goes back to something
77
00:05:31,056 --> 00:05:35,082
way back in philosophy called Zeno's
paradox and Aristotle's treatment of this
78
00:05:35,082 --> 00:05:40,019
is probably the one most of you learned
in college, and that is: suppose I want to
79
00:05:40,019 --> 00:05:44,058
leave this room, suppose I'm gonna leave
this room right here and the first day I'm
80
00:05:44,058 --> 00:05:48,070
standing right here. Here I am, da-ta-da,
and the first day I go half way to the
81
00:05:48,070 --> 00:05:53,009
door. Then before I get half, and then the
next day go another half way. And then the
82
00:05:53,009 --> 00:05:57,042
next day I go another half way, The next
day another half way, The next day another
83
00:05:57,042 --> 00:06:01,010
half way. I'd never actually leave the
room. Well, if I don't assume, cause
84
00:06:01,010 --> 00:06:04,078
what's happening here is I'm going up a
half and then a quarter, and then an
85
00:06:04,078 --> 00:06:08,075
eighth, and then a sixteenth. So if I made
my steps smaller and smaller and smaller
86
00:06:08,075 --> 00:06:12,058
and smaller and smaller and smaller and
smaller, it could be that I continue to
87
00:06:12,058 --> 00:06:16,084
increase, but I never actually get to the
maximum. But if instead, I assume that
88
00:06:16,084 --> 00:06:22,005
each step has to be at least 1/16. Well
then after sixteen steps, I'm going to be
89
00:06:22,005 --> 00:06:26,099
out of the room. So what Zeno's paradox is
that you can basically keep making steps halfway, and
90
00:06:26,099 --> 00:06:31,016
you'll never actually exit. And the
paradox was that you could keep moving
91
00:06:31,016 --> 00:06:35,090
towards the door but never actually get to
the door. The way we get around that is, we
92
00:06:35,090 --> 00:06:40,036
make this formal assumption that says
there's some k such that, if you move, you
93
00:06:40,036 --> 00:06:44,070
go up by at least k. So in this case I
talked about it being one sixteenth, if
94
00:06:44,070 --> 00:06:49,016
you go by, up by at least one sixteenth,
then in sixteen steps you're out of the
95
00:06:49,016 --> 00:06:53,056
room which, and, since you can't leave the
room, that's a max, what's gonna happen is, the process has to
96
00:06:53,056 --> 00:06:58,055
stop. So that's all there is to it. We
often have function consistent is F, it's
97
00:06:58,055 --> 00:07:03,046
got a maximum value. And then there's
some, if it's the case that the process
98
00:07:03,046 --> 00:07:08,049
moves over time, then in the next period,
you've gone up by at least some amount k.
99
00:07:08,049 --> 00:07:13,052
And since there's this max, you're going
up by at least k each time. Eventually
100
00:07:13,052 --> 00:07:18,081
you're gonna hit that max and the process
has to stop. And there's a bonus we just
101
00:07:18,081 --> 00:07:23,076
got as well, right? If each time I go up
by 1/16th, then in sixteen steps, I'm
102
00:07:23,076 --> 00:07:29,004
gonna have to stop. So you can also say
how fast the process is going to stop, and
103
00:07:29,004 --> 00:07:33,093
that's obviously not a very complicated
calculation at all. Here's the tricky part
104
00:07:33,093 --> 00:07:38,071
[laugh] about this, the hard part about
this is constructing the function. So the
105
00:07:38,071 --> 00:07:43,037
theory, the idea that there's a function,
there's a max, we go up by k each time,
106
00:07:43,037 --> 00:07:48,038
that's really straight forward. The really
tricky part is going to be coming up with
107
00:07:48,038 --> 00:07:53,016
a Lyapunov function, coming up with that
function F. So what we're going to do in
108
00:07:53,016 --> 00:07:57,026
this set of lectures is, we're gonna
take some processes, things like arms
109
00:07:57,026 --> 00:08:01,010
trading, trading within markets, people
deciding where to shop, and we're gonna
110
00:08:01,010 --> 00:08:04,088
show how, in some of these cases, it's
really easy to construct Lyapunov
111
00:08:04,088 --> 00:08:08,082
functions. In other cases, it's really
hard to construct Lyapunov functions
112
00:08:08,082 --> 00:08:12,076
and, I mean, we can't even construct Lyapunov
functions. So we're just going
113
00:08:12,076 --> 00:08:16,075
to explore how this framework, this
Lyapunov function framework, can help us
114
00:08:16,075 --> 00:08:20,034
make sense of some systems. Help us
understand why some things become so
115
00:08:20,034 --> 00:08:24,038
structured and so ordered so fast, and why
other things still seem to be churning
116
00:08:24,038 --> 00:08:28,038
around a little bit. So the outline of
what we're going to do is, we're just going
117
00:08:28,038 --> 00:08:32,033
to start out by first doing some simple
examples, see how Lyapunov functions
118
00:08:32,033 --> 00:08:36,038
work. Then we're going to move on and see
some sort of interesting applications of
119
00:08:36,038 --> 00:08:40,042
Lyapunov functions, maybe when they don't
work. And then from there, we'll go on and
120
00:08:40,042 --> 00:08:44,022
talk about processes that maybe we can't
even decide whether Lyapunov
121
00:08:44,022 --> 00:08:48,017
functions exist or not, some open problems
of mathematics that involve trying to
122
00:08:48,017 --> 00:08:51,099
figure out: does this thing go to an
equilibrium or does thing continually
123
00:08:51,099 --> 00:08:56,010
churn? And then we'll close it up by
talking about how Lyapunov functions
124
00:08:56,010 --> 00:09:00,020
differ from Markov processes. Remember,
Markov processes also went to equilibrium.
125
00:09:00,020 --> 00:09:04,052
We'll talk about how those equilibria are different
from the equilibrium we're talking about
126
00:09:04,052 --> 00:09:08,099
in these Lyapunov functions, and also how
just the entire logic about how the system
127
00:09:08,099 --> 00:09:13,047
goes to equilibrium is different in the
two cases. Okay, so let's get started.