The last time I looked at random walks, I used them to calculate the value of Pi for Pi Day. But what is a random walk, really? A mathematician will tell you that it's a stochastic process—a path defined by a series of random steps. It's a pretty abstract concept, but I want to show you how it can reveal something fundamental about life itself—the proteins that make up you and me and everything around us.
So let's start with the simplest random walk, in one dimension.
One Dimensional Random Walk
Suppose I have an object. This object can either move one space to the left or one space to the right. Suppose I let it make 100 steps. Here's what that might look like. (click the "play" to run it)
That's at least marginally interesting, right? But the cool part is that if you run it a bunch of times, it will (on average) end up farther away from the starting point depending on the number of steps. Oh sure—it's possible that it could take 1,000 steps and end up where it started, but that probably won't happen.
But wait. There is another kind of random walk—there is the Self Avoiding Walk (SAW). This is just like a random walk except that the object can't cross over its own path. In one dimension this would just be an object that continues to move to the left or continues to move to the right. After it makes its first move, there is only one way it can go. This is a boring simulation, so I won't show it—but you can change line 37 in the code above so that it reads saw=True (case matters) and then it will be a self avoiding walk.
Now for a plot. Suppose I run the random walk (the normal one, not the self avoiding one) such that it goes 10 steps. If I repeat these 10 steps 500 times, I will get an average final distance. Then I can repeat this for 20 steps, then 30 steps and so on. After that (which takes a while to run), I get the following plot of average distance vs. number of steps. If you want to see the code to produce this plot, here it is (no warranty included).
What is important about this plot? Really, the only thing to notice is that this is different than a plot of a one dimensional random self avoiding walk. That plot would be boring as it would show the distance as equal to the number of steps (since it can't go back on itself).
Two Dimensional Random Walk
If we go in two dimensions, it gets a little more interesting. Check this out—it's a 2-D random self avoiding walk. I have it set for 100 steps, but it doesn't usually make it that far before it gets stuck. Yes, if the object avoids its own path it can get into a situation where it can not make a move. Check it out. Again, click the "play" to run it (it's fun).
Again, let's see what happens when I run it a bunch of times at 10 steps up to 500 steps. Note: I just have the program quit when it gets stuck for a SAW.
The curve that fits the data isn't important. The thing you should focus on is the difference between SAW and non-SAW data. Since the SAW can't cross its own path, it is forced to expand outward giving it (on average) a greater distance from the starting point. However, the SAW also gets stuck at some point such that it doesn't really get farther than 10 units away (that's why it levels off). I think that's pretty cool.
Three Dimensional Random Walk
When will it end? Will I just keep moving into more and more dimensions (spoiler alert: No, I am going to stop at 4-D). Here is a 3-D random SAW.
Note: I turned off "user zoom" so that you won't accidentally zoom to nothing. However, you can still rotate the scene since it's 3-D. Just right-click-drag or ctrl-click-drag to move the camera view of the 3-D path. It's pretty. Oh, also notice that this is rarely going to get "stuck." With six options for movement, there is probably going to be at least one of those directions that is open (and not already traveled).
What about average distance traveled for SAW vs. non-SAW? Here you go (note, this is the same program for all of these graphs).
Again, the SAW version ends up at a greater distance because the object can't cross its path and gets "pushed" out more. But both types of walks have nice curve fits with the increasing distance with step size to the power of 0.4975 and the SAW increasing at a power of 0.4688. So, they are close to being the same but still different.
Four Dimensional Random Walk
How do you make a random walk in four dimensions? Mathematically, it's pretty easy—you just need an extra variable to represent that fourth dimension (and no, you can't use time as a fourth dimension here). For my python code, I am just going use a vector for position along with an extra variable (that I call "w"). If you still want a visual animation, the code still works. It just displays motion in the fourth dimension as a change in color. That means that in a SAW, it's possible that the object appears to cross its own path—but it doesn't. Actually, it just moved in the fourth dimension (which you can't really see) and avoided the path. Here is the 4-D walk (notice that I didn't tell you to click "play").
Now for the important part. Here is a plot of final distance vs. step number for both the normal and the SAW.
Notice that there is still a difference between SAW and normal walks—but the difference is very small. Basically in 4-D the object doesn't really run into its own path so that it doesn't have to avoid itself. Oh, and I have never seen it get stuck (but it's still technically possible).
Random Walks in Real Life
You might be thinking that I'm just some crazy old man that's obsessed with random walks. OK, that's mostly true. But still—there are real world applications of random walks. In particular, proteins can be modeled as a random walk. I won't go into all the details of proteins except to say two things. First, these are long molecular chains. Second, proteins are important for living things like you and me. If a protein is like a random walk, then maybe this model shows why life is in three dimensions instead of one, two, or four. Hear me out. (Yes, I know I'm crazy.)
Life can't be in one dimension. Sure you could make a 1-D protein, but it would never do anything useful. It wouldn't interact with other things (except on the ends) and more importantly, it wouldn't interact with itself. If the protein chain can't fold over and connect back to itself, it can't make useful molecules (you know, for life and stuff).
What about two-dimensional life? The big problem here is that you can't make long proteins. Yeast proteins are over 400 units long. Good luck getting a random SAW that is over 50 units long without it getting stuck. You just can't get long proteins in two dimensions and you can't have yeast in 2-D. Without yeast, you can't have two-dimensional beer—so we know life can't exist in 2-D.
If more dimensions allows for longer proteins, then why isn't life in 4-D? Oh, don't worry about space being 3-D—that's a whole other debate we can save for another time. More importantly, there is a problem with 4-D random walks. Since there are so many options for each step, a random walk is unlikely to cross over its own path—which is bad for proteins. You want them to be able to get long but also to have the opportunity to connect to itself. In four dimensions, random walks do that rarely, which would make it difficult (unlikely) to get more complex molecules that are probably important for life.
Or maybe I'm still just a crazy dude that likes random walks.
How about some homework questions for you? Yes, that's a good idea.
- In all of my examples, I have a random walks (and SAW) as a lattice walk. This means that the vector location of the object always consists of components that are integers. This makes it much easier to program, but maybe it's not realistic. See if the same conclusions about random walks in different dimensions holds true for a random walk that takes a step size of 1 unit, but at a random angle. This is pretty easy in 2-D since you just need one random angle. In 3-D you need two angles (the angles from spherical coordinates). Not sure how do to this in 4-D. Oh, seeing if it crosses its own path is more difficult too. Good luck.
- What if you don't have a step size of 1 but instead each step has its own distance? Pick something like a normal distribution for step sizes and see if this same stuff works.
- What does the average distance vs. step number look like for a five-dimensional SAW and a 5-D random walk?
- What is the average number of steps before a random walk has a path conflict (such that it would have to either avoid its path or connect to make some type of molecule)? Yes, do this for two, three, and four dimensions.