1
00:00:02,430 --> 00:00:04,020
Welcome back.

2
00:00:04,020 --> 00:00:06,240
Welcome back to Modeling Complex Systems.

3
00:00:06,240 --> 00:00:09,690
We're gonna keep expanding our family

4
00:00:09,690 --> 00:00:12,300
of spatially-explicit models this week

5
00:00:12,300 --> 00:00:15,590
and we're gonna start by
looking at stochastic CA.

6
00:00:15,590 --> 00:00:19,734
So in the case of the elementary CA,

7
00:00:19,734 --> 00:00:23,250
we were looking at deterministic rule set

8
00:00:23,250 --> 00:00:27,540
that told you for sure how
the state of an index cell

9
00:00:27,540 --> 00:00:30,300
would evolve in time or change in time

10
00:00:30,300 --> 00:00:33,180
based on its current state
and the state of its neighbor.

11
00:00:33,180 --> 00:00:35,250
And we're gonna relax that a little bit

12
00:00:35,250 --> 00:00:36,420
and we're gonna look at models

13
00:00:36,420 --> 00:00:38,390
that are still spatially explicit

14
00:00:38,390 --> 00:00:43,390
but where the growth or
evolution of the state of a cell

15
00:00:43,830 --> 00:00:46,140
will depend on both itself,

16
00:00:46,140 --> 00:00:47,880
the state of its neighbors, and pure luck.

17
00:00:47,880 --> 00:00:51,177
So we're gonna allow some randomness

18
00:00:53,460 --> 00:00:55,773
in this transition of our CA.

19
00:00:58,170 --> 00:01:00,840
But other than that, it's
still the same modeling recipe.

20
00:01:00,840 --> 00:01:04,113
So we start thinking about
what system do we wanna model?

21
00:01:05,520 --> 00:01:07,510
And I'm gonna keep it simple here

22
00:01:09,540 --> 00:01:11,550
and go straight to a 2D grid.

23
00:01:11,550 --> 00:01:14,340
So I'm thinking of
traditional euclidean space,

24
00:01:14,340 --> 00:01:18,120
modeling it as a CA,
so with discrete space,

25
00:01:18,120 --> 00:01:20,730
and I'm gonna use a 2D grid

26
00:01:20,730 --> 00:01:25,353
so much like the grid
on my piece of paper.

27
00:01:30,150 --> 00:01:32,070
Done, right?

28
00:01:32,070 --> 00:01:33,060
And then when you think about

29
00:01:33,060 --> 00:01:34,360
what the parts are in our system,

30
00:01:34,360 --> 00:01:35,460
well, in this case,

31
00:01:35,460 --> 00:01:39,050
the parts are every cell in our grid

32
00:01:42,510 --> 00:01:47,253
which will be defined by their state.

33
00:01:48,270 --> 00:01:50,850
So CAs are fun because you already see

34
00:01:50,850 --> 00:01:53,940
that it's mathematically
and computationally

35
00:01:53,940 --> 00:01:56,340
we can use a matrix or
two-dimensional array

36
00:01:56,340 --> 00:01:58,350
to store the entire state of our system

37
00:01:58,350 --> 00:02:00,630
in a spatially explicit manner.

38
00:02:00,630 --> 00:02:04,590
And so the value that's in
that matrix at a given cell,

39
00:02:04,590 --> 00:02:07,710
for example, here we represent its state

40
00:02:07,710 --> 00:02:10,984
and that could be 0, 1, 2 discrete states.

41
00:02:10,984 --> 00:02:14,710
In this video and the next,
we'll keep it fairly simple

42
00:02:16,500 --> 00:02:19,240
and we'll still look at a binary state

43
00:02:23,490 --> 00:02:27,480
which means the choice
between zero or one.

44
00:02:27,480 --> 00:02:32,130
So again, one would most
likely mean on, activated,

45
00:02:32,130 --> 00:02:35,220
there's something there and
zero would be off or unoccupied,

46
00:02:35,220 --> 00:02:37,695
unactivated, there's nothing there, right?

47
00:02:37,695 --> 00:02:39,393
That's just a convention.

