The summary for this unit will come in two parts
in the first part I’ll collect some of the definitions and terminology
key results and arguments that I went over in the many videos in this section
and then in the second part of the summary
I’ll take a step back and talk about what I think some of
these results mean why they are interesting and important
and why they’re fun to think about
so let’s get start it
so let’s summarize what we did in Unit 3
Unit 3 was on chaos and butterfly effect
I began by introducing a logistic equation
and I went through a derivation talking about
rabbits on an island and annihilation values
but the main thing is that the logistic equation is a very simple model
of population growth where there’s some limit to the growth
there’s some maximum population beyond which the population can’t pass
we ended up with this form
perhaps the most famous or
one of the most two famous equations in the study of chaos
f of x r x 1 minus x
and we interpret r as a growth parameter
and x is measured as a fraction of the annihilation parameter
so it’s some fraction of the maximum possible number of rabbits or whatever
and this function f of x we can iterate it
and it gives us the population next year
f of x is the population next year
given that x is the population this year
so we have results of the function
and we can now iterate this function like we did it Unit-1
to do so we turn to an online program
that will iterate the logistic equation
you enter r you enter some initial conditions
and it will make a time series plot and show you the numbers
and so here is just one sample output for that
hopefully you’ve experimented with this a bunch by now
and we found attracting periodic behavior of different periodicities
period 2 period 3 period 4
and we’ll see that there’re more period as well
and then we found something else
something that I hope it was surprising and kind of fun
and that is for r equals 4 and also for some other values the orbit is aperiodic
here’s an example of what that look like the orbit doesn’t hit some regular cycle
it just keeps bouncing around all over
so for this the orbit never repeats
so applying the same function over and over again
doing this incredibly repetitious process
always produces in somethings somethings new
it does not the orbit does not settle in to periodic behavior
so that was kind of weird and perhaps little bit surprising
and then things got thing hope even more interesting
so we started thinking about comparing the orbits for two different initial conditions
so we used the similar but different online program
to compare the time series for two initial conditions
and here is what the output for that just
for some sample values might look like
start with two different initial conditions and
they both end up at the same fixed point
I don’t know around .8 or .6 whatever it is
and then in this bottom plot
I plotted the difference between these two time series
so the difference starts off large and negative
and the difference decreases in the sense that it gets closer and closer to zero
so this is showing us that these two orbits that start far apart .7 apart or so
end up getting closer and closer together and reach the same fate
they end up here together
then we tried making a similar plot when r equals 4
that was the aperiodic case
here we saw that two orbits that start very close together
eventually end up very far apart
here the two orbits are right on the top of each other
there’s so similar one blots out the other
and then they start to pull apart here
this curve down below is plotting
the difference between those two initial conditions
it starts very small and then becomes very large
and this phenomenon is known as sensitive dependence on initial conditions
or more popularly as the butterfly effect
the idea is that okay it depends very sensitively
the long term behavior of the orbit depends very sensitively on the initial condition
and a very small initial change perhaps something as small as
might result from a butterfly flapping its wings
could make a large difference down line
so again just say that a different way sensitive dependence on initial conditions
I gave a formal mathematical definition of it which basically boils down to this
for any initial condition x, there is another nearby initial condition
very very close to it that eventually ends up far away
so the initial conditions are always getting pushed away from each other
so to predict the behavior of a system with sensitive dependence on initial conditions
would require knowing the initial condition with impossible accuracy
so we saw an example that to predict the Lorenz equation how to t equals 18
we get very different results if the initial condition varies by
what was it 2 nanometers or 10 nanometers out of 15 meters
so such precision is needed such accuracy as mean needed
that not only it is a practically impossible
but it’s perhaps even theoretically meaningless
the bottom line is that systems with sensitive dependence are deterministic
yet nevertheless they’re unpredictable in the long run
and usually even in the medium run
sensitive dependence on initial conditions means that the orbit
that a computer calculates for us actually isn’t the true orbit
we thought we were calculating
computers have to round off numbers and have finite precision
and so the orbit that a computer gives us is not the true orbit for that initial condition
and that may be worrying we might wonder
what is the computer showing us then is a complete nonsense
and it turns out that the computed orbit
it’s not that orbit we thought we were getting
but it’s arbitrarily close to some other true orbit for the dynamical system
it’s the orbit for a different initial condition
so we would say that the computed orbit shadows some other true orbit
and this result is known as the shadowing lemma
so finally we are in a position to define chaos in the mathematical sense
so we say that a dynamical system is chaotic if the following 4 criteria are met
it’s deterministic which the dynamical systems for studied certainly
are iterated functions and differential equations are deterministic dynamical systems
its orbits need to be bounded they can’t fly off to infinity
the orbits are aperiodic as we saw it was the case
for the logistic equation with r equals 4
and it has sensitive dependence on initial conditions
again as we saw with r equals 4 for the logistic equation
so the logistic equation and iterated function is a chaotic dynamical systems in this sense
so then we turned our attention towards the idea of randomness in this puzzle
that a deterministic dynamical system is producing a random output
so to start thinking about that I first introduced this idea of symbolic dynamics
and so what we do is we convert the orbit which is
a sequence of numbers between 0 and 1 into some symbols
L and R for left and right
we could do 0 and 1 or any two symbols that we wanted
so if x is less than a half we’ll say we’ll turn it into an L
and if x the iterate is greater than a half, we’ll turn it into R
and it turns out that this particular way is way here of converting
the orbit into symbols has this nice property
it’s known as a generating partition
and in brief what this means is that the initial condition
uniquely determines the symbol sequence and vice versa
in the limit that the symbol sequence goes to infinity
so the bottom line is because of this relation
the properties of the symbolic dynamical system
or dynamical system after doing this conversion
in the original dynamical system are the same
and by what I mean by properties are the same is that
the dynamical system in either at symbol form or it’s non symbol form
will have the same fixed points with the same stability
or same number of fixed points with the same stability
if one is aperiodic the other will be
if one has sensitive dependence on initial conditions, the other has too as well
so then I imagined looking at two different systems
a coin toss a random coin toss and the symbolic dynamics
symbol sequences from the logistic equation with r equals 4
and I argued that the logistic equation at r equals 4 is as random as a coin toss.
what I mean by that is that for both the logistic equation and the coin toss
all possible sequences of symbols occur with equal frequency
so all possible sequences of length 2 of length 3 of length 4 and so on occur equally likely
so what this means is if I give you two long sequences
one of which was generated by the logistic equation a deterministic process
and the other I generated by randomly tossing a coin
you could not perform a statistical test that could distinguish between the two
the logistic equation produces a sequence that is statistically identical
to that would be produced by a random coin
so that let us to think even more well what does randomness mean
and one of the key ideas here is we need a separate
the properties of a process and the results of a process
so instead of thinking about randomness as that which occurs by chance
I want to think about randomness in a different way
so sometimes called algorithmic randomness and the key idea
is that a random sequence is one that is incompressible
it contains no regularities or patterns
that I can use to come up with a shorter description of it.
but then we were faced with a puzzle
how can we tell if a sequence is compressible or not
I showed you the binary expansion for pi
and it certainly wasn’t obvious that that binary expansion
could be compressed into just the number pi
so we might wonder well ok
is there an compression algorithm that will always work
and it turns out that there does not exist an algorithm
for finding the best way to compress a sequence
however we can make an argument that
almost all sequences are incompressible and hence random
so let’s go through that argument
so we looked at two sets
the set of all sequences and a set of algorithms
and those sets are both infinite in size
there are infinite number of possible sequences
and an infinite number of possible algorithms
however and I didn’t prove this
but it turns out that there are infinitely
many more sequences than algorithms
in fact there are different types of infinity the number of sequences
what we would say is uncountably infinite
and the number of the algorithm is countably infinite
and so what this means is that they’re vastly vastly
infinite infinite many more sequences
and there are algorithms and each and each algorithm
I’m thinking of as a way to describe or compress a given sequence
so what this means is there cannot possibly be ways
to compress the vast majority of sequences
there simply aren’t enough algorithms compression algorithms
or schemes to go around
so what this means is that a randomly chosen infinite sequence
if you have a gigantic infinite bag that holds this infinite set of sequences
and you just close your eyes and pick one out with probability 1
it will be incompressible in this random
and what I mean by probability one is yes you could get astronomically lucky
and choose one that happen to be compressible
but in the long in the limit of infinite sequences that
would occur the probability of that occurring would be a zero
it’s sort of like saying what’s the probability if you toss a fair coin
and infinite number of times that it always comes up heads
yes there isn’t there is one way that it could come up all heads
but that’s one out of an infinite number
so we’ll say that you are going to get something other than all heads with probability 1
anyway so what bottom line is that
with probability 1 almost always a randomly chosen
infinite sequence is incompressible ie it’s random
now the logistic equation with r equals 4 produces all possible sequences
therefore so in sense that the logistic equation is filling up this bag
I was talking about consisting of all of these random infinite sequences
thus the logistic equation is producing random sequences
a deterministic systems is producing randomness
however then said well ok, any sequence can be generated by the logistic equation
but wait doesn't that mean that the logistic equation is
itself a compression algorithm for a random sequence
but the catch here is that in order to generate a particular sequence
we would need to know the initial condition infinitely precisely
you’ll have to remember all of the digits in that initial condition
and almost all numbers between 0 and 1 are irrational and random
so those numbers are incompressible
so in order to reproduce the sequence we need the logistic equation
that we’re going to iterate and that’s a very simple things
but we also need to remember the initial condition
to infinite accuracy and that’s something that’s incompressible
and thus is it’s random so what this means is
that we actually haven’t compressed the sequence at all
so in other words if you give me an infinite sequence
and say can you find a short way to describe this or represent it
can it be compressed
and I could say well sort of I could generate
the sequence with the logistic equation
however I need to remember an infinitely long initial condition
so really I haven’t compressed it at all
I’ve just taken the infinite longness and incompressibility of the sequence
and sort of swapped it for the infinite longest
and incompressibility of the initial condition
Ok, so the bottom line is that logistic equation is
a deterministic dynamical system that produces randomness
and you could think of that a number of different ways
you can think of it just in terms of statistics over sequences
that looks like a coin toss or in this algorithm make sense
so I should mention that a dynamical system that is not deterministic
one that has element of chance would be called a stochastic dynamical system
we were studying deterministic dynamical system
and so the main point in this is bold because I think this is may be
the important thing biggest important thing in this chapter or per unit
is that the qualities of a result can be
different from the qualities of a process that made it
so here we have a deterministic process producing a random result
and in some sense determinism and randomness are opposites
so we have the quality of the result randomness isn’t a sense very different
than the quality of the process generating it which is deterministic