1
00:00:02,334 --> 00:00:05,516
The summary for this unit will come in two parts
2
00:00:05,516 --> 00:00:09,513
in the first part I’ll collect some of the definitions and terminology
3
00:00:09,513 --> 00:00:14,648
key results and arguments that I went over in the many videos in this section
4
00:00:14,648 --> 00:00:16,541
and then in the second part of the summary
5
00:00:16,541 --> 00:00:18,902
I’ll take a step back and talk about what I think some of
6
00:00:18,902 --> 00:00:22,167
these results mean why they are interesting and important
7
00:00:22,167 --> 00:00:24,116
and why they’re fun to think about
8
00:00:24,116 --> 00:00:26,515
so let’s get start it
9
00:00:29,585 --> 00:00:32,718
so let’s summarize what we did in Unit 3
10
00:00:32,718 --> 00:00:38,017
Unit 3 was on chaos and butterfly effect
11
00:00:38,017 --> 00:00:41,583
I began by introducing a logistic equation
12
00:00:41,583 --> 00:00:43,496
and I went through a derivation talking about
13
00:00:43,496 --> 00:00:46,259
rabbits on an island and annihilation values
14
00:00:46,259 --> 00:00:49,971
but the main thing is that the logistic equation is a very simple model
15
00:00:49,971 --> 00:00:53,097
of population growth where there’s some limit to the growth
16
00:00:53,097 --> 00:01:00,082
there’s some maximum population beyond which the population can’t pass
17
00:01:00,082 --> 00:01:02,460
we ended up with this form
18
00:01:02,460 --> 00:01:04,869
perhaps the most famous or
19
00:01:04,869 --> 00:01:09,200
one of the most two famous equations in the study of chaos
20
00:01:09,200 --> 00:01:11,571
f of x r x 1 minus x
21
00:01:11,571 --> 00:01:14,465
and we interpret r as a growth parameter
22
00:01:14,465 --> 00:01:18,926
and x is measured as a fraction of the annihilation parameter
23
00:01:18,926 --> 00:01:25,803
so it’s some fraction of the maximum possible number of rabbits or whatever
24
00:01:25,803 --> 00:01:28,160
and this function f of x we can iterate it
25
00:01:28,160 --> 00:01:30,460
and it gives us the population next year
26
00:01:30,460 --> 00:01:32,811
f of x is the population next year
27
00:01:32,811 --> 00:01:36,245
given that x is the population this year
28
00:01:36,245 --> 00:01:38,303
so we have results of the function
29
00:01:38,303 --> 00:01:42,651
and we can now iterate this function like we did it Unit-1
30
00:01:43,934 --> 00:01:48,468
to do so we turn to an online program
31
00:01:48,468 --> 00:01:50,684
that will iterate the logistic equation
32
00:01:50,684 --> 00:01:53,870
you enter r you enter some initial conditions
33
00:01:53,870 --> 00:01:57,350
and it will make a time series plot and show you the numbers
34
00:01:57,350 --> 00:01:59,752
and so here is just one sample output for that
35
00:01:59,752 --> 00:02:03,142
hopefully you’ve experimented with this a bunch by now
36
00:02:03,142 --> 00:02:07,357
and we found attracting periodic behavior of different periodicities
37
00:02:07,357 --> 00:02:10,537
period 2 period 3 period 4
38
00:02:10,537 --> 00:02:14,159
and we’ll see that there’re more period as well
39
00:02:16,389 --> 00:02:17,637
and then we found something else
40
00:02:17,637 --> 00:02:20,541
something that I hope it was surprising and kind of fun
41
00:02:20,541 --> 00:02:26,651
and that is for r equals 4 and also for some other values the orbit is aperiodic
42
00:02:26,651 --> 00:02:30,685
here’s an example of what that look like the orbit doesn’t hit some regular cycle
43
00:02:30,685 --> 00:02:34,479
it just keeps bouncing around all over
44
00:02:34,479 --> 00:02:37,553
so for this the orbit never repeats
45
00:02:37,553 --> 00:02:40,110
so applying the same function over and over again
46
00:02:40,110 --> 00:02:42,726
doing this incredibly repetitious process
47
00:02:42,726 --> 00:02:45,080
always produces in somethings somethings new
48
00:02:45,080 --> 00:02:50,720
it does not the orbit does not settle in to periodic behavior
49
00:02:50,720 --> 00:02:53,934
so that was kind of weird and perhaps little bit surprising
50
00:02:53,934 --> 00:02:58,088
and then things got thing hope even more interesting
51
00:02:58,088 --> 00:03:03,745
so we started thinking about comparing the orbits for two different initial conditions
52
00:03:03,745 --> 00:03:06,576
so we used the similar but different online program
53
00:03:06,576 --> 00:03:10,790
to compare the time series for two initial conditions
54
00:03:10,790 --> 00:03:12,440
and here is what the output for that just
55
00:03:12,440 --> 00:03:15,078
for some sample values might look like
56
00:03:15,078 --> 00:03:18,090
start with two different initial conditions and
57
00:03:18,090 --> 00:03:21,213
they both end up at the same fixed point
58
00:03:21,213 --> 00:03:25,364
I don’t know around .8 or .6 whatever it is
59
00:03:25,364 --> 00:03:27,534
and then in this bottom plot
60
00:03:27,534 --> 00:03:31,970
I plotted the difference between these two time series
61
00:03:31,970 --> 00:03:36,002
so the difference starts off large and negative
62
00:03:36,002 --> 00:03:41,257
and the difference decreases in the sense that it gets closer and closer to zero
63
00:03:41,257 --> 00:03:46,692
so this is showing us that these two orbits that start far apart .7 apart or so
64
00:03:46,692 --> 00:03:49,981
end up getting closer and closer together and reach the same fate
65
00:03:49,981 --> 00:03:53,439
they end up here together
66
00:03:57,296 --> 00:04:00,578
then we tried making a similar plot when r equals 4
67
00:04:00,578 --> 00:04:03,531
that was the aperiodic case
68
00:04:03,531 --> 00:04:07,058
here we saw that two orbits that start very close together
69
00:04:07,058 --> 00:04:09,607
eventually end up very far apart
70
00:04:09,607 --> 00:04:12,595
here the two orbits are right on the top of each other
71
00:04:12,595 --> 00:04:15,807
there’s so similar one blots out the other
72
00:04:15,807 --> 00:04:21,326
and then they start to pull apart here
73
00:04:21,326 --> 00:04:23,103
this curve down below is plotting
74
00:04:23,103 --> 00:04:25,527
the difference between those two initial conditions
75
00:04:25,527 --> 00:04:28,822
it starts very small and then becomes very large
76
00:04:28,822 --> 00:04:33,128
and this phenomenon is known as sensitive dependence on initial conditions
77
00:04:33,128 --> 00:04:36,234
or more popularly as the butterfly effect
78
00:04:36,234 --> 00:04:38,931
the idea is that okay it depends very sensitively
79
00:04:38,931 --> 00:04:43,599
the long term behavior of the orbit depends very sensitively on the initial condition
80
00:04:43,599 --> 00:04:47,776
and a very small initial change perhaps something as small as
81
00:04:47,776 --> 00:04:50,045
might result from a butterfly flapping its wings
82
00:04:50,045 --> 00:04:54,666
could make a large difference down line
83
00:04:59,096 --> 00:05:04,493
so again just say that a different way sensitive dependence on initial conditions
84
00:05:04,493 --> 00:05:08,968
I gave a formal mathematical definition of it which basically boils down to this
85
00:05:08,968 --> 00:05:13,869
for any initial condition x, there is another nearby initial condition
86
00:05:13,869 --> 00:05:17,140
very very close to it that eventually ends up far away
87
00:05:17,140 --> 00:05:21,618
so the initial conditions are always getting pushed away from each other
88
00:05:21,618 --> 00:05:26,779
so to predict the behavior of a system with sensitive dependence on initial conditions
89
00:05:26,779 --> 00:05:30,936
would require knowing the initial condition with impossible accuracy
90
00:05:30,936 --> 00:05:36,224
so we saw an example that to predict the Lorenz equation how to t equals 18
91
00:05:36,224 --> 00:05:42,855
we get very different results if the initial condition varies by
92
00:05:42,855 --> 00:05:49,161
what was it 2 nanometers or 10 nanometers out of 15 meters
93
00:05:49,161 --> 00:05:53,333
so such precision is needed such accuracy as mean needed
94
00:05:53,333 --> 00:05:55,359
that not only it is a practically impossible
95
00:05:55,359 --> 00:05:58,826
but it’s perhaps even theoretically meaningless
96
00:05:58,826 --> 00:06:04,504
the bottom line is that systems with sensitive dependence are deterministic
97
00:06:04,504 --> 00:06:07,135
yet nevertheless they’re unpredictable in the long run
98
00:06:07,135 --> 00:06:11,056
and usually even in the medium run
99
00:06:15,694 --> 00:06:19,776
sensitive dependence on initial conditions means that the orbit
100
00:06:19,776 --> 00:06:23,380
that a computer calculates for us actually isn’t the true orbit
101
00:06:23,380 --> 00:06:25,777
we thought we were calculating
102
00:06:25,777 --> 00:06:29,721
computers have to round off numbers and have finite precision
103
00:06:29,721 --> 00:06:34,505
and so the orbit that a computer gives us is not the true orbit for that initial condition
104
00:06:34,505 --> 00:06:36,415
and that may be worrying we might wonder
105
00:06:36,415 --> 00:06:39,745
what is the computer showing us then is a complete nonsense
106
00:06:39,745 --> 00:06:43,043
and it turns out that the computed orbit
107
00:06:43,043 --> 00:06:45,261
it’s not that orbit we thought we were getting
108
00:06:45,261 --> 00:06:49,607
but it’s arbitrarily close to some other true orbit for the dynamical system
109
00:06:49,607 --> 00:06:52,794
it’s the orbit for a different initial condition
110
00:06:52,794 --> 00:06:56,703
so we would say that the computed orbit shadows some other true orbit
111
00:06:56,703 --> 00:07:00,595
and this result is known as the shadowing lemma
112
00:07:03,795 --> 00:07:09,258
so finally we are in a position to define chaos in the mathematical sense
113
00:07:09,258 --> 00:07:15,165
so we say that a dynamical system is chaotic if the following 4 criteria are met
114
00:07:15,165 --> 00:07:21,276
it’s deterministic which the dynamical systems for studied certainly
115
00:07:21,276 --> 00:07:27,639
are iterated functions and differential equations are deterministic dynamical systems
116
00:07:27,639 --> 00:07:31,573
its orbits need to be bounded they can’t fly off to infinity
117
00:07:31,573 --> 00:07:34,529
the orbits are aperiodic as we saw it was the case
118
00:07:34,529 --> 00:07:37,774
for the logistic equation with r equals 4
119
00:07:37,774 --> 00:07:40,852
and it has sensitive dependence on initial conditions
120
00:07:40,852 --> 00:07:45,104
again as we saw with r equals 4 for the logistic equation
121
00:07:45,104 --> 00:07:52,231
so the logistic equation and iterated function is a chaotic dynamical systems in this sense
122
00:07:57,251 --> 00:08:01,823
so then we turned our attention towards the idea of randomness in this puzzle
123
00:08:01,823 --> 00:08:06,957
that a deterministic dynamical system is producing a random output
124
00:08:06,957 --> 00:08:11,574
so to start thinking about that I first introduced this idea of symbolic dynamics
125
00:08:11,574 --> 00:08:14,457
and so what we do is we convert the orbit which is
126
00:08:14,457 --> 00:08:20,392
a sequence of numbers between 0 and 1 into some symbols
127
00:08:20,392 --> 00:08:22,303
L and R for left and right
128
00:08:22,303 --> 00:08:26,475
we could do 0 and 1 or any two symbols that we wanted
129
00:08:26,475 --> 00:08:29,960
so if x is less than a half we’ll say we’ll turn it into an L
130
00:08:29,960 --> 00:08:35,012
and if x the iterate is greater than a half, we’ll turn it into R
131
00:08:35,016 --> 00:08:39,859
and it turns out that this particular way is way here of converting
132
00:08:39,859 --> 00:08:42,952
the orbit into symbols has this nice property
133
00:08:42,952 --> 00:08:45,298
it’s known as a generating partition
134
00:08:45,298 --> 00:08:48,189
and in brief what this means is that the initial condition
135
00:08:48,189 --> 00:08:51,621
uniquely determines the symbol sequence and vice versa
136
00:08:51,621 --> 00:08:55,072
in the limit that the symbol sequence goes to infinity
137
00:08:55,072 --> 00:08:59,804
so the bottom line is because of this relation
138
00:08:59,804 --> 00:09:02,756
the properties of the symbolic dynamical system
139
00:09:02,756 --> 00:09:05,199
or dynamical system after doing this conversion
140
00:09:05,199 --> 00:09:08,139
in the original dynamical system are the same
141
00:09:08,139 --> 00:09:12,856
and by what I mean by properties are the same is that
142
00:09:12,856 --> 00:09:17,017
the dynamical system in either at symbol form or it’s non symbol form
143
00:09:17,017 --> 00:09:20,878
will have the same fixed points with the same stability
144
00:09:20,878 --> 00:09:23,570
or same number of fixed points with the same stability
145
00:09:23,570 --> 00:09:26,132
if one is aperiodic the other will be
146
00:09:26,132 --> 00:09:31,454
if one has sensitive dependence on initial conditions, the other has too as well
147
00:09:34,074 --> 00:09:38,163
so then I imagined looking at two different systems
148
00:09:38,163 --> 00:09:42,609
a coin toss a random coin toss and the symbolic dynamics
149
00:09:42,609 --> 00:09:46,585
symbol sequences from the logistic equation with r equals 4
150
00:09:46,585 --> 00:09:52,439
and I argued that the logistic equation at r equals 4 is as random as a coin toss.
151
00:09:52,439 --> 00:09:56,986
what I mean by that is that for both the logistic equation and the coin toss
152
00:09:56,986 --> 00:10:00,994
all possible sequences of symbols occur with equal frequency
153
00:10:00,994 --> 00:10:08,419
so all possible sequences of length 2 of length 3 of length 4 and so on occur equally likely
154
00:10:08,419 --> 00:10:11,619
so what this means is if I give you two long sequences
155
00:10:11,619 --> 00:10:16,254
one of which was generated by the logistic equation a deterministic process
156
00:10:16,254 --> 00:10:19,688
and the other I generated by randomly tossing a coin
157
00:10:19,688 --> 00:10:23,896
you could not perform a statistical test that could distinguish between the two
158
00:10:23,896 --> 00:10:28,375
the logistic equation produces a sequence that is statistically identical
159
00:10:28,375 --> 00:10:31,850
to that would be produced by a random coin
160
00:10:35,703 --> 00:10:40,649
so that let us to think even more well what does randomness mean
161
00:10:40,649 --> 00:10:44,514
and one of the key ideas here is we need a separate
162
00:10:44,514 --> 00:10:48,478
the properties of a process and the results of a process
163
00:10:48,478 --> 00:10:55,055
so instead of thinking about randomness as that which occurs by chance
164
00:10:55,055 --> 00:10:57,775
I want to think about randomness in a different way
165
00:10:57,775 --> 00:11:01,048
so sometimes called algorithmic randomness and the key idea
166
00:11:01,048 --> 00:11:04,355
is that a random sequence is one that is incompressible
167
00:11:04,355 --> 00:11:06,634
it contains no regularities or patterns
168
00:11:06,634 --> 00:11:09,966
that I can use to come up with a shorter description of it.
169
00:11:09,966 --> 00:11:12,581
but then we were faced with a puzzle
170
00:11:12,581 --> 00:11:14,876
how can we tell if a sequence is compressible or not
171
00:11:14,876 --> 00:11:17,514
I showed you the binary expansion for pi
172
00:11:17,514 --> 00:11:22,667
and it certainly wasn’t obvious that that binary expansion
173
00:11:22,667 --> 00:11:26,159
could be compressed into just the number pi
174
00:11:26,159 --> 00:11:27,628
so we might wonder well ok
175
00:11:27,628 --> 00:11:30,899
is there an compression algorithm that will always work
176
00:11:30,899 --> 00:11:33,933
and it turns out that there does not exist an algorithm
177
00:11:33,933 --> 00:11:37,553
for finding the best way to compress a sequence
178
00:11:37,553 --> 00:11:39,935
however we can make an argument that
179
00:11:39,935 --> 00:11:44,659
almost all sequences are incompressible and hence random
180
00:11:44,659 --> 00:11:47,431
so let’s go through that argument
181
00:11:49,732 --> 00:11:51,872
so we looked at two sets
182
00:11:51,872 --> 00:11:55,189
the set of all sequences and a set of algorithms
183
00:11:55,189 --> 00:11:57,678
and those sets are both infinite in size
184
00:11:57,678 --> 00:11:59,947
there are infinite number of possible sequences
185
00:11:59,947 --> 00:12:03,362
and an infinite number of possible algorithms
186
00:12:03,362 --> 00:12:06,528
however and I didn’t prove this
187
00:12:06,528 --> 00:12:08,187
but it turns out that there are infinitely
188
00:12:08,187 --> 00:12:10,635
many more sequences than algorithms
189
00:12:10,635 --> 00:12:15,384
in fact there are different types of infinity the number of sequences
190
00:12:15,384 --> 00:12:17,620
what we would say is uncountably infinite
191
00:12:17,620 --> 00:12:20,986
and the number of the algorithm is countably infinite
192
00:12:20,986 --> 00:12:24,005
and so what this means is that they’re vastly vastly
193
00:12:24,005 --> 00:12:26,225
infinite infinite many more sequences
194
00:12:26,225 --> 00:12:28,954
and there are algorithms and each and each algorithm
195
00:12:28,954 --> 00:12:33,951
I’m thinking of as a way to describe or compress a given sequence
196
00:12:33,951 --> 00:12:36,419
so what this means is there cannot possibly be ways
197
00:12:36,419 --> 00:12:38,557
to compress the vast majority of sequences
198
00:12:38,557 --> 00:12:41,293
there simply aren’t enough algorithms compression algorithms
199
00:12:41,293 --> 00:12:43,836
or schemes to go around
200
00:12:43,836 --> 00:12:47,569
so what this means is that a randomly chosen infinite sequence
201
00:12:47,569 --> 00:12:52,332
if you have a gigantic infinite bag that holds this infinite set of sequences
202
00:12:52,332 --> 00:12:56,175
and you just close your eyes and pick one out with probability 1
203
00:12:56,175 --> 00:12:59,596
it will be incompressible in this random
204
00:12:59,596 --> 00:13:04,635
and what I mean by probability one is yes you could get astronomically lucky
205
00:13:04,635 --> 00:13:07,872
and choose one that happen to be compressible
206
00:13:07,872 --> 00:13:10,709
but in the long in the limit of infinite sequences that
207
00:13:10,709 --> 00:13:13,914
would occur the probability of that occurring would be a zero
208
00:13:13,914 --> 00:13:18,232
it’s sort of like saying what’s the probability if you toss a fair coin
209
00:13:18,232 --> 00:13:22,105
and infinite number of times that it always comes up heads
210
00:13:22,105 --> 00:13:25,934
yes there isn’t there is one way that it could come up all heads
211
00:13:25,934 --> 00:13:28,182
but that’s one out of an infinite number
212
00:13:28,182 --> 00:13:35,245
so we’ll say that you are going to get something other than all heads with probability 1
213
00:13:35,245 --> 00:13:40,321
anyway so what bottom line is that
214
00:13:40,321 --> 00:13:44,224
with probability 1 almost always a randomly chosen
215
00:13:44,224 --> 00:13:48,069
infinite sequence is incompressible ie it’s random
216
00:13:48,069 --> 00:13:54,072
now the logistic equation with r equals 4 produces all possible sequences
217
00:13:54,072 --> 00:13:58,692
therefore so in sense that the logistic equation is filling up this bag
218
00:13:58,692 --> 00:14:03,114
I was talking about consisting of all of these random infinite sequences
219
00:14:03,114 --> 00:14:06,637
thus the logistic equation is producing random sequences
220
00:14:06,637 --> 00:14:11,764
a deterministic systems is producing randomness
221
00:14:11,764 --> 00:14:18,952
however then said well ok, any sequence can be generated by the logistic equation
222
00:14:18,952 --> 00:14:22,721
but wait doesn't that mean that the logistic equation is
223
00:14:22,721 --> 00:14:26,291
itself a compression algorithm for a random sequence
224
00:14:26,291 --> 00:14:30,244
but the catch here is that in order to generate a particular sequence
225
00:14:30,244 --> 00:14:33,897
we would need to know the initial condition infinitely precisely
226
00:14:33,897 --> 00:14:37,811
you’ll have to remember all of the digits in that initial condition
227
00:14:37,811 --> 00:14:41,632
and almost all numbers between 0 and 1 are irrational and random
228
00:14:41,632 --> 00:14:44,788
so those numbers are incompressible
229
00:14:44,788 --> 00:14:48,195
so in order to reproduce the sequence we need the logistic equation
230
00:14:48,195 --> 00:14:51,148
that we’re going to iterate and that’s a very simple things
231
00:14:51,148 --> 00:14:53,636
but we also need to remember the initial condition
232
00:14:53,636 --> 00:14:58,327
to infinite accuracy and that’s something that’s incompressible
233
00:14:58,327 --> 00:15:05,525
and thus is it’s random so what this means is
234
00:15:05,525 --> 00:15:09,578
that we actually haven’t compressed the sequence at all
235
00:15:09,578 --> 00:15:13,388
so in other words if you give me an infinite sequence
236
00:15:13,388 --> 00:15:16,461
and say can you find a short way to describe this or represent it
237
00:15:16,461 --> 00:15:18,691
can it be compressed
238
00:15:18,691 --> 00:15:21,388
and I could say well sort of I could generate
239
00:15:21,388 --> 00:15:24,608
the sequence with the logistic equation
240
00:15:24,608 --> 00:15:29,082
however I need to remember an infinitely long initial condition
241
00:15:29,082 --> 00:15:30,853
so really I haven’t compressed it at all
242
00:15:30,853 --> 00:15:34,508
I’ve just taken the infinite longness and incompressibility of the sequence
243
00:15:34,508 --> 00:15:36,612
and sort of swapped it for the infinite longest
244
00:15:36,612 --> 00:15:40,672
and incompressibility of the initial condition
245
00:15:41,424 --> 00:15:44,803
Ok, so the bottom line is that logistic equation is
246
00:15:44,803 --> 00:15:47,890
a deterministic dynamical system that produces randomness
247
00:15:47,890 --> 00:15:50,691
and you could think of that a number of different ways
248
00:15:50,691 --> 00:15:54,494
you can think of it just in terms of statistics over sequences
249
00:15:54,494 --> 00:15:58,899
that looks like a coin toss or in this algorithm make sense
250
00:15:58,899 --> 00:16:02,279
so I should mention that a dynamical system that is not deterministic
251
00:16:02,279 --> 00:16:06,846
one that has element of chance would be called a stochastic dynamical system
252
00:16:06,846 --> 00:16:10,247
we were studying deterministic dynamical system
253
00:16:10,247 --> 00:16:13,637
and so the main point in this is bold because I think this is may be
254
00:16:13,637 --> 00:16:17,709
the important thing biggest important thing in this chapter or per unit
255
00:16:17,709 --> 00:16:20,217
is that the qualities of a result can be
256
00:16:20,217 --> 00:16:23,297
different from the qualities of a process that made it
257
00:16:23,297 --> 00:16:27,449
so here we have a deterministic process producing a random result
258
00:16:27,449 --> 00:16:31,016
and in some sense determinism and randomness are opposites
259
00:16:31,016 --> 00:16:35,562
so we have the quality of the result randomness isn’t a sense very different
260
00:16:35,562 --> 00:16:40,825
than the quality of the process generating it which is deterministic