48
00:02:41,520 --> 00:02:44,490
And then one thing we
didn't discuss too much

49
00:02:44,490 --> 00:02:47,100
in the case of the elementary CA,

50
00:02:47,100 --> 00:02:48,960
because they were in one dimension,

51
00:02:48,960 --> 00:02:51,120
is the concept of neighborhood.

52
00:02:51,120 --> 00:02:53,490
It was sort of implicit because on a line,

53
00:02:53,490 --> 00:02:56,160
it's easy to think of both neighbors,

54
00:02:56,160 --> 00:02:59,490
one neighbor on the side as
the neighborhood of the cell.

55
00:02:59,490 --> 00:03:01,434
We could have included more neighbors

56
00:03:01,434 --> 00:03:03,330
in which case that wouldn't
be an elementary CA,

57
00:03:03,330 --> 00:03:08,330
just a more complicated
discrete CA in one dimension.

58
00:03:08,730 --> 00:03:12,900
But in 2D, it's kind of a more
subtle choice a little bit.

59
00:03:12,900 --> 00:03:17,900
And we'll have two traditional choices.

60
00:03:19,530 --> 00:03:24,530
So our index cell can either be in contact

61
00:03:26,610 --> 00:03:31,610
with the four cells with which
they share an edge, right?

62
00:03:32,160 --> 00:03:35,070
So my index shell shares an edge,

63
00:03:35,070 --> 00:03:38,010
a face with the cell on top,

64
00:03:38,010 --> 00:03:40,260
at the bottom, to the
right, and to the left.

65
00:03:40,260 --> 00:03:41,190
And that's four cells.

66
00:03:41,190 --> 00:03:43,800
So that's probably the simplest choice

67
00:03:43,800 --> 00:03:46,383
and the one we'll follow
in the next two videos.

68
00:03:47,250 --> 00:03:48,870
Formally speaking,

69
00:03:48,870 --> 00:03:51,780
we'll say that we're using a 2D grid

70
00:03:51,780 --> 00:03:53,320
with one Neumann neighborhood

71
00:03:54,900 --> 00:03:56,050
if we make that choice.

72
00:03:59,490 --> 00:04:01,050
Our index cell,

73
00:04:01,050 --> 00:04:02,710
another option could be

74
00:04:04,110 --> 00:04:07,595
that it's connected to
everything at a distance one

75
00:04:07,595 --> 00:04:09,960
if we're thinking about
growing sort of a square

76
00:04:09,960 --> 00:04:11,610
or a circle around it,

77
00:04:11,610 --> 00:04:14,463
which in this case would
now include the diagonals.

78
00:04:16,140 --> 00:04:18,880
So I go from four to eight neighbors

79
00:04:20,100 --> 00:04:23,730
and that's, in a way, just
a more connected system

80
00:04:23,730 --> 00:04:25,980
which makes it easy to remember its name,

81
00:04:25,980 --> 00:04:27,183
the Moore neighborhood.

82
00:04:30,120 --> 00:04:32,040
And I wanna pause here for a second

83
00:04:32,040 --> 00:04:34,650
and think it's not just
about being more connected

84
00:04:34,650 --> 00:04:38,010
because really the rule set in 1D,

85
00:04:38,010 --> 00:04:39,837
we had the state of the index cell

86
00:04:39,837 --> 00:04:41,730
and the state of both neighbors.

87
00:04:41,730 --> 00:04:44,790
So that was like three
states to specify a rule.

88
00:04:44,790 --> 00:04:46,770
Like what rule is gonna determine

89
00:04:46,770 --> 00:04:50,430
the change of state of my index cell.

90
00:04:50,430 --> 00:04:51,570
And in binary states,

91
00:04:51,570 --> 00:04:54,540
that's two times two
times two or two to three.

92
00:04:54,540 --> 00:04:57,450
So eight rules that were needed.

93
00:04:57,450 --> 00:05:00,540
Well, so the Moore
neighborhood is more connected

94
00:05:00,540 --> 00:05:04,500
but also states more plus possible states,

95
00:05:04,500 --> 00:05:06,090
and therefore possible rules.

96
00:05:06,090 --> 00:05:09,360
So here would be two to
the nine possible rules

