avatarMarcel Moosbrugger

Summarize

Random Walks Are Strange and Beautiful

A journey through dimensions and life

Photo by Jezael Melgoza on Unsplash

Imagine, you find yourself blindfolded in the center of a dense, unknown city. At each crossroad, flips of a coin decide your next steps: left, right, forward, or backward. With no vision to guide you and randomness as your only companion, you start an unpredictable journey.

This, in essence, captures the spirit of random walks, a powerful concept from probability theory that is much more useful than walking through a city blindfolded with a coin in our hand. Physicists use random walks to describe the movement of particles, and have applications in areas ranging from biology to social sciences. Understanding random walks allows data scientists to model, simulate and predict stochastic processes from many different areas.

Moreover, in reinforcement learning, agents can perform random walks to explore their environments and gain information about the effects of their actions.

In short, random walks are extremely versatile. But that is a whole other story.

Applications aside, random walks are simply fascinating. Even without the math behind them, we can appreciate the beautiful, yet complex and puzzling world they open for us. If you randomly walk around the city long enough and trace your steps, your path reveals a stunning pattern:

A random walk in two dimensions

The real mystery of random walks emerges when considering different dimensions. Our example of wandering through a city with coin flips is essentially a walk in two dimensions: we can move forward/backward — the first dimension — and left/right — the second dimension.

For a one-dimensional random walk, picture an ant walking on a string, taking any step forward or backward with equal probability. Now, as you might have guessed, for higher-dimensional random walks we have more and more directions to choose from. For instance, a bird can move left/right, forward/backward, and up/down. If it moves randomly, we have a random walk in three dimensions.

Visualizing random walks of even higher dimensions becomes hard, but we will get there. I promise. Before that, a fun question to ask ourselves is:

Is it guaranteed that a random walker returns to where it started?

Interestingly, this question very much depends on the dimension of the random walk. But let’s not get ahead ourselves. Let’s start slowly with the 1D-random-walk.

The Charm of One Dimension

As mentioned, a one-dimensional random walk can be pictured as an ant wandering on a string. But let’s put the analogies aside and make it more concrete using numbers.

We start at zero — the origin — and for every step either add one or subtract one, both with probability ½. We can visualize the walk like this:

The charm of the one-dimensional random walk is that it looks temptingly simple. Doesn’t it? The path we take is always a straight line.

However, despite the apparent simplicity, rich and complex phenomena lurk beneath the surface. To get a different perspective, let’s plot the position of the walk on the y-axis and time on the x-axis:

Although, the path we take is a straight line, our exact position is unpredictable. This phenomenon appears for example in fiber optics cables. Due to temperature fluctuations, the intensity of the light, or number of photons, traveling through the cable can change randomly. We can gain or loose some photons at every instance at random. Better understanding this effect is crucial to improve the quality of the signal.

Let’s go back to the world of mathematics. In the animation above, we can see that the random walk returns back to the origin at 0 after a few steps. In fact, this is guaranteed to happen if we wait long enough.

In 1D, the random walk eventually returns to the origin with probability 1.

Although, we might have expected this fact to be true, proving it is an entirely different story. Let me try to give a small glimpse into why this is true.

The random walk has many different possibilities of taking the first n steps. It turns out that the variance of the walk after n steps is also n and hence its standard deviation is √n. We cannot return to the origin after an odd number of steps. If we ever return, the number of steps must be even. Surprisingly, the probability of returning after an even number of n steps is about 1 over √n. Using this we get the following:

This means, that as the random walk runs and runs, the expected number of returns is infinite. We are not only guaranteed to return to the origin, but we do so infinitely often. In fact, we visit every point on the line infinitely often. If you are interested, there is a link to a more detailed derivation at the end [1]. But first, let’s add dimensions one by one and see where we get.

Exploring Two Dimensions

In two dimensions, like a vast chessboard that stretches into the horizon, we have four directions to choose from: left/right and forward/backward. In every step, the walk chooses a direction at random:

We have seen at the beginning what a complex and beautiful structure the two-dimensional random walk produces. If we take 100,000 steps at random and zoom out, the path we took looks almost organic:

The two-dimensional plane is infinitely larger than the one-dimensional line. We have many more points we can reach. Is it still guaranteed, that return back to where we started if we wait long enough? In fact, it is.

In 2D, the random walk eventually returns to the origin with probability 1.

In a very precise way, mathematicians figured out how to “split” a 2D random walk into two 1D random walks, which gives us the following.

