Obviously we're in my office again,
which often means that we'll be
doing some coding in the video.
And in this case,
I wanna show you codes that implement
the really simple, stochastic CA
that we saw in the last one.
So random walks and percolation.
And I keep showing different modeling schemes
and sharing MATLAB codes,
C++ code and Python.
Here I wanted to use Google Colab
specifically for this one
because we'll see some interesting interactive features,
that if you've never played with
are actually really easy
to use in Google Colab.
So we're gonna start with
what is probably the slightly more complicated
model of the two we saw.
The random walker.
And I'll start with a function to run a random walker.
And essentially I'm gonna assume that I have a world,
I'm calling this a world to be fancy,
but it's my two dimensional grid.
So a big matrix,
or in this case a two dimensional array
that can be square or not.
So that array is gonna have some specific dimensions
N one and N two.
I'm gonna keep track of my random locker.
So IJ is where my random locker is at any time.
And here I'm doing something kind of fancy.
So I keep track of my position.
I'm gonna keep track of the history of my random walker
so it's entire trajectory in time.
So that's a dynamical system.
And I'm going to evolve or grow,
or let that random walker move for a fixed number of steps.
50,000 or whatever integer I'd want to use.
So for every step,
I'm gonna do this slightly fancy thing where
even though my model is specified over binary state,
zero if the cell is unoccupied,
one if the walker's there,
I'm gonna set cells that have been visited
at any time, maybe multiple times,
but if a cell was visited at least once,
I'll set a state to two thirds.
This is not formally in the model, it's for visualization.
To be able to see not where the random walker is,
or only where it is, but where it has been, right?
And so I have disposition IJ for my random walker.
I guess I didn't need this line here.
But I keep my position IJ.
And I'm gonna throw a random number, a random die,
random coin that's gonna give me
a continuous number between zero and one.
That's so I can pick one of my four different rule set.
We saw some very similar algorithms
when we're looking at discrete models,
like the cloning factory.
And so the way this works is,
if my random number gives me
something smaller than 25 percent,
I can accept my first option.
It's just to take a right step.
And I realize now that in the last video,
you know I've
conceptually or mathematically formulated random walk
but I forgot to talk about boundary conditions.
Whenever it's time to code these things,
you need to think about boundary conditions
because of, of course your world isn't infinite.
So much like we did last week in the elementary CA,
I'll just assume periodic boundary conditions
using this modular operation.
So I take a right step,
which brings me to J plus one
or to the other side of the world
if J plus one is outside of the bounds of the world.
If my random number was not below
0.25,
I'll have another probability that if it's below 0.5,
so now I would know because of this else if.
I would know that it was between 25 and 50,
which also occurs with probability 25 percent.
And so if it is between 25 and 50,
I take my second option which is to go to the bottom,
which brings me to I minus one
with the module to give me the freedom
to loop around the world, and so on and so forth.
So if it's above 0.5 but below 75,
which happens with probability 25 percent,
I take my left step to J minus one
with the module of else between 75 and 100 percent.
I do my top step to I plus one
with the module of to loop around the world.
I could do a biased random walk.
Those probabilities don't have to be fixed.
So if I had only a 10 percent chance,
let's say I'm going left and a 40 percent chance of go,
10 chance of going right
and a 40 percent chance of going to the bottom,
this would stay at 0.5
and this one would go to 0.1.
So these could be parameters of my random walk
but I wanna show you the simplest case
of the unbiased random walk.
And then I set my,
the cell at this position to one
to show that that's where the
random walker currently is.
And I append or add the current position
of that random walker in the history of the world.
And now I have a function to run this
and plug the state of the system.
So I define the size of my world.
Right now I'm asking for
50,000 steps
and I also have this DT parameter, which is for my plot.
I can track in time the growth of my
or the
walk of my random walker.
If I had a one, I would be following every single step.
Plotting every single step of the way
much like we did in the CA case,
elementary CA video.
But here, I'll just plot the final stake for now.
I initialized my world with a bunch of zeros
so nothing's occupied.
My random walker can go anywhere.
And then I put my random walker in the middle of that world,
in the middle of nowhere.
And I start with an empty history.
And so this is much like we did last time.
I could plug through time
but here I'm just gonna plug the final state of my system.
So it's already a surprisingly beautiful figure, right?
So my random water started right in the middle of nowhere,
in the middle of this figure,
and then randomly went up
and explored this like
cool looking cluster of spaces.
And like I said, I could decide to
plug where my random walker has been every 10 steps.
In which case I'll just have this like
annoyingly slow video.
I guess I didn't have to like
enforce a sleep function here to make it even slower,
but I could track my random walker in real time
and look at the evolution or the growth of that cluster.
In class, in discussion group,
we'll be looking at the
mathematical properties of the dynamics of the random walk.
But I think what's interesting
with these spatially explicit model
is to look
at space itself.
Right, those clusters are beautiful.
This one looks like a trail of smoke
and you see the periodic boundaries acting up here.
So both left and right to left, and top to bottom.
Well you tend to get just
beautiful clusters out of these.
And it brings up notions that we saw last week.
So fractality, the dimensionality of these clusters
might be an interesting thing to look at.
Here I look at how we can coarse grain them.
And so here I'm gonna say,
I'm gonna coarse grain my states by 200.
So what I'm meaning is here's my position in X and Y.
So this is the same cluster as we had here if I rerun it.
All right, so this is exactly the same cluster.
We notice a little hole in this
shape.
This looks like continents on a different planet somehow.
And in the middle panel what we have
is every
200th
state of that
random walk.
Right, so we're just sampling
at every time, at every delta T equals 200,
the state of our random walker.
And we capture much of the shape of this random walk.
Because the random walks is so random, so slow,
it tends to spend a lot of time in the same place.
So it's easy to course grain it
and still keep the large scale feature of the random walk.
And then the final panel,
what I show is the first 200 step of my random walk.
Right, and I coarse grain even more.
And then eventually like run out of steps.
I just realized I don't show the first 200 or 1000 step,
I'm sorry, I should have made that clearer.
What I show is a sampling with the same number of points.
So I had 50,000
steps on the left,
so that means that I have 50 samples
at intervals of 1000
and therefore here I plug the first 50 times steps.
And so if I coarse grain in less
I get more points here and there.
What's interesting is that if you run more of these
there is this notion of self similarity.
You know, I mentioned that the dimension
of these clusters might be interesting.
And it's not unsurprising to get to get similar clusters
or similar looking shapes on the right and the left, right?
Even though this is just, you know,
the first 10 percent or something of the full clusters.
The features tend to repeat this themselves at all scales.
And by features I mean both the visual
features of the graph itself
with the statistical features of the random walk.
And we're gonna explore that more mathematically.
So it's yet another example of how,
you know, complex natural looking patterns
can emerge from very simple rules.
Here are just random motion, right?
And we're gonna see that in percolation as well.
So I'll be sharing these codes
and I invite you to play with them.
Maybe make a biased random walk or,
or start looking at the dimensionally of these clusters.
The codes are fairly simple.
So in this one I'll be doing something a little fancier
to introduce this notion of interactive
component in the model.
And so percolation is this really simple model.
I said in the first video,
we usually just don't even run it in time,
we just run it once.
So upsell can become occupied with a fixed probability.
So I have again, my world,
which I assume is gonna be full of zeroes at the start.
And I'm gonna go over every cell in that grid.
So for every cell in every row and every column.
And I'm gonna throw a random number.
So a random die or coin
that's gonna give me a number between zero and one,
which would form probability.
And if that number is below my occupation probability P,
so this probability I'm gonna turn cell on.
If not, I'm gonna leave it off at zero.
In percolation we often call this occupied
if it's active at one
and unoccupied if it remains at zero.
And then we might be interested in
whether there's a cluster that can conduct current,
right, percolation could be a model for
spread of electricity in a damaged material,
things like that.
We're often interested in the connectivity
and shape of these clusters.
And this next function is introducing
this really simple tool called forms on Google Colab.
And so I'm gonna have a probability,
which is my parameter in this percolation model,
which I could set to a fixed value
or I could tell Google Colab with this line here
that I want this parameter to be of a type slider
between zero and one with steps of 0.01.
Just adding this line,
if you add it,
magically you'll get this slider on the right.
And you'll notice that if I move this slider around
I'm updating the probability in the code itself.
You'll also notice that when I move it
the cells run automatically.
That's because at the very beginning
I added this other comment
to tell the cell to run automatically
when there is a change in the Google form, all right?
The Google form could be text,
could be, there are a lot of like
different data types to play with
and I invite you to like Google
how to play with them
if you're interested in more interactivity.
So that's how we're gonna set the value
of our percolation probability.
Our world, like I said,
is gonna start in with simple initial conditions,
all zeros, everything unoccupied.
And we're gonna run percolation,
which means that a fraction probability,
fraction P of our sites are gonna
turn on and become occupied.
And then we're gonna plug two figures.
The first one will be the state
of the world after percolation,
which should look like white noise
with a fraction probability of white cells
and one minus probability of black cells.
And I'm gonna do something fancier here
that I'm not gonna explain too much,
but I'm gonna look for connected cluster
in my Von Neumann Neighborhood.
So here this structure array
is encoding what I define as a connection.
So I explicitly say that diagonals,
the two top numbers of my three by three array
and the two bottom numbers on the corners, are zero.
So if I turned them on,
I would be in a Moore Neighborhood,
now I'm in a Von Newman Neighborhood.
And I'm gonna ask the code to find the connected cluster.
So that's kind of neat to have
a function to do it for us and label them.
And then I'm gonna look at
what are the sizes of those clusters
and keep only the biggest one.
So my second figure is gonna show us
the biggest connected cluster,
meaning sites that share an edge
in this random noise of percolation.
And we're gonna plug both.
Once you have your Google form set up
you can double click on it,
get rid of the code and make it look a lot cleaner.
Right so here I've run
percolation with a probability of 0.35,
which means that I know
that there's about 35 percent of pixels
on the left that are white
and 65 percent are black.
And my biggest cluster was like some connected cluster
in the bottom right quadrant of the figure.
And I can
make a higher probability 0.36, that's not much higher.
I get a slightly bigger maybe cluster in the top.
The left will always look like pure white noise, right?
Not much structure to find there.
0.4, slightly bigger cluster.
0.41 maybe,
I've set this like step to be 0.01.
Slightly bigger and then I can go much further.
0.47.
0.5.
And I can just play a little more
interactively with my code
and having to like change with the keyboard
and rerun the thing.
0.54.
And now they're growing and getting interesting.
And we're seeing some of the same
statistical features of randomness
that we saw with random walks, right?
Like maybe a good model for random forests.
And,
and by that I mean actual random forests in the world.
Satellite imagery, looks like a smoke trail a little bit.
And I'm growing
and growing my clusters.
And at some point my clusters get incredibly big.
What's interesting is that that point
is like actually very, very fine.
If I had an infinite
world to play with,
there is one point where below it
I expect only finite size clusters
and above it I expect an infinite spanning clusters.
So what a spanning cluster is,
if I go
a little higher,
is this idea that if I was conducting electricity,
for example, from top to bottom,
in a spanning cluster,
that cluster scales with the size of my system
and becomes infinite.
Or in this case would mean that
I can conduct a signal almost for certain
from somewhere at the bottom, somewhere on top, right?
There exists a cluster and its size is still gonna grow.
So if I go to 0.82, I'm still gonna get a bigger cluster
but I still have a connected world essentially.
And we're gonna look mathematically
in some other models about how equations,
very much like the tools we saw in dynamical systems,
can help us identify those critical transition.
It's very much like,
if you're thinking of percolation
as a model for disease spread,
this isn't unlike
the epidemic threshold that we saw
where below a certain density,
the disease cannot spread in the population.
Above that epidemic threshold,
above are not equal one can invade the system, right?
And so we're often gonna talk about
this critical value as the
percolation threshold of the system.
And from phase transition theory,
which is the study of these critical points,
there's a lot that we know about the behavior
of the system around that threshold.
So for example, I know that if I'm just around it,
the distribution of size of these non spanning clusters
actually follow with power law distributions,
power laws like the mathematical forms
that we saw in the study of fractal last week.
And so there's a lot of connections between
these different ideas of complexity
when I'm at around that critical point.
If I'm far from it, the system is boring, right?
A fully connected system to an empty system.
But there is a space in between,
a space in between emptiness
and boring order that exhibits really interesting behavior.
And so we're gonna dig in that more
and we're gonna use percolation as a modeling ingredient
to think about a lot of different system.
So I'll put all of this online.
I'll invite you to play with them, do your own models,
and then we can discuss that more in discussion group.
And I'll also share some videos of my own models of
stochastic CA and I'll start connecting ideas
from module one and module two.
So in one of the videos I'll share
I'll try and tell you the story
of how the forest got its shape.
Which uses ideas from percolation
and dynamical system into one story.
So I'll see you for that in the next one.
Bye.