Recent Posts


Random Walks

With this post, I want to introduce the concept of a random walk and point out some their many real-world applications.

Say you find yourself at the corner of a street block and decide to randomly move north, south, east, or west. After moving one block, you find yourself at the corner of a new block and industriously continue this process. This idea is the concept behind a random walk, particularly, one in two dimensions. Below, I animate some 100 step random walks in black fading them into red as they finish.

The stochasticity and spatial progression of a random walk makes them amenable to a variety of practical models in science. For example, random walks are used to model diffusion arising from effectively randomly directed elastic collations between many interacting particles—known as Brownian motion. The animation below shows an example of this phenomena by modeling the motion of a larger, yellow, particle being bombarded by many smaller ones and tracking the resultant motion.

Image Credit

This same principle is seen macroscopically examining diffusion of ink in water.

Image Credit

Naturally, we expect diffusion to be quicker if the surrounding particles are comparatively higher in energy. The above GIF illustrates this concept as temperature of the water in the right glass is higher than that of the left, resulting in the ink's faster diffusion.

In biology, random walks can be used to model the nearly random motion of bacteria as they search for food, a phenomenon dubbed chemotaxis. I say 'nearly random' because, in this case, the random walk is biased toward a particular direction. Loosely speaking, the food can be thought of as radiating particulates which bacteria have evolved to become attracted to, which effectively bias their walk in a specific direction. This process is animated below with the effective 'food source' at the center of the frame.

Image Credit

In many of these cases, it would be nice to know how far away from the origin a random will take you. Of course, we can never say with certainty the distance of a random walk, but we make an educated guess rooted in statistics. Quoting a result, it can be shown that the distance of a random walk is proportional to the square root of the number of steps taken. Simply put,

where N is the number of steps taken in the walk.

Now, let’s investigate these random walks and see if we can computationally recover some theoretical results. Rather than updating the figure after each step, as I had done in my first animation, I'll display the progression of the walk at certain step intervals to expedite the animations. The black lines will trace the current walk while the faded red lines show a history of previous walks. As walks accumulate, the most frequently visited areas will become opaquer while those rarely touched will remain translucent.

(Top) An animation of a ten 1,000 step random walks updated every 50 steps. (Bottom) An animation of ten 10,000 step random walks updated every 500 steps.

Notice, in both the above cases the areas near the beginning of the walk are visited more frequently than those at the boundaries. This is of course expected, as farther reaching walks are less likely to occur than those moving about the starting point.

As a quantifiable measure, we can examine the distance of the random walk observing its agreement with theoretically predicted results. To illustrate this, I’m affixing a graph which dynamically updates with each walk iteration displaying the distance travelled from the origin of each walk (red), the cumulative average distance of all previous walks (blue), and the theoretical prediction for the average distance (black). Moreover, rather than updating the graph at discrete step intervals, I’ll only flash the path of each walk in black as they finish.

100 step random walks

1,000 step random walks

10,000 step random walks

Regardless of the number of steps, we see the distance from the origin converging onto the theoretically predicted results in all cases. Furthermore, with the longer random walks, the opaque areas near the origin are evidently seen as more frequently visited then those on the outskirts.

As a final thought, there's a theorem which states that random walks starting from the origin in one and two dimensions are guaranteed to return to the origin in some finite number of steps. More generally, every walk in these lower dimensions is eventually guaranteed to visit every single point in space. This recurrence, however, is not true in higher dimensions, giving rise to the commonly quoted phrase regarding regarding random walks attributed to Shizuo Kakutani:

"A drunk man will find his way home, but a drunk bird may get lost forever."

Kirill Shmilovich

©2016 by Kirill Shmilovich