Hey guys, in this video I wanted to talk about self-avoiding walks, which are a special case
of random walks and I basically just wanted to introduce them as a mathematical concept
and maybe go over a little bit of the basics of what they are and how they work. Let's go ahead and
get started with that. A random walk is a kind of like concept or branch of mathematics. It's
called lattice theory usually. And it basically works as follows. Let's use the simple case of
we're just in two dimensions, although you can expand this to also three dimensions,
and suppose you have a lattice or a grid. Then basically a random walk is how can you move
and take steps from an initial point--let's say A--how do you move in this lattice space? A random
walk is basically just programmed to randomly move in 2D space. In 2D space you have four
options. You can move up, right, down, or left at each step and each step basically is an edge from--
if you think of this as a node--then each step is just an edge that takes you from one step to the
next. Or from one location to the next. And so this is an idea in mathematics called a random walk.
Self-avoiding random walks, or self-avoiding walks, are random walks that have the additional property
which is that they do not cross. At each step when we're moving, a regular random cross can
go back to where it started from and it can pass and basically create crosses like this.
But a self-avoiding walk cannot do that. For a self-avoiding walk, you are not allowed to
move back to a place where you already were and so you cannot create crosses. Let's say this
is the first step I take. I'm starting from here and I go step one. This is one step. This is step
two. This is step three. At step three, I can't go to the left anymore because that would be going back
to a point that I already visited and I can't go down anymore either because I already visited this
point as well. At step three for a self-avoiding walk, I only have two possibilities. I can go up
or I can go to the right. And so this creates random walks that look a little bit different
from regular random walks because you basically cannot cross them. When we are creating random
walks, we usually refer to d as the distance or the size of the random walk. If I want d equal
to 15, that basically means I want a random walk or a self-avoiding walk that takes 15 steps. And so if
you're programming something like that in computer science, if you want a self-avoiding walk at step
15 that takes 15 steps, you're going to run into some problems where your self-avoiding walk has to
terminate early because it gets stuck. Let me do an example. Let's say we start here at A. I'm
going to go to the left one, go down two, go to the right two, and then go up and left. At this point B,
this self-avoiding walk has to terminate because I'm left with no other options of where to go.
Let's say I've just randomly moved left, down, down, right, right, up, left. At this point,
the self-avoiding walk has to terminate because I have no options of where to go. I can't go down
because I already visited this point here. I can't go right. I can't go up and I can't go left. This
self-avoiding walk has d or length 1, 2, 3, 4, 5, 6, 7. This has to have a size
seven and you can't keep going. This could have been randomly generated in a computer program
that creates self-avoiding walks and it would not count as a self-avoiding walk that has 15 steps.
Basically, you have to kind of iterate through a couple tries of making random self-avoiding
walks until you get one that actually reaches the desired length. This is basically like a problem
that you sometimes have to solve. One way that you can avoid getting into this position where
you're stuck and you have to terminate early is by doing an algorithm called the n-step look ahead
algorithm. With an n-step look ahead algorithm-- let's say we do a one-step look ahead algorithm.
That says that at each point before we move, we're going to look and see--or you have a
computer program look and see--what does the future look like. You look one step ahead. Let's say
I move up. It makes sure basically that where you randomly move is available at that nth step. So if
you have a one-step look ahead algorithm, at each point, you look one step ahead to see where you can
move before you actually make that random move. If you do a two-step look ahead, you make sure to move
only where you are sure you have two possible steps that you can take in the future before you
actually make a move. You can increase the n. You can look three steps ahead, four steps ahead.
You can increase the n but basically it becomes more computationally difficult for large n
to keep looking ahead before you have the random walk move. And then jumping to another topic, I also
wanted to mention that it's very easy to calculate the probability of getting a certain self-avoiding
walk. This is actually how iI earned about self-avoiding walks because you can create them
basically using like Monte Carlo methods and it's also very easy to calculate their probabilities.
Basically at each step, you would just update the probability using basic counting rules. This
was a self-avoiding walk that was created using a one-step look-ahead algorithm and it's a size
nine meaning it took nine steps. If I wanted to calculate the probability of getting this exact
self-avoiding walk, this nine step self-avoiding walk, you do that very easily as follows. At each
node, you calculate the probability of being able to move to the next spot and then you just
multiply each event because it's basically--each step is independent of the previous one because
you're just making a random step each time--and so you just calculate the probability at each step.
For nine steps, you have nine independent probabilities. You multiply them and then that
would be the overall probability of getting this self-avoiding walk. For example for this graph,
we're starting here at the first point. When we look ahead, we have one out of four probabilities
of moving anywhere because we can move up, down, right, or left. The first step we have one out
of four probability of moving to the left. Here we moved to the left and now we can no longer
go back to the right because we already visited this node. At the second node, we have a one
out of three probability of moving somewhere. We can move up, left, or down. The second event was
one third. When we go to the third node, we can no longer go up. We can go to the left, down, or right.
That's going to be one third probability. Here the node is going to have a one-half probability.
We can no longer go up because that was our first node that we visited and we cannot go to the left.
We have two possibilities. For this node, we have three again. That's going to be
one third probability of moving anywhere. For here, we can go one third places again. At this node we
cannot go left or down, so we have one out of two possibilities of going somewhere. At this node, we
have one out of three, and finally at this node we have one out of three again. That would get us
from point A to point B. And this would be the probability of having this self-avoiding
walk. When we do this multiplication, getting this self-avoiding walk of size nine using the one-step
ahead algorithm would be a probability of 1 over 1 1 6 6 4 and that's it for this video.
*chiptune music*