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