Hence, similar to the one-dimensional random walk, in two dimensions we can expect to revisit the origin, and any other point, infinitely often. This is good news for our random walker wandering through the city with coin flips: should they get lost, it is guaranteed that they will eventually return to where they started.

The Complexity of Three Dimensions

Although both previous random walks return to their origin, going from one to two dimensions increased the complexity and structure significantly. Adding a third dimension, our walker now has six directions to choose from. Additionally to left/right and forward/backward, the process can now also move up or down.

After 10,000 steps, the final path reveals an intricate walk, or one might say flight, through space.

It is hard to judge whether or not the walker returned to the origin just from the plots. We have again infinitely more possible points compared to the two-dimensional random walk. But, this was also the case when moving from 1D to 2D. Still, in two dimensions the walker is guaranteed to come back eventually. So, is this still true in three dimensions? No!

In 3D, the random walk is more likely to wander off forever, than to return.

I was surprised when I saw this fact for the first time. How can a random walker return in dimensions 1 and 2 but not in 3? But the math checks out. Analogous the the return probabilities for the 2D random walk we have to multiply an extra 1 over √n for every dimension we add.

Because the expected number of returns to the origin is finite, we are not guaranteed to return at all. In fact, the return probability is about 34 %, which means we get lost forever with a probability of around 64 %. For higher dimensional random walks this probability only increases.

Let’s try to get an intuitive understanding of why random walks always return for lower dimensions but not for three, and more dimensions. As previously mentioned if a random walk returns to the origin it is also guaranteed to eventually visit every possible point. Moreover, the standard deviation of a random walk after n steps is √n, regardless of the dimension. Loosely speaking, this means that after n steps the random walker is likely no more than a distance of √n away from the origin. However, the number of points within a distance of √n to the origin grows as we add more and more dimensions. At three dimensions, the random walk just can’t keep up with the number of points. There are too many. It is easy to get lost in the third dimension.

The mathematician Shizuo Kakutani compared the 2D random walk to a drunken man stumbling around and the 3D random walk to a drunken bird, leading to his famous quote:

“A drunk man will find his way home, but a drunk bird may get lost forever.” — Shizuo Kakutani

The Beauty of Four Dimensions and the Unseen

Because the three-dimensional random walk is not guaranteed to return so is the random walk in four dimensions. But what does it even mean to take a walk in four dimensions?

Our walker has now four dimensions to roam in. Every dimension corresponds to two directions. So, at every step, our walker randomly chooses between eight directions. It is easy to describe the 4D random walk in this way, but it’s hard to picture it because we live in a three-dimensional world.

It seems impossible to even name the directions the walker can choose from. First, we have the familiar directions from 3D: left/right, forward/backward, and up/down. But what do we call the two directions in the fourth dimension? There are no obvious choices because as humans, we and everything we know are restricted to three spatial dimensions.

Extra Dimensions Are Hidden Everywhere

There is a trick we can employ. The fourth dimension doesn’t need to be a dimension of space. It is enough if the fourth dimension is represented as some concept independent of the other three spatial dimensions.

Let’s make this idea more concrete. Imagine our walker wanders around in three-dimensional space, but, additionally can measure and change its temperature. So, at every point in time, the walker can either take a step in any spatial direction, or increase or decrease its temperature by one degree, all with equal probability.

From this perspective, we circumvented the problems with visualizing the 4D random walk: we are left with three dimensions of space. Using colors for the temperature, we can even plot a four-dimensional random walk.

Our shift in perspective is much more than a neat trick. Letting go of the idea that dimensions must relate to space a whole new world opens up. Yes, we live in three-dimensional space. But as humans, we are much more than a point moving in space. We have desires and goals, fears and setbacks. We don’t merely walk, we love, we cry, and we take difficult decisions. The human experience is a beautiful journey through countless dimensions, many of which elude being captured by mathematics.

Although the outcome of individual steps and decisions in our lives is uncertain, and sometimes painful or full of risks, random walks remind us that it is the sum of all steps that sculpt our path through the complex dimensions of life, in the end revealing a unique and beautiful picture. What is your next step?

(Other than the cover photo, all images are by the author. You are free to use them as you see fit.)

Extra Resources

[1] Detailed derivation of return probabilities (excellent youtube video by Ari Seff)

Data Science
Probability
Random Walk
Getting Started
Dimensions
Recommended from ReadMedium