So we've seen that the logistic equation, 
with R = 4, produces randomness.

The output is as random as a fair coin toss.

So in this lecture, 
I want to think some about what this means,

and dig deeper into the notion of randomness itself.

So the first point I want to make, and this is a very general point,

and I think that a general and important lesson from the study of chaos and dynamical systems,

is that it's important to distinguish between 
the properties of a process that generates an outcome,

and the properties of the outcome itself.

So, here, we have a deterministic system,

so the property of the function making the output is deterministic,

but the qualities of the output are random.

Um, let me say a little bit about the alternative to a deterministic function.

So if a function isn't deterministic,

one usually says it's stochastic.

What stochastic means is that, OK, it's not deterministic,

so the same input does not always give the same output.

There is some element of chance.

So we could have a stochastic system producing a random result.

Presumably that's what happened with the fair coin.

Or we could have a deterministic system producing a random result.

So the properties of these generating processes are different, maybe even opposite:

deterministic and stochastic,

but they both can produce random results.

OK, so now we need to think:

what does it mean to say a result is random?

Normally, if I said, uh, something is random,

and asked you what it meant,

you might refer to some element of chance.

But how can we think about random without, uh,

How can we think about randomness

without invoking this idea of chance?

So, here are some ways to think about this.

Let me begin with an example:

Next term at College of the Atlantic,

I'm teaching a class on quantum mechanics.

Classes at CoA, um, meet 20 times over 10 weeks.

They meet twice a week.

And registration will be happening here in a couple of weeks,

and students will ask me often:

"When does your quantum mechanics class meet?"

And I'll be able to say:

"It meets every Tuesday and Friday at 1 pm."

So, notice what I did:

there're actually 20 class meetings,

but I was able to describe the times the class will meet

very simply and concisely.

I didn't have to list all 20 times.

I mean, I could have.

I could have said:

"It meets the first Monday at,

I'm sorry, the first Tuesday at, uh, 1,

and the first Friday at 1,

and the second Tuesday at 1,

and the second Friday at 1,

and so on and so on and so on.

The students will look at me strange,

or even more strangely than they normally look at me,

and wonder why I was doing that.

So the point is that

that's lots of redundancy,

and, um, I can take those 20 things

and express them very, very compactly.

So I'd say that, that sort of full dataset,

all of my meeting times,

is very compressible.

I can take all that information and compress it down into a small statement.

On the other hand, I could, if I was feeling devious,
or quirky, I guess,

have the quantum mechanics class meet a different time,

and maybe a different day every week.

That, I don't know why I would do that,

but maybe let's imagine that I wanted to do that,

just to mess with students,

or, I don't know, mess with the registrar or something.

So, um, now the class maybe meets 7 pm on a Tuesday,

and then, you know, 3 am on a Thursday,

and then next week it meets at noon,

and then another day at midnight.

And so it meets at different times 
with no obvious pattern every week.

So then, if a student came up to me and said:

"When does your quantum mechanics class meet in the spring?"

I would have to list, to her or him,

all 20 times.

Because there's no pattern or no regularity,

I can't take those 20 times that I would think of as random,

and compress them.

So what I'm trying to suggest is that

when we're thinking about, um, randomness,

another way to describe what it means to be random

is to say that randomness is incompressibility.

If you have a dataset, 
or a symbol sequence,

that you can't compress,

because there're no patterns there
to come up with a shorter description

then maybe that's what we mean by randomness.

That's one definition of randomness, in fact.

The first example,
the class that meets at the same time,

uh, two days a week, 
for 10 weeks,

that's not a random meeting time.

And accordingly, I can compress that
and describe my meeting times very concisely.

On the other hand, if I meet different times
without any obvious pattern every week,

night and day,
different days of the week,

that's a random class time

and I couldn't describe that in any concise way.

I'd have to list all 20 times.

So randomness, 
one way of thinking about randomness,

is as incompressibility.

So let me do a few examples to get us thinking

about some of the, um,
subtleties associated with this notion of randomness.

So the idea is that a sequence is random
if it is incompressible.

So let's consider these 3, uh, 3 examples.
That'll help illustrate this idea.

So here's the first example:
010101

And in all of these, 
we can imagine these maybe going on forever.

I just think maybe we should put dots to indicate that,
if you want.

So 010101, 
a really, really long, maybe even an infinite sequence,

and is this sequence compressible?

I would definitely say yes.

I can describe this sequence very compactly.

I would say, um,
01 repeated forever.

So there, I took an infinite sequence,
and I described it very compactly.

And since it is compressible,

I would say that this is not random.

OK, let's look at example number 2.

101011 and on and on and on it goes.

And, say, is this compressible?

Is there any short or concise way to describe this sequence?

Any short algorithm, computer program you could write,

that would reproduce this.

And the answer here, um, turns out to be no.

Then I would say that this is random.

Is it compressible?
No.

It's incompressible,
therefore it's random.

So you might wonder, OK, 
where did I get this from?

Did I just make it up?

Uh, no, I didn't just make it up.

And it actually turns out that people are, uh,

when people try to make a random sequence,

um, we're not very good at making randomness.

That's one of the reasons why true randomness is a useful resource,

as I was saying before.

So, um, I took this from a website called
random.org

where it will generate random numbers for you.

You can choose all sorts of different ways,

and it generates random numbers from, um,

some I guess electronic device that's coupled to the atmostphere

that picks up atmospheric noise.

So, um, it doesn't use a random number generator,

it uses random motion of molecules in the air somehow
to produce random numbers.

So anyway, it's a great website if you need random numbers.

They're actually kind of hard to come by.

You can get them at 
random.org

OK, so, uh, this is random
because it is incompressible.

I cannot compress it.

All right, so here's another example.

Again, a long sequence of zeros and ones.

There's not really an obvious pattern here,

although there's this 4 and a 6,

but then we have, um, more alternation here.

And so again, you might wonder and look at this
and think for a long time, and say:

OK, is this random? Is this not random?
Is it compressible?

And it turns out that, um, this sequence is compressible.

And this is, um, pi in binary.

Um, you'd have to put a decimal there, I guess,
um, to make it really binary.

So anyway, this is the binary expansion of pi.

So this is compressible
in that I could, um,

come up with a short or concise description of this.

I could just say:
"Print pi in binary."

That might be a difficult task to do,
but I could specify it,

what that task is, in a rather concise way.

And I could write a computer program that would do this.

It might be a longer computer pro-- 
surely it would be a longer computer program than this.

But, um, if I wanted,

I can make the program run forever and print, um,

an infinite number of digits of pi,
in the limit of infinite time,

and the program would not have to grow infinitely large.

Whatever algorithm it was for calculating pi,

it could just keep chugging along,

and the program doesn't have to get bigger.

Here, if I wanted to generate more and more of this sequence,

the program has to contain a copy of this sequence

because there's no way I can compress it

because it's a random sequence.

So, OK.

So this is not random
because it is compressible.

This is random
because it is not compressible.

And this one is a little bit puzzling

because it seems like it ought to be random

and it looks random,

but it turns out that, um, 
there actually is a short description for it.

So then we might wonder:

"Well, wait. How do you know this is really random?"

Maybe there's some, not pi, 
but maybe there's some other number

that this is a binary expansion of,

or there's some other way of compressing this

and you're just not smart enough to have figured it out yet.

So there're some subtleties with this notion of compressibility

that we're going to have to think through.