97
00:05:09,360 --> 00:05:13,440
for binary states, not even
including the randomness yet.

98
00:05:13,440 --> 00:05:16,530
And so it's not only a
choice of connectivity,

99
00:05:16,530 --> 00:05:20,287
it's also a choice of
space of the rule set.

100
00:05:22,170 --> 00:05:24,210
And so for that reason,

101
00:05:24,210 --> 00:05:26,970
and also because mathematically
and computationally

102
00:05:26,970 --> 00:05:29,490
it's a little easier to deal with,

103
00:05:29,490 --> 00:05:31,110
we're gonna typically focus

104
00:05:31,110 --> 00:05:35,760
on the von Neumann neighborhood, okay?

105
00:05:35,760 --> 00:05:37,890
And you can think in the
von Neumann neighborhood

106
00:05:37,890 --> 00:05:41,100
of that shared edge as
a shared contact, right?

107
00:05:41,100 --> 00:05:43,470
So if we were looking at
the spread of the disease

108
00:05:43,470 --> 00:05:45,390
where maybe zero means susceptible

109
00:05:45,390 --> 00:05:47,220
and one means infectious,

110
00:05:47,220 --> 00:05:50,670
those shared edges would
literally be contacts

111
00:05:50,670 --> 00:05:54,753
between individuals through
which the disease can spread.

112
00:05:55,710 --> 00:05:57,450
So that's a natural choice.

113
00:05:57,450 --> 00:05:58,750
And we'll stick with that.

114
00:05:59,847 --> 00:06:02,550
And so the rule set
becomes a little different

115
00:06:02,550 --> 00:06:07,550
in two dimensions, and
especially with random rules.

116
00:06:15,720 --> 00:06:17,940
And we're gonna focus on two models here

117
00:06:17,940 --> 00:06:21,033
that we're gonna explore
computationally in the next video.

118
00:06:24,388 --> 00:06:25,710
Let me just, rule sets plural.

119
00:06:25,710 --> 00:06:27,730
We're gonna look at random walks

120
00:06:30,060 --> 00:06:32,703
that I also like to
call the drunkards walk,

121
00:06:34,050 --> 00:06:35,463
and percolation.

122
00:06:36,420 --> 00:06:38,160
This isn't a random choice.

123
00:06:38,160 --> 00:06:39,780
They're simple models,

124
00:06:39,780 --> 00:06:43,320
so that makes them appropriate
as a starting point.

125
00:06:43,320 --> 00:06:46,110
But they're also sort of
key modeling ingredients.

126
00:06:46,110 --> 00:06:49,890
So the same way that in module
one in dynamical systems

127
00:06:49,890 --> 00:06:52,950
we saw an exponential
growth, logistic growth,

128
00:06:52,950 --> 00:06:56,310
exponential decay, time and time again,

129
00:06:56,310 --> 00:06:58,230
here in spatially explicit model,

130
00:06:58,230 --> 00:07:01,290
these two mechanisms,

131
00:07:01,290 --> 00:07:03,180
the random walk and percolation

132
00:07:03,180 --> 00:07:06,330
are standard way of including
structure and space.

133
00:07:06,330 --> 00:07:08,490
And so they will show
up time and time again

134
00:07:08,490 --> 00:07:11,883
very much in the next few modules.

135
00:07:12,750 --> 00:07:16,200
So think of them not only as
simple toy models to start

136
00:07:16,200 --> 00:07:19,113
but as key modeling
ingredients to build upon.

137
00:07:21,210 --> 00:07:22,818
And so the random walk

138
00:07:22,818 --> 00:07:26,613
wants to model the random
movement of a particle.

139
00:07:30,630 --> 00:07:35,430
So I have a particle in my index cell,

140
00:07:35,430 --> 00:07:37,143
so my index cell is on,

141
00:07:38,010 --> 00:07:40,380
and the particle can move randomly

142
00:07:40,380 --> 00:07:42,390
and we're gonna assume
that it moves for sure.

143
00:07:42,390 --> 00:07:44,493
That's gonna be part of our rule set.

144
00:07:45,330 --> 00:07:47,580
So with probability one,

