Welcome back.
Welcome back to Modeling Complex Systems.
We're gonna keep expanding our family
of spatially-explicit models this week
and we're gonna start by looking at stochastic CA.
So in the case of the elementary CA,
we were looking at deterministic rule set
that told you for sure how the state of an index cell
would evolve in time or change in time
based on its current state and the state of its neighbor.
And we're gonna relax that a little bit
and we're gonna look at models
that are still spatially explicit
but where the growth or evolution of the state of a cell
will depend on both itself,
the state of its neighbors, and pure luck.
So we're gonna allow some randomness
in this transition of our CA.
But other than that, it's still the same modeling recipe.
So we start thinking about what system do we wanna model?
And I'm gonna keep it simple here
and go straight to a 2D grid.
So I'm thinking of traditional euclidean space,
modeling it as a CA, so with discrete space,
and I'm gonna use a 2D grid
so much like the grid on my piece of paper.
Done, right?
And then when you think about
what the parts are in our system,
well, in this case,
the parts are every cell in our grid
which will be defined by their state.
So CAs are fun because you already see
that it's mathematically and computationally
we can use a matrix or two-dimensional array
to store the entire state of our system
in a spatially explicit manner.
And so the value that's in that matrix at a given cell,
for example, here we represent its state
and that could be 0, 1, 2 discrete states.
In this video and the next, we'll keep it fairly simple
and we'll still look at a binary state
which means the choice between zero or one.
So again, one would most likely mean on, activated,
there's something there and zero would be off or unoccupied,
unactivated, there's nothing there, right?
That's just a convention.
And then one thing we didn't discuss too much
in the case of the elementary CA,
because they were in one dimension,
is the concept of neighborhood.
It was sort of implicit because on a line,
it's easy to think of both neighbors,
one neighbor on the side as the neighborhood of the cell.
We could have included more neighbors
in which case that wouldn't be an elementary CA,
just a more complicated discrete CA in one dimension.
But in 2D, it's kind of a more subtle choice a little bit.
And we'll have two traditional choices.
So our index cell can either be in contact
with the four cells with which they share an edge, right?
So my index shell shares an edge,
a face with the cell on top,
at the bottom, to the right, and to the left.
And that's four cells.
So that's probably the simplest choice
and the one we'll follow in the next two videos.
Formally speaking,
we'll say that we're using a 2D grid
with one Neumann neighborhood
if we make that choice.
Our index cell,
another option could be
that it's connected to everything at a distance one
if we're thinking about growing sort of a square
or a circle around it,
which in this case would now include the diagonals.
So I go from four to eight neighbors
and that's, in a way, just a more connected system
which makes it easy to remember its name,
the Moore neighborhood.
And I wanna pause here for a second
and think it's not just about being more connected
because really the rule set in 1D,
we had the state of the index cell
and the state of both neighbors.
So that was like three states to specify a rule.
Like what rule is gonna determine
the change of state of my index cell.
And in binary states,
that's two times two times two or two to three.
So eight rules that were needed.
Well, so the Moore neighborhood is more connected
but also states more plus possible states,
and therefore possible rules.
So here would be two to the nine possible rules
for binary states, not even including the randomness yet.
And so it's not only a choice of connectivity,
it's also a choice of space of the rule set.
And so for that reason,
and also because mathematically and computationally
it's a little easier to deal with,
we're gonna typically focus
on the von Neumann neighborhood, okay?
And you can think in the von Neumann neighborhood
of that shared edge as a shared contact, right?
So if we were looking at the spread of the disease
where maybe zero means susceptible
and one means infectious,
those shared edges would literally be contacts
between individuals through which the disease can spread.
So that's a natural choice.
And we'll stick with that.
And so the rule set becomes a little different
in two dimensions, and especially with random rules.
And we're gonna focus on two models here
that we're gonna explore computationally in the next video.
Let me just, rule sets plural.
We're gonna look at random walks
that I also like to call the drunkards walk,
and percolation.
This isn't a random choice.
They're simple models,
so that makes them appropriate as a starting point.
But they're also sort of key modeling ingredients.
So the same way that in module one in dynamical systems
we saw an exponential growth, logistic growth,
exponential decay, time and time again,
here in spatially explicit model,
these two mechanisms,
the random walk and percolation
are standard way of including structure and space.
And so they will show up time and time again
very much in the next few modules.
So think of them not only as simple toy models to start
but as key modeling ingredients to build upon.
And so the random walk
wants to model the random movement of a particle.
So I have a particle in my index cell,
so my index cell is on,
and the particle can move randomly
and we're gonna assume that it moves for sure.
That's gonna be part of our rule set.
So with probability one,
and I'm putting a probability on my rules now
because some of them will be stochastic
or maybe to keep a convention,
I'll just say that I leave, right, so I go to zero.
So I leave my index cell.
So if I'm at one in the index cell,
four zeroes around it, I leave the index cell.
Now what's a little bit tricky is that now with randomness,
this random walker,
this random walker decides to go left,
that means that it's not going right, up or down, right?
So really, I can't necessarily say, well,
with probability 25%,
my motif to the left is gonna become this.
With probability 25%,
it becomes something else
because those probabilities are correlated.
If I go left, I can't go right.
So really what I prefer to do,
instead of using the deterministic rule set
like we did in the CA
is to draw all the possible evolution of this motif,
not just for the intake cell,
but for the entire neighborhood.
And so with probability 25%, I go up,
if not, with probability 25% I go left,
if not, with probability 25% I go right.
And I shouldn't say, if not,
I'm mixing up probabilities a little bit.
Really what I should say
is that there's four possibilities,
each with equal probability 25%
and that's the random walker
chooses to go up, left, right, or down, right?
That's the sort of the best way to say it.
And so the writing of this rule set
is conceptually a little different
than it was for the deterministic CA
or the elementary CA that we last saw.
And so that's a really simple model
but it's used, for example,
to describe in a discrete way a Brownian motion
that you might have seen in physics or chemistry
which is the little vibration and variation
in position of a particle in a liquid or fluid.
And could also describe literally a random walker
moving in two dimensions.
So a really dumb animal trying to get food, for example,
it's a simple model for random transportation
or random displacement of something
in a complex systems.
Percolation is even less dynamical.
So in that sense,
it often doesn't have this notion of time.
So in percolation,
we'll just say that an off cell turns on with probability P
and we could say that an on sell,
that a on cell stays on with probability one.
And that's why I say
that it doesn't really have this notion of time,
because really what we're doing
is just initializing a random matrix.
But even that random matrix given its density
can have interesting properties.
And so often you just do one-time step of the CA
and then you're done, right?
There's no notion of of time, if you do involve percolation,
there might be interesting (indistinct) dynamics
but you know that there is a fixed point
where everything is on and stays on forever.
So that's an easy,
that's a useful model for growth of forest, for example,
or the growth of cluster.
And it's called percolation
because it's also a model
for how things spread through a fluid.
So you could think of on cells
at cells that a fluid can go through
if it's percolating through a medium.
So much like coffee percolation,
I put water through a grid
which is my coffee grains and piece the probability
that the water can occupy a certain state.
And I'm interested in whether the water
is gonna percolate through
and give me that sweet, sweet coffee, right?
If my probability of water flowing through
and occupying a pocket between coffee ground is too small,
then my water's just gonna sit on top of my coffee
and not give me my much needed caffeine, right?
So that's the idea here.
But it's really used to study percolation of things
through a medium, in this case a 2D grid.
And so the next video, we're gonna code both of those
and start looking at spatial features
that can emerge from randomness
instead of just discreet rules, right?
So I'll see you in the next one.