1
00:00:01,780 --> 00:00:07,520
So let’s analyze properties of symbol sequence generated by the logistic equation
2
00:00:07,520 --> 00:00:11,950
So here I'll think about the symbol sequence generated from an orbit of the logistic equation
3
00:00:11,950 --> 00:00:16,910
and this is with r equals 4.0 so this is a chaotic value, it’s aperiodic
4
00:00:16,910 --> 00:00:20,000
and it has a sensitive dependence on initial conditions
5
00:00:20,000 --> 00:00:22,450
and I’m going to imagine an experiment
6
00:00:22,450 --> 00:00:25,590
and I’m going to do another experiment side by side
7
00:00:25,590 --> 00:00:28,930
and I’m going to imagine tossing a fair coin many many times
8
00:00:28,930 --> 00:00:32,930
so if I tossed a fair coin the outcomes are heads and tails
9
00:00:32,930 --> 00:00:35,850
probability of heads is a half
10
00:00:35,850 --> 00:00:38,460
probability of tails is a half
11
00:00:38,460 --> 00:00:41,930
and the tosses are independent
12
00:00:41,930 --> 00:00:44,880
meaning that the outcome of one toss has no influence
13
00:00:44,880 --> 00:00:48,490
on the outcome of the next toss or any other toss.
14
00:00:48,490 --> 00:00:51,050
symbol sequence I would get the orbit
15
00:00:51,050 --> 00:00:54,290
and then I would convert that to L's and R's
16
00:00:54,290 --> 00:00:59,350
and what I want to do is compare the statistical features of these L’s and R’s
17
00:00:59,350 --> 00:01:04,020
to the statistical features of these H’s and T’s
18
00:01:04,020 --> 00:01:07,790
and I’m going to imagine that we have an infinite amount of data
19
00:01:07,790 --> 00:01:09,420
so we’ve done this infinitely long
20
00:01:09,420 --> 00:01:11,420
and we’ve done this infinitely long.
21
00:01:11,420 --> 00:01:13,820
Ok, that’s a little bit unrealistic.
22
00:01:13,820 --> 00:01:18,730
But there is simplify the discussion and I’ll talk about again a little bit.
23
00:01:18,730 --> 00:01:23,700
Ok, so the first thing we might do we have this infinitely long string sequence of L’s and R’s
24
00:01:23,700 --> 00:01:26,720
so we could say what’s the frequency of L
25
00:01:26,720 --> 00:01:31,120
what’s the frequency of R
26
00:01:45,361 --> 00:01:51,231
and if we did that we would find that half of these symbols were L
27
00:01:51,231 --> 00:01:53,411
and half were R
28
00:01:53,411 --> 00:01:55,061
and we could do the same thing here.
29
00:01:55,061 --> 00:01:59,551
I’ve tossed a fair coin a million and billion an infinite number of times
30
00:01:59,551 --> 00:02:03,061
and we could ask the same question what’s the frequency of H?
31
00:02:03,061 --> 00:02:07,551
what’s the frequency of R ?
32
00:02:09,919 --> 00:02:14,649
and the frequency of H is a half
33
00:02:14,649 --> 00:02:20,239
frequency of tails is a half
34
00:02:20,646 --> 00:02:23,366
So all this says is the heads and the tails are equally likely
35
00:02:23,366 --> 00:02:26,796
occur equally often and the L's and R's occur equally often
36
00:02:26,796 --> 00:02:31,246
doesn’t mean the sequences are the same or have the same statistical features.
37
00:02:31,246 --> 00:02:38,946
It just means that the statistics or the frequency of a single symbol are the same.
38
00:02:38,946 --> 00:02:40,786
So now let’s do another experiment.
39
00:02:40,786 --> 00:02:45,836
Let’s ask about the frequency of L L R L R L
40
00:02:47,745 --> 00:02:50,855
LLR LLR and RR
41
00:02:50,855 --> 00:02:54,855
I better not say that and write that instead, so
42
00:03:05,761 --> 00:03:09,711
Ok, so I was trying to say the frequency of these outcomes
43
00:03:09,711 --> 00:03:12,491
So if I scanned down this very long string and said
44
00:03:12,491 --> 00:03:17,931
how often do I see or what fraction the time do I see an LL together
45
00:03:17,931 --> 00:03:21,931
what fraction the time do I see an LR, RL and RR
46
00:03:23,476 --> 00:03:28,666
and that would be a quarter for all of these
47
00:03:29,941 --> 00:03:34,051
All the four possible pairs are equally likely
48
00:03:34,774 --> 00:03:39,024
the same thing will happen to over here
49
00:03:39,024 --> 00:03:44,437
so if I ask what’s the frequency of HH HT TT and TH
50
00:03:44,437 --> 00:03:49,680
I would see a similar thing
51
00:04:05,810 --> 00:04:09,620
so the frequency of all possible pairs
52
00:04:09,620 --> 00:04:12,970
the frequencies are equal, they’re all equally likely
53
00:04:12,970 --> 00:04:18,640
and the frequency of all possible pairs here are all equally likely.
54
00:04:18,640 --> 00:04:21,190
and you can probably guess the next step
55
00:04:21,190 --> 00:04:29,560
Let’s ask about the frequency of all possible triples LLL, LLR, LRL and so on
56
00:04:33,570 --> 00:04:38,950
Ok, so for the symbolic dynamics, the symbolic sequence from the logistic equation
57
00:04:38,950 --> 00:04:44,230
there are 8 possible outcomes of 3 consecutive symbols
58
00:04:44,230 --> 00:04:51,250
LLL , LLR and so on and they all occur equally likely with a fraction of an eighth
59
00:04:51,250 --> 00:04:53,720
And it’s the same story for the fair coin
60
00:04:53,720 --> 00:04:57,170
there are 8 possible outcomes of 3 consecutive symbols
61
00:04:57,170 --> 00:05:00,920
HHH, HTH and so on
62
00:05:00,920 --> 00:05:02,760
and they all occur equally likely,
63
00:05:02,760 --> 00:05:09,320
equally often their frequencies are the same 1 over 8
64
00:05:09,320 --> 00:05:12,200
I could keep doing this experiment
65
00:05:12,200 --> 00:05:15,779
I could do look at 4 consecutive symbols
66
00:05:15,779 --> 00:05:18,959
5 consecutive symbols, 6 consecutive symbols
67
00:05:18,959 --> 00:05:22,789
for both of these situations and I would see in all cases
68
00:05:22,789 --> 00:05:28,481
all sequences occur equally often
69
00:05:28,481 --> 00:05:33,401
so I considered all five, sequences of five possible point tosses out to see there
70
00:05:33,401 --> 00:05:39,091
occur with equal frequency, same story with L's and R's over here.
71
00:05:39,091 --> 00:05:42,141
So what this means is that the logistic equation
72
00:05:42,141 --> 00:05:46,651
the particular symbolic dynamics from the logistic equation with r equals 4
73
00:05:46,651 --> 00:05:49,641
are as random as a coin toss.
74
00:05:49,641 --> 00:05:52,671
So that’s an important result that I want to think about for bit
75
00:05:52,671 --> 00:05:54,901
So let me write that down.
76
00:05:59,794 --> 00:06:04,974
So the logistic equation with r equals 4, is as random as a coin toss.
77
00:06:04,974 --> 00:06:10,504
for coin toss all possible sequences of H's and T's are equally likely,
78
00:06:10,504 --> 00:06:16,834
for the logistic equation all possible sequences of L's and R's are equally likely.
79
00:06:16,834 --> 00:06:20,757
Here is another way to think about what this means
80
00:06:20,757 --> 00:06:23,807
suppose I would do generate two symbolic sequences
81
00:06:23,807 --> 00:06:25,697
and again that the names of the letters don’t matter
82
00:06:25,697 --> 00:06:30,117
I could use H's and T's, 0's and 1's, the letters are arbitrary.
83
00:06:30,117 --> 00:06:34,587
One of those very long symbol sequences I generated by tossing a coin
84
00:06:34,587 --> 00:06:37,167
again and again and again and again
85
00:06:37,167 --> 00:06:41,587
The other symbol sequence I would generate by iterating the logistic equation
86
00:06:41,587 --> 00:06:43,557
again and again and again and again
87
00:06:43,557 --> 00:06:46,537
and then writing it in symbolic form
88
00:06:46,537 --> 00:06:49,557
and then I handed you those two sequences
89
00:06:49,557 --> 00:06:52,407
and I ask you to tell me which was which
90
00:06:52,407 --> 00:06:53,827
there would be no way
91
00:06:53,827 --> 00:06:54,637
what this means is
92
00:06:54,637 --> 00:06:57,817
there would be no way to tell those two sequences apart
93
00:06:57,817 --> 00:07:00,327
one is generated by a fair coin
94
00:07:00,327 --> 00:07:05,367
but we think of as sort of the most random process imaginable.
95
00:07:05,367 --> 00:07:11,647
The other sequence is generated by iterating a function about as deterministic as it gets.
96
00:07:11,647 --> 00:07:17,167
Nevertheless their outcomes are indistinguishable.
97
00:07:17,167 --> 00:07:23,297
Now I should mention that of course if we were to do this experiment in real life
98
00:07:23,297 --> 00:07:28,947
We can’t have an infinite sequence of fair coin tosses or iterates.
99
00:07:28,947 --> 00:07:30,507
So what we'll have a very long one
100
00:07:30,507 --> 00:07:32,667
these wouldn’t be exactly an eighth
101
00:07:32,667 --> 00:07:34,057
these all wouldn’t be exactly an eight
102
00:07:34,057 --> 00:07:35,517
some would be a little bit more
103
00:07:35,517 --> 00:07:39,167
a little bit less but it wouldn’t effect the overall argument
104
00:07:39,167 --> 00:07:41,527
that in the limit that the sequences
105
00:07:41,527 --> 00:07:43,327
get longer and longer and longer
106
00:07:43,327 --> 00:07:45,427
all of these frequencies become the same
107
00:07:45,427 --> 00:07:47,547
and all of these frequencies become the same
108
00:07:47,547 --> 00:07:53,237
and the two that two sequences are indistinguishable.
109
00:07:58,497 --> 00:08:01,487
So we just saw an example of a deterministic function
110
00:08:01,487 --> 00:08:03,247
producing a random outcome
111
00:08:03,247 --> 00:08:06,407
and not just a random outcome but an outcome that I said is
112
00:08:06,407 --> 00:08:10,127
in a sense as random as a fair coin.
113
00:08:10,127 --> 00:08:12,517
Deterministically iterating a function produces something
114
00:08:12,517 --> 00:08:14,987
that’s indistinguishable from a random coin toss.
115
00:08:14,987 --> 00:08:18,937
So that seems really weird and we’re going to talk about that in a second.
116
00:08:18,937 --> 00:08:22,297
But first I want to point out that this discovery
117
00:08:22,297 --> 00:08:25,847
that iterating the logistic equation turning in a symbolic dynamics
118
00:08:25,847 --> 00:08:27,777
make something that looks like a fair coin
119
00:08:27,777 --> 00:08:30,149
is actually a tremendously useful result
120
00:08:30,149 --> 00:08:33,599
because randomness is actually really useful resource
121
00:08:33,599 --> 00:08:36,419
in science and in our lives.
122
00:08:36,419 --> 00:08:40,249
Having access to randomness is in a sense a good thing
123
00:08:40,249 --> 00:08:44,099
So let me explain what I mean by this.
124
00:08:44,099 --> 00:08:50,259
In many numerical algorithms when does what’s called Monte Carlo simulation
125
00:08:50,259 --> 00:08:54,979
and that requires access to a good source of random numbers
126
00:08:54,979 --> 00:09:01,639
because it requires some sort of random sampling of some sort of a space.
127
00:09:01,639 --> 00:09:08,609
In statistics it’s really important to do, to work with what’s called an unbiased sample
128
00:09:08,609 --> 00:09:12,790
you want to get a random sample, so you have really big population
129
00:09:12,790 --> 00:09:15,280
a million people in a country or state or something
130
00:09:15,280 --> 00:09:17,970
and you want to figure out their statistical properties
131
00:09:17,970 --> 00:09:20,380
some average income who knows
132
00:09:20,380 --> 00:09:21,870
you want to make sure that
133
00:09:21,870 --> 00:09:25,030
Ok, you could ask all million people, that probably takes too long
134
00:09:25,030 --> 00:09:27,180
so instead, you ask some smaller sample
135
00:09:27,180 --> 00:09:30,910
But you want that smaller sample of your larger population
136
00:09:30,910 --> 00:09:32,800
to be representative of a whole.
137
00:09:32,800 --> 00:09:35,810
and the best way to do that is to do a random sample
138
00:09:35,810 --> 00:09:39,190
then I was easy and clear to know how to do that
139
00:09:39,190 --> 00:09:42,740
but having access to good, some sort of good randomness algorithm
140
00:09:42,740 --> 00:09:48,570
if that even makes sense, it does, as we’ll see is a very useful thing.
141
00:09:48,570 --> 00:09:54,712
In other activities, randomness is also useful resource
142
00:09:54,712 --> 00:09:57,522
So if I am engaged in some strategic interaction
143
00:09:57,522 --> 00:10:01,912
with some opponent and that could be bargaining,
144
00:10:01,912 --> 00:10:06,972
that could be, I don’t know, running away from somebody that’s trying to catch me,
145
00:10:06,972 --> 00:10:11,222
evading somebody that’s trying to do something bad to me
146
00:10:11,222 --> 00:10:14,432
I want my actions to be as unpredictable as possible
147
00:10:14,432 --> 00:10:16,742
If the regularities and what I am doing
148
00:10:16,742 --> 00:10:19,042
then my opponent can exploit that regularity
149
00:10:19,042 --> 00:10:21,822
and that could be in a game like prisoner’s dilemma
150
00:10:21,822 --> 00:10:28,352
or rock paper scissors or in some other sort of physical situations
151
00:10:28,352 --> 00:10:30,072
where I’m running away from somebody
152
00:10:30,072 --> 00:10:35,242
and I want to move left and right with equal, equal probabilities.
153
00:10:35,242 --> 00:10:38,672
So in strategic interaction if you’re random
154
00:10:38,672 --> 00:10:42,322
then there is no regularities that an opponent can exploit.
155
00:10:42,322 --> 00:10:47,362
very similar story in cryptography I want to use,
156
00:10:47,362 --> 00:10:49,302
there is a lots of different ways to do cryptography,
157
00:10:49,302 --> 00:10:56,481
but one way is you need some symbol sequence, some source
158
00:10:56,481 --> 00:10:58,001
yes, some symbol sequence
159
00:10:58,001 --> 00:11:01,847
that you use to encode the message you want to keep secret
160
00:11:01,847 --> 00:11:07,527
and the sequences that I’m using as part of that encoding scheme
161
00:11:07,527 --> 00:11:11,167
needs to be as random or as close to random as possible
162
00:11:11,167 --> 00:11:15,216
Because if there are regularities in that encoding sequence
163
00:11:15,216 --> 00:11:17,326
then an opponent can exploit that
164
00:11:17,326 --> 00:11:20,276
and could maybe figure out my secret messages
165
00:11:20,276 --> 00:11:23,666
so anyway the point of all this is that may be we think of randomness
166
00:11:23,666 --> 00:11:26,576
something unwanted and often it is unwanted.
167
00:11:26,576 --> 00:11:29,613
I don’t want my car to like randomly starting in the morning or not
168
00:11:29,613 --> 00:11:33,203
I’d like to know that even when it’s really cold out it’s going to start
169
00:11:33,203 --> 00:11:36,213
So often we think of randomness something to avoid
170
00:11:36,213 --> 00:11:39,313
but randomness actually is a really useful resource
171
00:11:39,313 --> 00:11:44,993
so the logistic equation with r equals 4 can generate numbers
172
00:11:44,993 --> 00:11:47,823
or bits zeros and ones
173
00:11:47,823 --> 00:11:50,603
that can be used as a random number generator
174
00:11:50,603 --> 00:11:53,573
which is really useful in all sort of applications
175
00:11:53,573 --> 00:11:56,503
now I’m not an expert in random number generators
176
00:11:56,503 --> 00:11:59,793
and I don’t but I don’t think that the logistic equation
177
00:11:59,793 --> 00:12:03,353
in this exact form is used in random number generator
178
00:12:03,353 --> 00:12:06,063
however it’s the same basic idea
179
00:12:06,063 --> 00:12:12,293
one is iterating one the computer iterates a deterministic function
180
00:12:12,293 --> 00:12:16,103
that is chaotic and so produces this random outcome
181
00:12:16,103 --> 00:12:18,873
and then that serves as a source of randomness
182
00:12:18,873 --> 00:12:20,823
for whatever is your computer is trying to do
183
00:12:20,823 --> 00:12:25,323
so randomness is actually a useful resource in many circumstances
184
00:12:25,323 --> 00:12:29,053
in any event in the next lecture we’ll dig deeper into randomness
185
00:12:29,053 --> 00:12:32,984
because we clearly have to think a little more about what randomness means
186
00:12:32,984 --> 00:12:37,384
given that we have a deterministic system producing a random result.