So let’s analyze properties of symbol sequence generated by the logistic equation
So here I'll think about the symbol sequence generated from an orbit of the logistic equation
and this is with r equals 4.0 so this is a chaotic value, it’s aperiodic
and it has a sensitive dependence on initial conditions
and I’m going to imagine an experiment
and I’m going to do another experiment side by side
and I’m going to imagine tossing a fair coin many many times
so if I tossed a fair coin the outcomes are heads and tails
probability of heads is a half
probability of tails is a half
and the tosses are independent
meaning that the outcome of one toss has no influence
on the outcome of the next toss or any other toss.
symbol sequence I would get the orbit
and then I would convert that to L's and R's
and what I want to do is compare the statistical features of these L’s and R’s
to the statistical features of these H’s and T’s
and I’m going to imagine that we have an infinite amount of data
so we’ve done this infinitely long
and we’ve done this infinitely long.
Ok, that’s a little bit unrealistic.
But there is simplify the discussion and I’ll talk about again a little bit.
Ok, so the first thing we might do we have this infinitely long string sequence of L’s and R’s
so we could say what’s the frequency of L
what’s the frequency of R
and if we did that we would find that half of these symbols were L
and half were R
and we could do the same thing here.
I’ve tossed a fair coin a million and billion an infinite number of times
and we could ask the same question what’s the frequency of H?
what’s the frequency of R ?
and the frequency of H is a half
frequency of tails is a half
So all this says is the heads and the tails are equally likely
occur equally often and the L's and R's occur equally often
doesn’t mean the sequences are the same or have the same statistical features.
It just means that the statistics or the frequency of a single symbol are the same.
So now let’s do another experiment.
Let’s ask about the frequency of L L R L R L
LLR LLR and RR
I better not say that and write that instead, so
Ok, so I was trying to say the frequency of these outcomes
So if I scanned down this very long string and said
how often do I see or what fraction the time do I see an LL together
what fraction the time do I see an LR, RL and RR
and that would be a quarter for all of these
All the four possible pairs are equally likely
the same thing will happen to over here
so if I ask what’s the frequency of HH HT TT and TH
I would see a similar thing
so the frequency of all possible pairs
the frequencies are equal, they’re all equally likely
and the frequency of all possible pairs here are all equally likely.
and you can probably guess the next step
Let’s ask about the frequency of all possible triples LLL, LLR, LRL and so on
Ok, so for the symbolic dynamics, the symbolic sequence from the logistic equation
there are 8 possible outcomes of 3 consecutive symbols
LLL , LLR and so on and they all occur equally likely with a fraction of an eighth
And it’s the same story for the fair coin
there are 8 possible outcomes of 3 consecutive symbols
HHH, HTH and so on
and they all occur equally likely,
equally often their frequencies are the same 1 over 8
I could keep doing this experiment
I could do look at 4 consecutive symbols
5 consecutive symbols, 6 consecutive symbols
for both of these situations and I would see in all cases
all sequences occur equally often
so I considered all five, sequences of five possible point tosses out to see there
occur with equal frequency, same story with L's and R's over here.
So what this means is that the logistic equation
the particular symbolic dynamics from the logistic equation with r equals 4
are as random as a coin toss.
So that’s an important result that I want to think about for bit
So let me write that down.
So the logistic equation with r equals 4, is as random as a coin toss.
for coin toss all possible sequences of H's and T's are equally likely,
for the logistic equation all possible sequences of L's and R's are equally likely.
Here is another way to think about what this means
suppose I would do generate two symbolic sequences
and again that the names of the letters don’t matter
I could use H's and T's, 0's and 1's, the letters are arbitrary.
One of those very long symbol sequences I generated by tossing a coin
again and again and again and again
The other symbol sequence I would generate by iterating the logistic equation
again and again and again and again
and then writing it in symbolic form
and then I handed you those two sequences
and I ask you to tell me which was which
there would be no way
what this means is
there would be no way to tell those two sequences apart
one is generated by a fair coin
but we think of as sort of the most random process imaginable.
The other sequence is generated by iterating a function about as deterministic as it gets.
Nevertheless their outcomes are indistinguishable.
Now I should mention that of course if we were to do this experiment in real life
We can’t have an infinite sequence of fair coin tosses or iterates.
So what we'll have a very long one
these wouldn’t be exactly an eighth
these all wouldn’t be exactly an eight
some would be a little bit more
a little bit less but it wouldn’t effect the overall argument
that in the limit that the sequences
get longer and longer and longer
all of these frequencies become the same
and all of these frequencies become the same
and the two that two sequences are indistinguishable.
So we just saw an example of a deterministic function
producing a random outcome
and not just a random outcome but an outcome that I said is
in a sense as random as a fair coin.
Deterministically iterating a function produces something
that’s indistinguishable from a random coin toss.
So that seems really weird and we’re going to talk about that in a second.
But first I want to point out that this discovery
that iterating the logistic equation turning in a symbolic dynamics
make something that looks like a fair coin
is actually a tremendously useful result
because randomness is actually really useful resource
in science and in our lives.
Having access to randomness is in a sense a good thing
So let me explain what I mean by this.
In many numerical algorithms when does what’s called Monte Carlo simulation
and that requires access to a good source of random numbers
because it requires some sort of random sampling of some sort of a space.
In statistics it’s really important to do, to work with what’s called an unbiased sample
you want to get a random sample, so you have really big population
a million people in a country or state or something
and you want to figure out their statistical properties
some average income who knows
you want to make sure that
Ok, you could ask all million people, that probably takes too long
so instead, you ask some smaller sample
But you want that smaller sample of your larger population
to be representative of a whole.
and the best way to do that is to do a random sample
then I was easy and clear to know how to do that
but having access to good, some sort of good randomness algorithm
if that even makes sense, it does, as we’ll see is a very useful thing.
In other activities, randomness is also useful resource
So if I am engaged in some strategic interaction
with some opponent and that could be bargaining,
that could be, I don’t know, running away from somebody that’s trying to catch me,
evading somebody that’s trying to do something bad to me
I want my actions to be as unpredictable as possible
If the regularities and what I am doing
then my opponent can exploit that regularity
and that could be in a game like prisoner’s dilemma
or rock paper scissors or in some other sort of physical situations
where I’m running away from somebody
and I want to move left and right with equal, equal probabilities.
So in strategic interaction if you’re random
then there is no regularities that an opponent can exploit.
very similar story in cryptography I want to use,
there is a lots of different ways to do cryptography,
but one way is you need some symbol sequence, some source
yes, some symbol sequence
that you use to encode the message you want to keep secret
and the sequences that I’m using as part of that encoding scheme
needs to be as random or as close to random as possible
Because if there are regularities in that encoding sequence
then an opponent can exploit that
and could maybe figure out my secret messages
so anyway the point of all this is that may be we think of randomness
something unwanted and often it is unwanted.
I don’t want my car to like randomly starting in the morning or not
I’d like to know that even when it’s really cold out it’s going to start
So often we think of randomness something to avoid
but randomness actually is a really useful resource
so the logistic equation with r equals 4 can generate numbers
or bits zeros and ones
that can be used as a random number generator
which is really useful in all sort of applications
now I’m not an expert in random number generators
and I don’t but I don’t think that the logistic equation
in this exact form is used in random number generator
however it’s the same basic idea
one is iterating one the computer iterates a deterministic function
that is chaotic and so produces this random outcome
and then that serves as a source of randomness
for whatever is your computer is trying to do
so randomness is actually a useful resource in many circumstances
in any event in the next lecture we’ll dig deeper into randomness
because we clearly have to think a little more about what randomness means
given that we have a deterministic system producing a random result.