145
00:07:47,580 --> 00:07:49,830
and I'm putting a
probability on my rules now

146
00:07:49,830 --> 00:07:51,780
because some of them will be stochastic

147
00:08:00,570 --> 00:08:02,430
or maybe to keep a convention,

148
00:08:02,430 --> 00:08:05,970
I'll just say that I leave,
right, so I go to zero.

149
00:08:05,970 --> 00:08:07,683
So I leave my index cell.

150
00:08:08,880 --> 00:08:11,520
So if I'm at one in the index cell,

151
00:08:11,520 --> 00:08:14,013
four zeroes around it,
I leave the index cell.

152
00:08:15,420 --> 00:08:19,740
Now what's a little bit tricky
is that now with randomness,

153
00:08:19,740 --> 00:08:20,760
this random walker,

154
00:08:20,760 --> 00:08:22,710
this random walker decides to go left,

155
00:08:22,710 --> 00:08:26,133
that means that it's not going
right, up or down, right?

156
00:08:27,300 --> 00:08:30,270
So really, I can't necessarily say, well,

157
00:08:30,270 --> 00:08:34,170
with probability 25%,

158
00:08:34,170 --> 00:08:37,470
my motif to the left is gonna become this.

159
00:08:41,700 --> 00:08:43,770
With probability 25%,

160
00:08:43,770 --> 00:08:45,180
it becomes something else

161
00:08:45,180 --> 00:08:47,490
because those probabilities
are correlated.

162
00:08:47,490 --> 00:08:50,310
If I go left, I can't go right.

163
00:08:50,310 --> 00:08:52,650
So really what I prefer to do,

164
00:08:52,650 --> 00:08:54,900
instead of using the
deterministic rule set

165
00:08:54,900 --> 00:08:56,320
like we did in the CA

166
00:09:02,730 --> 00:09:07,730
is to draw all the possible
evolution of this motif,

167
00:09:10,110 --> 00:09:12,000
not just for the intake cell,

168
00:09:12,000 --> 00:09:13,863
but for the entire neighborhood.

169
00:09:25,980 --> 00:09:30,480
And so with probability 25%, I go up,

170
00:09:30,480 --> 00:09:34,050
if not, with probability 25% I go left,

171
00:09:34,050 --> 00:09:37,470
if not, with probability 25% I go right.

172
00:09:37,470 --> 00:09:38,430
And I shouldn't say, if not,

173
00:09:38,430 --> 00:09:40,290
I'm mixing up probabilities a little bit.

174
00:09:40,290 --> 00:09:41,220
Really what I should say

175
00:09:41,220 --> 00:09:44,820
is that there's four possibilities,

176
00:09:44,820 --> 00:09:47,610
each with equal probability 25%

177
00:09:47,610 --> 00:09:50,130
and that's the random walker

178
00:09:50,130 --> 00:09:53,010
chooses to go up, left,
right, or down, right?

179
00:09:53,010 --> 00:09:55,410
That's the sort of the best way to say it.

180
00:09:55,410 --> 00:09:57,690
And so the writing of this rule set

181
00:09:57,690 --> 00:09:59,610
is conceptually a little different

182
00:09:59,610 --> 00:10:02,250
than it was for the deterministic CA

183
00:10:02,250 --> 00:10:04,263
or the elementary CA that we last saw.

184
00:10:07,440 --> 00:10:09,930
And so that's a really simple model

185
00:10:09,930 --> 00:10:11,430
but it's used, for example,

186
00:10:11,430 --> 00:10:14,820
to describe in a discrete
way a Brownian motion

187
00:10:14,820 --> 00:10:17,340
that you might have seen
in physics or chemistry

188
00:10:17,340 --> 00:10:20,040
which is the little
vibration and variation

189
00:10:20,040 --> 00:10:24,157
in position of a particle
in a liquid or fluid.

190
00:10:24,157 --> 00:10:28,998
And could also describe
literally a random walker

191
00:10:28,998 --> 00:10:32,070
moving in two dimensions.

192
00:10:32,070 --> 00:10:35,576
So a really dumb animal trying
to get food, for example,

193
00:10:35,576 --> 00:10:40,576
it's a simple model for
random transportation

194
00:10:41,640 --> 00:10:43,620
or random displacement of something

195
00:10:43,620 --> 00:10:45,063
in a complex systems.

196
00:10:46,433 --> 00:10:49,830
Percolation is even less dynamical.

197
00:10:49,830 --> 00:10:51,540
So in that sense,

198
00:10:51,540 --> 00:10:54,120
it often doesn't have this notion of time.

199
00:10:54,120 --> 00:10:54,990
So in percolation,

200
00:10:54,990 --> 00:10:59,990
we'll just say that an off cell
turns on with probability P

201
00:11:08,250 --> 00:11:10,293
and we could say that an on sell,

202
00:11:14,640 --> 00:11:18,813
that a on cell stays on
with probability one.

203
00:11:20,520 --> 00:11:21,480
And that's why I say

204
00:11:21,480 --> 00:11:23,850
that it doesn't really
have this notion of time,

205
00:11:23,850 --> 00:11:25,830
because really what we're doing

206
00:11:25,830 --> 00:11:28,980
is just initializing a random matrix.

207
00:11:28,980 --> 00:11:33,060
But even that random
matrix given its density

208
00:11:33,060 --> 00:11:36,210
can have interesting properties.

209
00:11:36,210 --> 00:11:39,000
And so often you just do
one-time step of the CA

210
00:11:39,000 --> 00:11:40,020
and then you're done, right?

211
00:11:40,020 --> 00:11:43,830
There's no notion of of time,
if you do involve percolation,

212
00:11:43,830 --> 00:11:47,490
there might be interesting
(indistinct) dynamics

213
00:11:47,490 --> 00:11:49,380
but you know that there is a fixed point

214
00:11:49,380 --> 00:11:51,633
where everything is on
and stays on forever.

215
00:11:52,500 --> 00:11:54,060
So that's an easy,

216
00:11:54,060 --> 00:11:59,060
that's a useful model for
growth of forest, for example,

217
00:11:59,280 --> 00:12:00,930
or the growth of cluster.

218
00:12:00,930 --> 00:12:02,310
And it's called percolation

219
00:12:02,310 --> 00:12:05,460
because it's also a model

220
00:12:05,460 --> 00:12:07,860
for how things spread through a fluid.

221
00:12:07,860 --> 00:12:11,160
So you could think of on cells

222
00:12:11,160 --> 00:12:16,080
at cells that a fluid can go through

223
00:12:16,080 --> 00:12:17,820
if it's percolating through a medium.

224
00:12:17,820 --> 00:12:19,320
So much like coffee percolation,

225
00:12:19,320 --> 00:12:21,450
I put water through a grid

226
00:12:21,450 --> 00:12:24,690
which is my coffee grains
and piece the probability

227
00:12:24,690 --> 00:12:27,690
that the water can occupy a certain state.

228
00:12:27,690 --> 00:12:29,730
And I'm interested in whether the water

229
00:12:29,730 --> 00:12:31,080
is gonna percolate through

230
00:12:31,080 --> 00:12:33,901
and give me that sweet,
sweet coffee, right?

231
00:12:33,901 --> 00:12:38,220
If my probability of water flowing through

232
00:12:38,220 --> 00:12:42,833
and occupying a pocket between
coffee ground is too small,

233
00:12:44,040 --> 00:12:46,710
then my water's just gonna
sit on top of my coffee

234
00:12:46,710 --> 00:12:51,260
and not give me my much
needed caffeine, right?

235
00:12:51,260 --> 00:12:53,220
So that's the idea here.

236
00:12:53,220 --> 00:12:57,570
But it's really used to
study percolation of things

237
00:12:57,570 --> 00:13:00,270
through a medium, in this case a 2D grid.

238
00:13:00,270 --> 00:13:03,450
And so the next video, we're
gonna code both of those

239
00:13:03,450 --> 00:13:06,450
and start looking at spatial features

240
00:13:06,450 --> 00:13:08,580
that can emerge from randomness

241
00:13:08,580 --> 00:13:10,830
instead of just discreet rules, right?

242
00:13:10,830 --> 00:13:12,430
So I'll see you in the next one.